navigate.cpp

this keik game source

            Child[ i ].door = door->entnum;
            }
         else
            {
            Child[ i ].door = 0;
            }
         }
		}
	}

EXPORT_FROM_DLL void PathNode::Unarchive
	(
	Archiver &arc
	)

	{
	int i;

	nodenum = arc.ReadInteger();
	assert( nodenum <= MAX_PATHNODES );
	if ( nodenum > MAX_PATHNODES )
		{
		arc.FileError( "Node exceeds max path nodes" );
		}

	nodeflags = arc.ReadInteger();

	setOrigin( arc.ReadVector() );
	setAngles( arc.ReadVector() );

	setangles	= arc.ReadBoolean();
	target	   = arc.ReadString();
	targetname	= arc.ReadString();
	animname		= arc.ReadString();

   occupiedTime = arc.ReadFloat();
   entnum       = arc.ReadInteger();
   if ( !LoadingSavegame )
      {
      occupiedTime = 0;
      entnum       = 0;
      }

	numChildren = arc.ReadInteger();
	assert( numChildren <= NUM_PATHSPERNODE );
	if ( numChildren > NUM_PATHSPERNODE )
		{
		arc.FileError( "Exceeded num paths per node" );
		}

	for( i = 0; i < numChildren; i++ )
		{
		Child[ i ].node		= arc.ReadShort();
		Child[ i ].moveCost	= arc.ReadShort();
		arc.ReadRaw( Child[ i ].maxheight, sizeof( Child[ i ].maxheight ) );
		Child[ i ].door		= arc.ReadInteger();
		}

   if ( !LoadingSavegame )
      {
      // Fixup the doors
      PostEvent( EV_Path_FindEntities, 0 );
      }

	pathnodes[ nodenum ] = this;
	if ( ai_maxnode < nodenum )
		{
		ai_maxnode = nodenum;
		}

	PathManager.AddNode( this );
	}

EXPORT_FROM_DLL void RestoreEnts
	(
	void
	)

	{
	int i;

	for( i = 0; i < NumIgnoreObjects; i++ )
		{
		IgnoreObjects[ i ]->link();
		}
	}

EXPORT_FROM_DLL qboolean PathNode::TestMove
	(
   Entity *ent,
   Vector start,
   Vector end,
	Vector &min,
	Vector &max,
	qboolean allowdoors,
   qboolean fulltest
	)

	{
   // NOTE: TestMove may allow wide paths to succeed when they shouldn't since it 
   // may place the lower node above obstacles that actors can't step over.
   // Since any path that's wide enough for large boxes must also allow
   // thinner boxes to go through, you must ignore the results of TestMove
   // when thinner checks have already failed.
	trace_t  trace;
	Vector   end_trace;
   Vector   pos;
   Vector   dir;
   float    t;
   float    dist;

   // By requiring that paths have STEPSIZE headroom above the path, we simplify the test
   // to see if an actor can move to a node down to a simple trace.  By stepping up the start
   // and end points, we account for the actor's ability to step up any geometry lower than
   // STEPSIZE in height.
   start.z += STEPSIZE;
   end.z += STEPSIZE;

   // Check the move
   trace = G_Trace( start, min, max, end, ent, MASK_PATHSOLID, "PathNode::TestMove 1" );
   if ( trace.startsolid || ( trace.fraction != 1 ) )
		{
      // No direct path available.  The actor will most likely not be able to move through here.
      return false;
		}

   if ( !fulltest )
      {
      // Since we're not doing a full test (full tests are only done when we're connecting nodes to save time),
      // we test to see if the midpoint of the move would only cause a change in height of STEPSIZE
      // from the predicted height.  This prevents most cases where a dropoff lies between a actor and a node.
	   Vector pos;
	   
      // Since we start and end are already STEPSIZE above the ground, we have to check twice STEPSIZE below
      // the midpoint to see if the midpoint is on the ground.
      dir = end - start;
      pos = start + dir * 0.5;
	   end_trace = pos;
      end_trace.z -= STEPSIZE * 2;

	   // Check that the midpos is onground.  This may fail on ok moves, but a true test would be too slow 
      // to do in real time.  Also, we may miss cases where a dropoff exists before or after the midpoint.
      // Once the actor is close enough to the drop off, it will discover the fall and hopefully try
      // another route.
	   trace = G_Trace( pos, min, max, end_trace, ent, MASK_PATHSOLID, "PathNode::TestMove 2" );
      if ( trace.startsolid || ( trace.fraction == 1 ) )
		   {
         // We're not on the ground, so there's a good posibility that we can't make this move without falling.
		   return false;
		   }
      }
   else if ( !( contents & MASK_WATER ) )
      {
      // When we're creating the paths during load time, we do a much more exhaustive test to see if the
      // path is valid.  This test takes a bounding box and moves it 8 units at a time closer to the goal,
      // testing the ground after each move.  The test involves checking whether we will fall more than
      // STEPSIZE to the ground (since we've raised the start and end points STEPSIZE above the ground,
      // we must actually test 2 * STEPSIZE down to see if we're on the ground).  After each test, we set
      // the new height of the box to be STEPSIZE above the ground.  Each move closer to the goal is only
      // done horizontally to simulate how the actors normally move.  This method ensures that any actor
      // wider than 8 units in X and Y will be able to move from start to end.
      //
      // NOTE: This may allow wide paths to succeed when they shouldn't since it 
      // may place the lower node above obstacles that actors can't step over.
      // Since any path that's wide enough for large boxes must also allow
      // thinner boxes to go through, you must ignore the results of TestMove
      // when thinner checks have already failed.

      dir = end - start;
	   dir.z = 0;
	   dist = dir.length();
      dir *= 1 / dist;

	   // check the entire move
	   pos = start;
	   for( t = 0; t < dist; t += 8 )
		   {
         // Move the box to our position along the path and make our downward trace vector
		   end_trace.x = pos.x = start.x + t * dir.x;
		   end_trace.y = pos.y = start.y + t * dir.y;
         end_trace.z = pos.z - STEPSIZE * 2;

         // check the ground
		   trace = G_Trace( pos, min, max, end_trace, ent, MASK_PATHSOLID, "PathNode::TestMove 3" );
		   if ( trace.startsolid || ( trace.fraction == 1 ) )
			   {
            // Either we're stuck in something solid, or we would fall farther than STEPSIZE to the ground,
            // so the path is not acceptable.
            return false;
			   }

         // move the box to STEPSIZE above the ground.
		   pos.z = trace.endpos[ 2 ] + STEPSIZE;
		   }
      }

   return true;
	}

