navigate.cpp

this keik game source

	{
	trace_t	trace;
	Vector	end;
	Vector	start;

	worldorigin.x = ( ( int )( worldorigin.x * 0.125 ) ) * 8;
	worldorigin.y = ( ( int )( worldorigin.y * 0.125 ) ) * 8;
	setOrigin( worldorigin );

   if ( !( contents & MASK_WATER ) )
      {
	   start = worldorigin + "0 0 1";
	   end = worldorigin;
	   end[ 2 ] -= 256;

	   trace = G_Trace( start, mins, maxs, end, NULL, MASK_PATHSOLID, "PathNode::FindChildren" );
	   if ( trace.fraction != 1 && !trace.allsolid )
		   {
		   setOrigin( trace.endpos );
		   }
      }

	PathManager.AddNode( this );
	}

EXPORT_FROM_DLL void PathNode::DrawConnections
	(
	void
	)
	
	{
	int i;
	pathway_t *path;
	PathNode *node;

	for( i = 0; i < numChildren; i++ )
		{
		path = &Child[ i ];
		node = AI_GetNode( path->node );

		G_DebugLine( worldorigin + "0 0 24", node->worldorigin + "0 0 24", 0.7, 0.7, 0, 1 );
		}
	}

EXPORT_FROM_DLL void DrawAllConnections
	(
	void
	)
	
	{
	int         i;
	pathway_t   *path;
	PathNode    *node;
	PathNode    *n;
   Vector      down;
   Vector      up;
   Vector      dir;
   Vector      p1;
   Vector      p2;
   Vector      p3;
   Vector      playerorigin;
   qboolean    showroutes;
   qboolean    shownums;
   qboolean    draw;
   int         maxheight;
   int         pathnum;

   showroutes = ( ai_showroutes->value != 0 );
   shownums = ( ai_shownodenums->value != 0 );

   if ( ai_showroutes->value == 1 )
      {
      pathnum = ( 32 / WIDTH_STEP ) - 1;
      }
   else
      {
      pathnum = ( ( ( int )ai_showroutes->value ) / WIDTH_STEP ) - 1;
      }

   if ( ( pathnum < 0 ) || ( pathnum >= MAX_WIDTH ) )
      {
      gi.printf( "ai_showroutes: Value out of range\n" );
      gi.cvar_set( "ai_showroutes", "0" );
      return;
      }

   // Figure out where the camera is
   assert( g_edicts[ 1 ].client );
   playerorigin.x = g_edicts[ 1 ].client->ps.pmove.origin[ 0 ];
   playerorigin.y = g_edicts[ 1 ].client->ps.pmove.origin[ 1 ];
   playerorigin.z = g_edicts[ 1 ].client->ps.pmove.origin[ 2 ];
   playerorigin *= 0.125;
   playerorigin += g_edicts[ 1 ].client->ps.viewoffset;

	for( node = NodeList; node != NULL; node = node->chain )
		{
		if ( !gi.inPVS( playerorigin.vec3(), node->worldorigin.vec3() ) )
			{
			continue;
			}

      if ( shownums )
         {
         G_DrawDebugNumber( node->worldorigin + Vector( 0, 0, 14 ), node->nodenum, 1.5, 1, 1, 0 );
         }

      draw = false;
		for( i = 0; i < node->numChildren; i++ )
			{
			path = &node->Child[ i ];
			n = AI_GetNode( path->node );

         if ( !showroutes )
            {
            continue;
            }

			maxheight = path->maxheight[ pathnum ];
         if ( maxheight == 0 )
            {
            continue;
            }

         draw = true;

         // don't draw the path if it's already been drawn by the destination node
         if ( n->drawtime < level.time )
            {
            down.z = 2;
            up.z = maxheight;
			   G_DebugLine( node->worldorigin + down, n->worldorigin + down,     0, 1, 0, 1 );
			   G_DebugLine( n->worldorigin + down,    n->worldorigin + up,       0, 1, 0, 1 );
			   G_DebugLine( node->worldorigin + up,   n->worldorigin + up,       0, 1, 0, 1 );
			   G_DebugLine( node->worldorigin + up,   node->worldorigin + down,  0, 1, 0, 1 );
            }

         // draw an arrow for the direction
         dir.x = n->worldorigin.x - node->worldorigin.x;
         dir.y = n->worldorigin.y - node->worldorigin.y;
         dir.normalize();

         p1 = node->worldorigin;
         p1.z += maxheight * 0.5;
         p2 = dir * 8;
         p3 = p1 + p2 * 2;

         G_DebugLine( p1, p3, 0, 1, 0, 1 );

         p2.z += 8;
         G_DebugLine( p3, p3 - p2, 0, 1, 0, 1 );

         p2.z -= 16;
         G_DebugLine( p3, p3 - p2, 0, 1, 0, 1 );
			}

      if ( !draw )
         {
         // Put a little X where the node is to show that it had no connections
         p1 = node->worldorigin;
         p1.z += 2;

         p2 = Vector( 12, 12, 0 );
         G_DebugLine( p1 - p2, p1 + p2, 1, 0, 0, 1 );

         p2.x = -12;
         G_DebugLine( p1 - p2, p1 + p2, 1, 0, 0, 1 );
         }

		node->drawtime = level.time;
		}
	}

