text: ////////////////////////////////////////////////////////////////////////////
  //	Module 		: level_graph.cpp
  //	Created 	: 02.10.2001
  //  Modified 	: 11.11.2003
  //	Author		: Oles Shihkovtsov, Dmitriy Iassenev
  //	Description : Level graph
  ////////////////////////////////////////////////////////////////////////////
  
  #include "stdafx.h"
  #include "level_graph.h"
  #include "profiler.h"
  
  LPCSTR LEVEL_GRAPH_NAME = "level.ai";
  
  #ifdef AI_COMPILER
  CLevelGraph::CLevelGraph		(LPCSTR filename)
  #else
  CLevelGraph::CLevelGraph		()
  #endif
  {
  #ifndef AI_COMPILER
  #ifdef DEBUG
  	sh_debug.create				("debug\\ai_nodes","$null");
  #endif
  	string_path					file_name;
  	FS.update_path				(file_name,"$level$",LEVEL_GRAPH_NAME);
  #else
  	string256					file_name;
  	strconcat					(sizeof(file_name), file_name, filename, LEVEL_GRAPH_NAME);
  #endif
  	m_reader					= FS.r_open	(file_name);
  
  	// m_header & data
  	m_header					= (CHeader*)m_reader->pointer();
  	R_ASSERT					(header().version() == XRAI_CURRENT_VERSION);
  	m_reader->advance			(sizeof(CHeader));
  	m_nodes						= (CVertex*)m_reader->pointer();
  	m_row_length				= iFloor((header().box().max.z - header().box().min.z)/header().cell_size() + EPS_L + 1.5f);
  	m_column_length				= iFloor((header().box().max.x - header().box().min.x)/header().cell_size() + EPS_L + 1.5f);
  	m_access_mask.assign		(header().vertex_count(),true);
  	unpack_xz					(vertex_position(header().box().max),m_max_x,m_max_z);
  
  #ifdef DEBUG
  #	ifndef AI_COMPILER
  		m_current_level_id		= -1;
  		m_current_actual		= false;
  		m_current_center		= Fvector().set(flt_max,flt_max,flt_max);
  		m_current_radius		= Fvector().set(flt_max,flt_max,flt_max);
  #	endif
  #endif
  }
  
  CLevelGraph::~CLevelGraph		()
  {
  	FS.r_close					(m_reader);
  }
  
  u32	CLevelGraph::vertex		(const Fvector &position) const
  {
  	CLevelGraph::CPosition	_node_position;
  	vertex_position			(_node_position,position);
  	float					min_dist = flt_max;
  	u32						selected;
  	set_invalid_vertex		(selected);
  	for (u32 i=0; i<header().vertex_count(); ++i) {
  		float				dist = distance(i,position);
  		if (dist < min_dist) {
  			min_dist		= dist;
  			selected		= i;
  		}
  	}
  
  	VERIFY					(valid_vertex_id(selected));
  	return					(selected);
  }
  
  u32 CLevelGraph::vertex		(u32 current_node_id, const Fvector& position) const
  {
  	START_PROFILE("Level_Graph::find vertex")
  #ifndef AI_COMPILER
  	Device.Statistic->AI_Node.Begin	();
  #endif
  
  	u32						id;
  
  	if (valid_vertex_position(position)) {
  		// so, our position is inside the level graph bounding box
  		if (valid_vertex_id(current_node_id) && inside(vertex(current_node_id),position)) {
  			// so, our node corresponds to the position
  #ifndef AI_COMPILER
  			Device.Statistic->AI_Node.End();
  #endif
  			return				(current_node_id);
  		}
  
  		// so, our node doesn't correspond to the position
  		// try to search it with O(logN) time algorithm
  		u32						_vertex_id = vertex_id(position);
  		if (valid_vertex_id(_vertex_id)) {
  			// so, there is a node which corresponds with x and z to the position
  			bool				ok = true;
  			if (valid_vertex_id(current_node_id)) {
  				float				y0 = vertex_plane_y(current_node_id,position.x,position.z);
  				float				y1 = vertex_plane_y(_vertex_id,position.x,position.z);
  				bool				over0 = position.y > y0;
  				bool				over1 = position.y > y1;
  				float				y_dist0 = position.y - y0;
  				float				y_dist1 = position.y - y1;
  				if (over0) {
  					if (over1) {
  						if (y_dist1 - y_dist0 > 1.f)
  							ok		= false;
  						else
  							ok		= true;
  					}
  					else {
  						ok			= false;
  					}
  				}
  				else {
  					if (over1) {
  						ok			= true;
  					}
  					else {
  						ok			= false;
  					}
  				}
  			}
  			if (ok) {
  #ifndef AI_COMPILER
  				Device.Statistic->AI_Node.End();
  #endif
  				return			(_vertex_id);
  			}
  		}
  	}
  
  	if (!valid_vertex_id(current_node_id)) {
  		// so, we do not have a correct current node
  		// performing very slow full search
  		id					= vertex(position);
  		VERIFY				(valid_vertex_id(id));
  #ifndef AI_COMPILER
  		Device.Statistic->AI_Node.End();
  #endif
  		return				(id);
  	}
  
  	// so, our position is outside the level graph bounding box
  	// or
  	// there is no node for the current position
  	// try to search the nearest one iteratively
  	SContour			_contour;
  	Fvector				point;
  	u32					best_vertex_id = current_node_id;
  	contour				(_contour,current_node_id);
  	nearest				(point,position,_contour);
  	float				best_distance_sqr = position.distance_to_sqr(point);
  	const_iterator		i,e;
  	begin				(current_node_id,i,e);
  	for ( ; i != e; ++i) {
  		u32				level_vertex_id = value(current_node_id,i);
  		if (!valid_vertex_id(level_vertex_id))
  			continue;
  
  		contour			(_contour,level_vertex_id);
  		nearest			(point,position,_contour);
  		float			distance_sqr = position.distance_to_sqr(point);
  		if (best_distance_sqr > distance_sqr) {
  			best_distance_sqr	= distance_sqr;
  			best_vertex_id		= level_vertex_id;
  		}
  	}
  
  #ifndef AI_COMPILER
  	Device.Statistic->AI_Node.End();
  #endif
  	return					(best_vertex_id);
  
  	STOP_PROFILE
  }
  
  u32	CLevelGraph::vertex_id				(const Fvector &position) const
  {
  	CPosition			_vertex_position = vertex_position(position);
  	CVertex				*B = m_nodes;
  	CVertex				*E = m_nodes + header().vertex_count();
  	CVertex				*I = std::lower_bound	(B,E,_vertex_position.xz());
  	if ((I == E) || ((*I).position().xz() != _vertex_position.xz()))
  		return			(u32(-1));
  
  	u32					best_vertex_id = u32(I - B);
  	float				y = vertex_plane_y(best_vertex_id,position.x,position.z);
  	for (++I; I != E; ++I) {
  		if ((*I).position().xz() != _vertex_position.xz())
  			break;
  
  		u32				new_vertex_id = u32(I - B);
  		float			_y = vertex_plane_y(new_vertex_id,position.x,position.z);
  		if (y <= position.y) {
  			// so, current node is under the specified position
  			if (_y <= position.y) {
  				// so, new node is under the specified position
  				if (position.y - _y < position.y - y) {
  					// so, new node is closer to the specified position
  					y				= _y;
  					best_vertex_id	= new_vertex_id;
  				}
  			}
  		}
  		else
  			// so, current node is over the specified position
  			if (_y <= position.y) {
  				// so, new node is under the specified position
  				y				= _y;
  				best_vertex_id	= new_vertex_id;
  			}
  			else
  				// so, new node is over the specified position
  				if (_y - position.y  < y - position.y) {
  					// so, new node is closer to the specified position
  					y				= _y;
  					best_vertex_id	= new_vertex_id;
  				}
  	}
  
  	return			(best_vertex_id);
  }