EXPORT_FROM_DLL qboolean PathNode::CheckMove
	(
   Entity *ent,
   Vector pos,
	Vector &min,
	Vector &max,
	qboolean allowdoors,
   qboolean fulltest
	)

   {
   // Since we need to support actors of variable widths, we need to do some special checks when a potential
   // path goes up or down stairs.  Placed pathnodes are only 16x16 in width, so when they are dropped to the
   // ground, they may end in a position where a larger box would not fit.  Making the pathnodes larger
   // would make it hard to place paths where smaller actors could go, and making paths of various sizes would
   // be overkill (more work for the level designer, or a lot of redundant data).  The solution is to treat
   // paths with verticle movement differently than paths that are purely horizontal.  For horizontal moves,
   // a simple trace STEPSIZE above the ground will be sufficient to prove that we can travel from one node
   // to another, in either direction.  For moves that have some change in height, we can check that we have
   // a clear path by tracing horizontally from the higher node to a point where larger bounding box actors
   // could then move at a slope downward to the lower node.  This fixes the problem where path points that
   // are larger than the depth of a step would have to intersect with the step in order to get the center
   // of the box on solid ground.  If you're still confused, well, tough. :)  Think about the problem of
   // larger bounding boxes going up stairs for a bit and you should see the problem.  You can also read
   // section 8.4, "Translating a Convex Polygon", from Computational Geometry in C (O'Rourke) (a f'ing
   // great book, BTW) for information on similar problems (which is also a good explanation of how
   // Quake's collision detection works).
   trace_t trace;
   int height;

   height = ( int )fabs( pos.z - worldorigin.z );
   // Check if the path is strictly horizontal
   if ( !height )
      {
      // We do two traces for the strictly horizontal test.  One normal, and one STEPSIZE
      // above.  The normal trace is needed because most doors in the game aren't tall enough
      // to allow actors to trace STEPSIZE above the ground.  This means that failed horizontal
      // tests require two traces.  Annoying.
      trace = G_Trace( worldorigin, min, max, pos, ent, MASK_PATHSOLID, "PathNode::CheckMove 1" );
      if ( !trace.startsolid && ( trace.fraction == 1 ) )
		   {
         return true;
		   }

      // Do the step test
      return TestMove( ent, pos, worldorigin, min, max, allowdoors, fulltest );
      }
   
   Vector size;
   float  width;

   size = max - min;
   width = max( size.x, size.y );

   // if our bounding box is smaller than that of the pathnode, we can do the standard trace.
   if ( width <= 32 )
      {
      return TestMove( ent, pos, worldorigin, min, max, allowdoors, fulltest );
      }

   Vector start;
   Vector end;
   Vector delta;
   float  radius;
   float  len;

   // We calculate the radius of the smallest cylinder that would contain the bounding box.
   // In some cases, this would make the first horizontal move longer than it needs to be, but
   // that shouldn't be a problem.

   // multiply the width by 1/2 the square root of 2 to get radius
   radius = width * 1.415 * 0.5;

   // Make sure that our starting position is the higher node since it doesn't matter which
   // direction the move is in.
   if ( pos.z < worldorigin.z )
      {
      start = worldorigin;
      end = pos;
      }
   else
      {
      start = pos;
      end = worldorigin;
      }

   // If the distance between the two points is less than the radius of the bounding box,
   // then we only have to do the horizontal test since larger bounding boxes would not fall.
   delta = end - start;
   len = delta.length();
   if ( len <= radius )
      {
      end.z = start.z;
      return TestMove( ent, start, end, min, max, allowdoors, fulltest );
      }

   Vector mid;

   // normalize delta and multiply by radius (saving a few multiplies by combining into one).
   delta *= radius / len;

   mid = start;
   mid.x += delta.x;
   mid.y += delta.y;

   // Check the horizontal move
   if ( !TestMove( ent, start, mid, min, max, allowdoors, fulltest ) )
      {
      return false;
      }

   // Calculate our new endpoint
   end.z -= delta.z;

   // Check our new sloping move
   return TestMove( ent, mid, end, min, max, allowdoors, fulltest );
   }