MapCell::MapCell()
	{
	Init();
	}

MapCell::~MapCell()
	{
	Init();
	}

EXPORT_FROM_DLL void MapCell::Init
	(
	void
	)

	{
	numnodes = 0;
	memset( nodes, 0, sizeof( nodes ) );
	}

EXPORT_FROM_DLL qboolean MapCell::AddNode
	(
	PathNode *node
	)

	{
	if ( numnodes >= PATHMAP_NODES )
		{
		return false;
		}

	nodes[ numnodes ] = ( short )node->nodenum;
	numnodes++;

	return true;
	}

EXPORT_FROM_DLL qboolean MapCell::RemoveNode
	(
	PathNode *node
	)

	{
	int i;
	int num;

	num = node->nodenum;
	for( i = 0; i < numnodes; i++ )
		{
		if ( num == ( int )nodes[ i ] )
			{
			break;
			}
		}

	if ( i >= numnodes )
		{
		return false;
		}

	numnodes--;

	// Since we're not worried about the order of the nodes, just
	// move the last node into the slot occupied by the removed node.
	nodes[ i ] = nodes[ numnodes ];
	nodes[ numnodes ] = 0;

	return true;
	}

EXPORT_FROM_DLL PathNode *MapCell::GetNode
	(
	int index
	)

	{
	assert( index >= 0 );
	assert( index < numnodes );
	if ( index >= numnodes )
		{
		return NULL;
		}

	return AI_GetNode( nodes[ index ] );
	}

EXPORT_FROM_DLL int MapCell::NumNodes
	(
	void
	)

	{
	return numnodes;
	}

/*                         All
                     work and no play
                 makes Jim a dull boy. All
               work and no  play makes Jim a  
             dull boy. All  work and no  play 
           makes Jim a dull boy. All work and no  
         play makes Jim a dull  boy. All work and 
        no play makes Jim a dull boy. All work and  
       no play makes Jim a dull boy. All work and no  
      play makes Jim a dull boy. All work and no play  
     makes Jim a dull boy. All work and no play makes  
    Jim a dull boy.  All work and no  play makes Jim a  
   dull boy. All work and no play makes Jim a dull boy.  
   All work and no play makes  Jim a dull boy. All work  
  and no play makes Jim a dull boy. All work and no play  
  makes Jim a dull boy. All work and no play makes Jim a  
 dull boy. All work and no play makes Jim a dull boy. All  
 work and no play makes  Jim a dull boy. All  work and no 
 play makes Jim a dull boy. All work and no play makes Jim  
 a dull boy. All work  and no play makes Jim  a dull boy. 
 All work and no play makes Jim  a dull boy. All work and 
 no play makes Jim a dull boy. All work and no play makes  
 Jim a dull boy.  All work and no  play makes Jim a  dull 
 boy. All work and no play makes Jim a dull boy. All work  
 and no play makes Jim  a dull boy. All work  and no play 
 makes Jim a dull boy.  All work and no play  makes Jim a 
 dull boy. All work and no play makes Jim a dull boy. All  
  work and no play makes Jim a dull boy. All work and no  
  play makes Jim a dull boy.  All work and no play makes  
   Jim a dull boy. All work and no play makes Jim a dull  
   boy. All work and no play  makes Jim a dull boy. All  
    work and no play makes Jim a dull boy. All work and  
     no play makes  Jim a dull  boy. All work  and no 
      play makes Jim a dull boy. All work and no play  
       makes Jim a dull  boy. All work and  no play 
        makes Jim a dull boy. All work and no play  
         makes Jim a  dull boy. All  work and no  
           play makes Jim a  dull boy. All work  
             and no play makes Jim a dull boy.  
               All work  and no  play makes  
                 Jim a dull boy. All work  
                     and no play makes  
                          Jim  a  
*/