EXPORT_FROM_DLL Door *PathNode::CheckDoor
	(
	Vector pos
	)

	{
	trace_t	trace;
	Entity	*ent;

	trace = G_Trace( worldorigin, vec_zero, vec_zero, pos, NULL, MASK_PATHSOLID, "PathNode::CheckDoor" );

	ent = trace.ent->entity;
	if ( ent && ent->isSubclassOf( Door ) )
		{
		return ( Door * )ent;
		}

	return NULL;
	}

EXPORT_FROM_DLL qboolean PathNode::CheckMove
	(
	Vector pos,
	Vector min,
	Vector max
	)

	{
	return true;
	}

EXPORT_FROM_DLL qboolean PathNode::CheckPath
	(
	PathNode *node,
	Vector min,
	Vector max,
   qboolean fulltest
	)

	{
	Vector	delta;
	qboolean allowdoors;
   qboolean result;

	delta = node->worldorigin - worldorigin;
	delta[ 2 ] = 0;
	if ( delta.length() >= PATHMAP_CELLSIZE )
		{
		return false;
		}

	allowdoors = ( nodeflags & AI_DOOR ) && ( node->nodeflags & AI_DOOR );

   result = CheckMove( NULL, node->worldorigin, min, max, allowdoors, fulltest );
	RestoreEnts();

   return result;
	}

EXPORT_FROM_DLL qboolean PathNode::ClearPathTo
	(
	PathNode *node,
	byte maxheight[ NUM_WIDTH_VALUES ],
   qboolean fulltest
	)

	{
	int      i;
	int      width;
   int      height;
   int      bottom;
   int      top;
	Vector   min;
	Vector   max;
   Vector   bmin;
   Vector   bmax;
	qboolean path;
	edict_t	*touch[ MAX_EDICTS ];
   Entity   *ent;
   int      num;

	path = false;
	for( i = 0; i < NUM_WIDTH_VALUES; i++ )
		{
		maxheight[ i ] = 0;
      }

   width = NUM_WIDTH_VALUES * WIDTH_STEP * 0.5;
   min = Vector( -width, -width, 0 );
   max = Vector( width, width, MAX_HEIGHT );
   G_CalcBoundsOfMove( worldorigin, node->worldorigin, min, max, &bmin, &bmax );

  	num = gi.BoxEdicts( bmin.vec3(), bmax.vec3(), touch, MAX_EDICTS, AREA_SOLID );
   for( i = 0; i < num; i++ )
      {
		ent = touch[ i ]->entity;
		if ( ent && ent->isSubclassOf( Door ) )
         {
         ent->unlink();
         }
      }

	for( i = 0; i < NUM_WIDTH_VALUES; i++ )
		{
		width = ( i + 1 ) * WIDTH_STEP * 0.5;

		min.x = min.y = -width;
      max.x = max.y = width;

      // Perform a binary search to find the height of the path.  Neat, eh? :)
      bottom = 0;
      top = MAX_HEIGHT;
      while( top >= bottom )
         {
         height = ( ( bottom + top + 3 ) >> 1 ) & ~0x3;
         if ( !height )
            {
            break;
            }

			max.z = ( float )height;
			if ( !CheckPath( node, min, max, fulltest ) )
            {
            top = height - 4;
            }
         else
            {
            bottom = height + 4;
      	   maxheight[ i ] = height;
            }
         }

      if ( !maxheight[ i ] )
         {
         // If no paths were available at this width, don't allow any wider paths.
         // CheckPath uses TestMove which may allow wide paths to succeed when they
         // shouldn't since it may place the lower node above obstacles that actors
         // can't step over.  Since any path that's wide enough for large boxes must
         // also allow thinner boxes to go through, this check avoids the hole in
         // TestMove's functioning.
         break;
         }

      path = true;
      }

   // Restore the doors
   for( i = 0; i < num; i++ )
      {
		ent = touch[ i ]->entity;
		if ( ent && ent->isSubclassOf( Door ) )
         {
         ent->link();
         }
      }

	return path;
	}

EXPORT_FROM_DLL qboolean PathNode::LadderTo
	(
	PathNode *node,
	byte maxheight[ NUM_WIDTH_VALUES ]
	)

	{
	int i;
	int j;
	int m;
	int width;
	Vector min;
	Vector max;
	qboolean path;

	trace_t trace;
	
	if ( !( nodeflags & AI_LADDER ) || !( node->nodeflags & AI_LADDER ) )
		{
		return false;
		}

	if ( ( worldorigin.x != node->worldorigin.x ) || ( worldorigin.y != node->worldorigin.y ) )
		{
		return false;
		}

	path = false;

	for( i = 0; i < NUM_WIDTH_VALUES; i++ )
		{
		width = ( i + 1 ) * WIDTH_STEP * 0.5;
		min = Vector( -width, -width, 12 );
		max = Vector( width, width, 40 );

		trace = G_Trace( worldorigin, min, max, node->worldorigin, NULL, MASK_PATHSOLID, "PathNode::LadderTo 1" );
		if ( ( trace.fraction != 1 ) || trace.startsolid )
			{
			maxheight[ i ] = 0;
			continue;
			}

		path = true;

		m = 40;
		for( j = 48; j < MAX_HEIGHT; j+= 8 )
			{
			max.z = j;
			trace = G_Trace( worldorigin, min, max, node->worldorigin, NULL, MASK_PATHSOLID, "PathNode::LadderTo 2" );
			if ( ( trace.fraction != 1 ) || trace.startsolid )
				{
				break;
				}
			
			m = j;
			}

		maxheight[ i ] = m;
		}

	return path;
	}

EXPORT_FROM_DLL qboolean PathNode::ConnectedTo
	(
	PathNode *node
	)

	{
	int i;

	for( i = 0; i < numChildren; i++ )
		{
		if ( Child[ i ].node == node->nodenum )
			{
			return true;
			}
		}

	return false;
	}

EXPORT_FROM_DLL void PathNode::ConnectTo
	(
	PathNode *node,
	byte maxheight[ NUM_WIDTH_VALUES ],
	float cost,
	Door *door
	)

	{
	int i;

	if ( ( numChildren < NUM_PATHSPERNODE ) && ( node != this ) )
		{
		Child[ numChildren ].node = node->nodenum;
		for( i = 0; i < NUM_WIDTH_VALUES; i++ )
			{
			Child[ numChildren ].maxheight[ i ] = maxheight[ i ];
			}
		Child[ numChildren ].moveCost = ( int )cost;
		Child[ numChildren ].door = door ? door->entnum : 0;
		numChildren++;
		}
	else
		{
		warning( "ConnectTo", "Child overflow" );
		}
	}

EXPORT_FROM_DLL void PathNode::ConnectTo
	(
	PathNode *node,
	byte maxheight[ NUM_WIDTH_VALUES ]
	)

	{
	Vector delta;
	Door *door;

	door = CheckDoor( node->worldorigin );
	delta = node->worldorigin - worldorigin;
	ConnectTo( node, maxheight, delta.length(), door );
	}

EXPORT_FROM_DLL void PathNode::Disconnect
	(
	PathNode *node
	)

	{
	int i;

	for( i = 0; i < numChildren; i++ )
		{
		if ( Child[ i ].node == node->nodenum )
			{
			break;
			}
		}

	// Should never happen, but let it slide after release
	assert( i != numChildren );
	if ( i == numChildren )
		{
		return;
		}

	numChildren--;

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

EXPORT_FROM_DLL void PathNode::FindChildren
	(
	Event *ev
	)