CLASS_DECLARATION( Class, PathSearch, NULL );

ResponseDef PathSearch::Responses[] =
	{
		{ &EV_AI_SavePaths,				( Response )PathSearch::SavePathsEvent },
		{ &EV_AI_LoadNodes,				( Response )PathSearch::LoadNodes },
		{ &EV_AI_SaveNodes,				( Response )PathSearch::SaveNodes },
		{ &EV_AI_ClearNodes,				( Response )PathSearch::ClearNodes },
      { &EV_AI_SetNodeFlags,        ( Response )PathSearch::SetNodeFlagsEvent },
      { &EV_AI_RecalcPaths,         ( Response )PathSearch::RecalcPathsEvent },
      { &EV_AI_CalcPath,            ( Response )PathSearch::CalcPathEvent },
      { &EV_AI_DisconnectPath,      ( Response )PathSearch::DisconnectPathEvent },

		{ NULL, NULL }
	};

void PathSearch::AddToGrid
	(
	PathNode *node,
	int x,
	int y
	)

	{
	PathNode *node2;
	MapCell *cell;
	int numnodes;
	int i;
	int j;
	byte maxheight[ NUM_WIDTH_VALUES ];

	cell = GetNodesInCell( x, y );
	if ( !cell )
		{
		return;
		}

	if ( !cell->AddNode( node ) )
		{
		warning( "AddToGrid", "Node overflow at ( %d, %d )\n", x, y );
		return;
		}

	if ( !loadingarchive )
		{
      //
      // explicitly link up the targets and their destinations
      //
      if ( node->nodeflags & AI_JUMP )
         {
         if ( node->target.length() > 1 )
            {
            node2 = AI_FindNode( node->target.c_str() );
            if ( node2 )
               {
				   for( j = 0; j < NUM_WIDTH_VALUES; j++ )
					   {
					   maxheight[ j ] = MAX_HEIGHT;
					   }
				   node->ConnectTo( node2, maxheight );
               }
            }
         }

		// Connect the node to its neighbors
		numnodes = cell->NumNodes();
		for( i = 0; i < numnodes; i++ )
			{
			node2 = ( PathNode * )cell->GetNode( i );
			if ( node2 == node )
				{
				continue;
				}

			if ( ( node->numChildren < NUM_PATHSPERNODE ) && !node->ConnectedTo( node2 ) )
            {
            if ( node->ClearPathTo( node2, maxheight ) || node->LadderTo( node2, maxheight ) )
				   {
				   node->ConnectTo( node2, maxheight );
				   }
			   else if ( ( node->nodeflags & AI_JUMP ) && ( node->target == node2->targetname ) )
				   {
				   //FIXME
				   // don't hardcode size
				   for( j = 0; j < NUM_WIDTH_VALUES; j++ )
					   {
					   maxheight[ j ] = MAX_HEIGHT;
					   }
				   node->ConnectTo( node2, maxheight );
				   }
            }

			if ( ( node2->numChildren < NUM_PATHSPERNODE ) && !node2->ConnectedTo( node ) )
            {
				if ( node2->ClearPathTo( node, maxheight ) || node2->LadderTo( node, maxheight ) )
				   {
				   node2->ConnectTo( node, maxheight );
				   }
            else if ( ( node2->nodeflags & AI_JUMP ) && ( node2->target == node->targetname ) )
				   {
				   //FIXME
				   // don't hardcode size
				   for( j = 0; j < NUM_WIDTH_VALUES; j++ )
					   {
					   maxheight[ j ] = MAX_HEIGHT;
					   }
				   node2->ConnectTo( node, maxheight );
				   }
            }
			}
		}
	}

qboolean PathSearch::RemoveFromGrid
	(
	PathNode *node,
	int x,
	int y
	)

	{
	MapCell	*cell;
	PathNode *node2;
	int		numnodes;
	int		i;

	cell = GetNodesInCell( x, y );
	if ( !cell || !cell->RemoveNode( node ) )
		{
		return false;
		}

	// Disconnect the node from all nodes in the cell
	numnodes = cell->NumNodes();
	for( i = 0; i < numnodes; i++ )
		{
		node2 = ( PathNode * )cell->GetNode( i );
		if ( node2->ConnectedTo( node ) )
			{
			node2->Disconnect( node );
			}
		}

	return true;
	}

int PathSearch::NodeCoordinate
	(
	float coord
	)

	{
	return ( ( int )coord + 4096 - ( PATHMAP_CELLSIZE / 2 ) ) / PATHMAP_CELLSIZE;
	}

int PathSearch::GridCoordinate
	(
	float coord
	)

	{
	return ( ( int )coord + 4096 ) / PATHMAP_CELLSIZE;
	}

void PathSearch::AddNode
	(
	PathNode *node
	)

	{
	int x;
	int y;

	assert( node );

	numNodes++;

	if ( NodeList == NULL )
		{
		NodeList = node;
		node->chain = NULL;
		}
	else
		{
		node->chain = NodeList;
		NodeList = node;
		}

	x = NodeCoordinate( node->worldorigin[ 0 ] );
	y = NodeCoordinate( node->worldorigin[ 1 ] );

	AddToGrid( node, x, y );
	AddToGrid( node, x + 1, y );
	AddToGrid( node, x,	y + 1 );
	AddToGrid( node, x + 1, y + 1 );

	node->gridX = x;
	node->gridY = y;
	}

void PathSearch::RemoveNode
	(
	PathNode *node
	)

	{
	int x;
	int y;
	PathNode *n;
	PathNode *p;

	assert( node );

	x = node->gridX;
	y = node->gridY;

	RemoveFromGrid( node, x, y );
	RemoveFromGrid( node, x + 1, y );
	RemoveFromGrid( node, x, y + 1 );
	RemoveFromGrid( node, x + 1, y + 1 );

	p = NULL;
	for( n = NodeList; n != node; p = n, n = n->chain )
		{
		if ( !n )
			{
			// Not in list.
			return;
			}
		}

	if ( p )
		{
		p->chain = n->chain;
		}
	else
		{
		NodeList = n->chain;
		}

	n->chain = NULL;
	numNodes--;
	}

void PathSearch::UpdateNode
	(
	PathNode *node
	)

	{
	int x;
	int y;
	int mx;
	int my;

	assert( node );

	x = NodeCoordinate( node->worldorigin[ 0 ] );
	y = NodeCoordinate( node->worldorigin[ 1 ] );

	mx = node->gridX;
	my = node->gridY;

	RemoveFromGrid( node, mx, my );
	RemoveFromGrid( node, mx + 1, my );
	RemoveFromGrid( node, mx, my + 1 );
	RemoveFromGrid( node, mx + 1, my + 1 );

	node->numChildren = 0;

	AddToGrid( node, x, y );
	AddToGrid( node, x + 1, y );
	AddToGrid( node, x,	y + 1 );
	AddToGrid( node, x + 1, y + 1 );

	node->gridX = x;
	node->gridY = y;
	}
	
MapCell *PathSearch::GetNodesInCell
	(
	int x,
	int y
	)

	{
	if ( ( x < 0 ) || ( x >= PATHMAP_GRIDSIZE ) || ( y < 0 ) || ( y >= PATHMAP_GRIDSIZE ) )
		{
		return NULL;
		}

	return &PathMap[ x ][ y ];
	}

MapCell *PathSearch::GetNodesInCell
	(
	Vector pos
	)

	{
	int x;
	int y;

	x = GridCoordinate( pos[ 0 ] );
	y = GridCoordinate( pos[ 1 ] );

	return GetNodesInCell( x, y );
	}

EXPORT_FROM_DLL PathNode *PathSearch::NearestNode
	(
	Vector pos,
   Entity *ent,
   qboolean usebbox
	)

	{
	Vector	delta;
	PathNode	*node;
	PathNode	*bestnode;
	float		bestdist;
	float		dist;
	int		n;
	int		i;
	MapCell	*cell;
	Vector	min;