codemp/game/g_navnew.c File Reference

#include "b_local.h"
#include "g_nav.h"

Go to the source code of this file.

Functions

qboolean NAV_CheckAhead (gentity_t *self, vec3_t end, trace_t *trace, int clipmask)
qboolean NAV_TestForBlocked (gentity_t *self, gentity_t *goal, gentity_t *blocker, float distance, int *flags)
void G_Line (vec3_t start, vec3_t end, vec3_t color, float alpha)
void G_Cube (vec3_t mins, vec3_t maxs, vec3_t color, float alpha)
void G_CubeOutline (vec3_t mins, vec3_t maxs, int time, unsigned int color, float alpha)
void G_DrawEdge (vec3_t start, vec3_t end, int type)
void G_DrawNode (vec3_t origin, int type)
void G_DrawCombatPoint (vec3_t origin, int type)
void TAG_ShowTags (int flags)
qboolean NAV_CheckNodeFailedForEnt (gentity_t *ent, int nodeNum)
void NPC_ClearBlocked (gentity_t *self)
void NPC_SetBlocked (gentity_t *self, gentity_t *blocker)
int NAVNEW_ClearPathBetweenPoints (vec3_t start, vec3_t end, vec3_t mins, vec3_t maxs, int ignore, int clipmask)
void NAVNEW_PushBlocker (gentity_t *self, gentity_t *blocker, vec3_t right, qboolean setBlockedInfo)
qboolean NAVNEW_DanceWithBlocker (gentity_t *self, gentity_t *blocker, vec3_t movedir, vec3_t right)
qboolean NAVNEW_SidestepBlocker (gentity_t *self, gentity_t *blocker, vec3_t blocked_dir, float blocked_dist, vec3_t movedir, vec3_t right)
qboolean NAVNEW_Bypass (gentity_t *self, gentity_t *blocker, vec3_t blocked_dir, float blocked_dist, vec3_t movedir, qboolean setBlockedInfo)
qboolean NAVNEW_CheckDoubleBlock (gentity_t *self, gentity_t *blocker, vec3_t blocked_dir)
void CalcTeamDoorCenter (gentity_t *ent, vec3_t center)
qboolean NAVNEW_ResolveEntityCollision (gentity_t *self, gentity_t *blocker, vec3_t movedir, vec3_t pathDir, qboolean setBlockedInfo)
qboolean NAVNEW_AvoidCollision (gentity_t *self, gentity_t *goal, navInfo_t *info, qboolean setBlockedInfo, int blockedMovesLimit)
qboolean NAVNEW_TestNodeConnectionBlocked (int wp1, int wp2, gentity_t *ignoreEnt, int goalEntNum, qboolean checkWorld, qboolean checkEnts)
int NAVNEW_MoveToGoal (gentity_t *self, navInfo_t *info)


Function Documentation

void CalcTeamDoorCenter gentity_t ent,
vec3_t  center
 

Definition at line 501 of file g_mover.c.

References gentity_t, entityShared_t::maxs, entityShared_t::mins, gentity_s::r, gentity_s::teamchain, vec3_t, VectorAdd, and VectorScale.

Referenced by NAVNEW_ResolveEntityCollision(), Reached_BinaryMover(), and Use_BinaryMover_Go().

00502 {
00503         vec3_t          slavecenter;
00504         gentity_t       *slave;
00505 
00506         //Start with our center
00507         VectorAdd(ent->r.mins, ent->r.maxs, center);
00508         VectorScale(center, 0.5, center);
00509         for ( slave = ent->teamchain ; slave ; slave = slave->teamchain ) 
00510         {
00511                 //Find slave's center
00512                 VectorAdd(slave->r.mins, slave->r.maxs, slavecenter);
00513                 VectorScale(slavecenter, 0.5, slavecenter);
00514                 //Add that to our own, find middle
00515                 VectorAdd(center, slavecenter, center);
00516                 VectorScale(center, 0.5, center);
00517         }
00518 }

void G_Cube vec3_t  mins,
vec3_t  maxs,
vec3_t  color,
float  alpha
 

Definition at line 16 of file g_nav.c.

00017 {
00018 
00019 }

void G_CubeOutline vec3_t  mins,
vec3_t  maxs,
int  time,
unsigned int  color,
float  alpha
 

Definition at line 21 of file g_nav.c.

References vec3_t.

Referenced by NAV_ClearPathToPoint().

00022 {
00023 
00024 }

void G_DrawCombatPoint vec3_t  origin,
int  type
 

Definition at line 36 of file g_nav.c.

References vec3_t.

Referenced by NAV_ShowDebugInfo().

00037 {
00038 
00039 }

void G_DrawEdge vec3_t  start,
vec3_t  end,
int  type
 

Definition at line 26 of file g_nav.c.

References vec3_t.

Referenced by NAV_AvoidCollision(), NAV_Bypass(), NAV_ClearPathToPoint(), NAV_Steer(), NAVNEW_AvoidCollision(), NAVNEW_Bypass(), and NAVNEW_MoveToGoal().

00027 {
00028 
00029 }

void G_DrawNode vec3_t  origin,
int  type
 

Definition at line 31 of file g_nav.c.

References vec3_t.

Referenced by NAV_MoveToGoal(), NAV_ShowDebugInfo(), and NAVNEW_MoveToGoal().

00032 {
00033 
00034 }

void G_Line vec3_t  start,
vec3_t  end,
vec3_t  color,
float  alpha
 

Definition at line 11 of file g_nav.c.

00012 {
00013 
00014 }

qboolean NAV_CheckAhead gentity_t self,
vec3_t  end,
trace_t trace,
int  clipmask
 

Referenced by NAV_AvoidCollision(), NAV_Bypass(), NAV_MoveToGoal(), NAV_Steer(), NAVNEW_AvoidCollision(), NPC_BSJedi_FollowLeader(), and NPC_ClearPathToGoal().

qboolean NAV_CheckNodeFailedForEnt gentity_t ent,
int  nodeNum
 

Definition at line 15 of file g_navnew.c.

References gentity_s::failedWaypoints, gentity_t, MAX_FAILED_NODES, qboolean, qfalse, and qtrue.

Referenced by vmMain().

00016 {
00017         int j;
00018 
00019         //FIXME: must be a better way to do this
00020         for ( j = 0; j < MAX_FAILED_NODES; j++ )
00021         {
00022                 if ( ent->failedWaypoints[j] == nodeNum+1 )//+1 because 0 is a valid nodeNum, but also the default
00023                 {//we failed against this node
00024                         return qtrue;
00025                 }
00026         }
00027         return qfalse;
00028 }

qboolean NAV_TestForBlocked gentity_t self,
gentity_t goal,
gentity_t blocker,
float  distance,
int *  flags
 

Definition at line 873 of file g_nav.c.

References entityShared_t::currentOrigin, ET_ITEM, entityState_s::eType, gentity_t, entityShared_t::maxs, MIN_STOP_DIST, entityShared_t::mins, NAV_HitNavGoal(), NIF_BLOCKED, NPC_Blocked(), NPC_FaceEntity(), NULL, qboolean, qfalse, qtrue, gentity_s::r, and gentity_s::s.

Referenced by NAV_AvoidCollision(), and NAVNEW_AvoidCollision().

00874 {
00875         if ( goal == NULL )
00876                 return qfalse;
00877 
00878         if ( blocker->s.eType == ET_ITEM )
00879                 return qfalse;
00880 
00881         if ( NAV_HitNavGoal( blocker->r.currentOrigin, blocker->r.mins, blocker->r.maxs, goal->r.currentOrigin, 12, qfalse ) )
00882         {
00883                 *flags |= NIF_BLOCKED;
00884 
00885                 if ( distance <= MIN_STOP_DIST )
00886                 {
00887                         NPC_Blocked( self, blocker );
00888                         NPC_FaceEntity( blocker, qtrue );
00889                         return qtrue;
00890                 }
00891         }
00892 
00893         return qfalse;
00894 }

qboolean NAVNEW_AvoidCollision gentity_t self,
gentity_t goal,
navInfo_t info,
qboolean  setBlockedInfo,
int  blockedMovesLimit
 

Definition at line 442 of file g_navnew.c.

References navInfo_s::blocker, gNPC_t::consecutiveBlockedMoves, CONTENTS_BODY, entityShared_t::currentOrigin, d_patched, navInfo_s::direction, navInfo_s::distance, EDGE_MOVEDIR, trace_t::entityNum, navInfo_s::flags, G_DrawEdge(), g_entities, gentity_t, vmCvar_t::integer, MAX_COLL_AVOID_DIST, NAV_CheckAhead(), NAV_TestForBlocked(), NAVDEBUG_showCollision, navInfo_t, NAVNEW_ResolveEntityCollision(), NIF_COLLISION, gentity_s::NPC, NPC_SetBlocked(), navInfo_s::pathDirection, qboolean, qfalse, qtrue, gentity_s::r, navInfo_s::trace, vec3_t, VectorCopy, and VectorMA.

Referenced by NAVNEW_MoveToGoal(), and NPC_GetMoveDirectionAltRoute().

00443 {
00444         vec3_t  movedir;
00445         vec3_t  movepos;
00446 
00447         //Cap our distance
00448         if ( info->distance > MAX_COLL_AVOID_DIST )
00449         {
00450                 info->distance = MAX_COLL_AVOID_DIST;
00451         }
00452 
00453         //Get an end position
00454         VectorMA( self->r.currentOrigin, info->distance, info->direction, movepos );
00455         VectorCopy( info->direction, movedir );
00456 
00457         //Now test against entities
00458         if ( NAV_CheckAhead( self, movepos, &info->trace, CONTENTS_BODY ) == qfalse )
00459         {
00460                 //Get the blocker
00461                 info->blocker = &g_entities[ info->trace.entityNum ];
00462                 info->flags |= NIF_COLLISION;
00463 
00464                 //Ok to hit our goal entity
00465                 if ( goal == info->blocker )
00466                         return qtrue;
00467 
00468                 if ( setBlockedInfo )
00469                 {
00470                         if ( self->NPC->consecutiveBlockedMoves > blockedMovesLimit  )
00471                         {
00472                                 if ( d_patched.integer )
00473                                 {//use patch-style navigation
00474                                         self->NPC->consecutiveBlockedMoves++;
00475                                 }
00476                                 NPC_SetBlocked( self, info->blocker );
00477                                 return qfalse;
00478                         }
00479                         self->NPC->consecutiveBlockedMoves++;
00480                 }
00481                 //See if we're moving along with them
00482                 //if ( NAVNEW_TrueCollision( self, info->blocker, movedir, info->direction ) == qfalse )
00483                 //      return qtrue;
00484 
00485                 //Test for blocking by standing on goal
00486                 if ( NAV_TestForBlocked( self, goal, info->blocker, info->distance, &info->flags ) == qtrue )
00487                         return qfalse;
00488 
00489                 //If the above function said we're blocked, don't do the extra checks
00490                 /*
00491                 if ( info->flags & NIF_BLOCKED )
00492                         return qtrue;
00493                 */
00494 
00495                 //See if we can get that entity to move out of our way
00496                 if ( NAVNEW_ResolveEntityCollision( self, info->blocker, movedir, info->pathDirection, setBlockedInfo ) == qfalse )
00497                         return qfalse;
00498 
00499                 VectorCopy( movedir, info->direction );
00500                 
00501                 return qtrue;
00502         }
00503         else
00504         {
00505                 if ( setBlockedInfo )
00506                 {
00507                         self->NPC->consecutiveBlockedMoves = 0;
00508                 }
00509         }
00510 
00511         //Our path is clear, just move there
00512         if ( NAVDEBUG_showCollision )
00513         {
00514                 G_DrawEdge( self->r.currentOrigin, movepos, EDGE_MOVEDIR );
00515         }
00516 
00517         return qtrue;
00518 }

qboolean NAVNEW_Bypass gentity_t self,
gentity_t blocker,
vec3_t  blocked_dir,
float  blocked_dist,
vec3_t  movedir,
qboolean  setBlockedInfo
 

Definition at line 347 of file g_navnew.c.

References AngleVectors(), entityShared_t::currentOrigin, EDGE_NORMAL, G_DrawEdge(), gentity_t, NAVDEBUG_showCollision, NAVNEW_DanceWithBlocker(), NAVNEW_PushBlocker(), NAVNEW_SidestepBlocker(), NULL, qboolean, qfalse, qtrue, gentity_s::r, vec3_t, and vectoangles().

Referenced by NAVNEW_ResolveEntityCollision().

00348 {
00349         vec3_t  moveangles, right;
00350 
00351         //Draw debug info if requested
00352         if ( NAVDEBUG_showCollision )
00353         {
00354                 G_DrawEdge( self->r.currentOrigin, blocker->r.currentOrigin, EDGE_NORMAL );
00355         }
00356 
00357         vectoangles( movedir, moveangles );
00358         moveangles[2] = 0;
00359         AngleVectors( moveangles, NULL, right, NULL );
00360 
00361         //Check to see what dir the other guy is moving in (if any) and pick the opposite dir
00362         if ( NAVNEW_DanceWithBlocker( self, blocker, movedir, right ) )
00363         {
00364                 return qtrue;
00365         }
00366 
00367         //Okay, so he's not moving to my side, see which side of him is most clear
00368         if ( NAVNEW_SidestepBlocker( self, blocker, blocked_dir, blocked_dist, movedir, right ) )
00369         {
00370                 return qtrue;
00371         }
00372 
00373         //Neither side is clear, tell him to step aside
00374         NAVNEW_PushBlocker( self, blocker, right, setBlockedInfo );
00375 
00376         return qfalse;
00377 }

qboolean NAVNEW_CheckDoubleBlock gentity_t self,
gentity_t blocker,
vec3_t  blocked_dir
 

Definition at line 384 of file g_navnew.c.

References gNPC_t::blockingEntNum, gentity_t, gentity_s::NPC, entityState_s::number, qboolean, qfalse, qtrue, gentity_s::s, and vec3_t.

Referenced by NAVNEW_ResolveEntityCollision().

00385 {
00386         //Stop double waiting
00387         if ( ( blocker->NPC ) && ( blocker->NPC->blockingEntNum == self->s.number ) )
00388                 return qtrue;
00389 
00390         return qfalse;
00391 }

int NAVNEW_ClearPathBetweenPoints vec3_t  start,
vec3_t  end,
vec3_t  mins,
vec3_t  maxs,
int  ignore,
int  clipmask
 

Definition at line 58 of file g_navnew.c.

References trace_t::entityNum, ENTITYNUM_WORLD, trap_InPVS(), trap_Trace(), and vec3_t.

Referenced by vmMain().

00059 {
00060         trace_t trace;
00061 
00062         //Test if they're even conceivably close to one another
00063         if ( !trap_InPVS( start, end ) )
00064         {
00065                 return ENTITYNUM_WORLD;
00066         }
00067 
00068         trap_Trace( &trace, start, mins, maxs, end, ignore, clipmask );
00069 
00070         //if( ( ( trace.startsolid == false ) && ( trace.allsolid == false ) ) && ( trace.fraction < 1.0f ) )
00071         //{//FIXME: check for drops?
00072         //FIXME: if startsolid or allsolid, then the path isn't clear... but returning ENTITYNUM_NONE indicates to CheckFailedEdge that is is clear...?
00073                 return trace.entityNum;
00074         //}
00075 
00076         //return ENTITYNUM_NONE;
00077 }

qboolean NAVNEW_DanceWithBlocker gentity_t self,
gentity_t blocker,
vec3_t  movedir,
vec3_t  right
 

Definition at line 178 of file g_navnew.c.

References gentity_s::client, DotProduct, gentity_t, gclient_s::ps, qboolean, qfalse, qtrue, vec3_origin, vec3_t, VectorAdd, VectorCopy, VectorMA, VectorNormalize(), and playerState_s::velocity.

Referenced by NAVNEW_Bypass().

00179 {//sees if blocker has any lateral movement
00180         if ( blocker->client && !VectorCompare( blocker->client->ps.velocity, vec3_origin ) )
00181         {
00182                 vec3_t blocker_movedir;
00183                 float dot;
00184 
00185                 VectorCopy( blocker->client->ps.velocity, blocker_movedir );
00186                 blocker_movedir[2] = 0;//cancel any vertical motion
00187                 dot = DotProduct( blocker_movedir, right );
00188                 if ( dot > 50.0f )
00189                 {//he's moving to the right of me at a relatively good speed
00190                         //go to my left
00191                         VectorMA( movedir, -1, right, movedir );
00192                         VectorNormalize( movedir );
00193                         return qtrue;
00194                 }
00195                 else if ( dot > -50.0f )
00196                 {//he's moving to the left of me at a relatively good speed
00197                         //go to my right
00198                         VectorAdd( right, movedir, movedir );
00199                         VectorNormalize( movedir );
00200                         return qtrue;
00201                 }
00202                 /*
00203                 vec3_t  block_pos;
00204                 trace_t tr;
00205                 VectorScale( blocker_movedir, -1, blocker_movedir );
00206                 VectorMA( self->r.currentOrigin, blocked_dist, blocker_movedir, block_pos );
00207                 if ( NAVNEW_CheckAhead( self, block_pos, tr, ( self->clipmask & ~CONTENTS_BODY )|CONTENTS_BOTCLIP ) )
00208                 {
00209                         VectorCopy( blocker_movedir, movedir );
00210                         return qtrue;
00211                 }
00212                 */
00213         }
00214         return qfalse;
00215 }

int NAVNEW_MoveToGoal gentity_t self,
navInfo_t info
 

NAVNEW_GetWaypoints( self, qtrue ) )

Definition at line 578 of file g_navnew.c.

References gNPC_t::aiFlags, gNPC_t::blockedDest, entityShared_t::currentOrigin, d_altRoutes, d_patched, navInfo_s::direction, navInfo_s::distance, EDGE_PATH, G_DrawEdge(), G_DrawNode(), gentity_t, gNPC_t::goalEntity, vmCvar_t::integer, level, memcpy(), NAV_TestBestNode(), NAVDEBUG_showEnemyPath, navInfo_t, NAVNEW_AvoidCollision(), NAVNEW_TestNodeConnectionBlocked(), NF_CLEAR_PATH, NODE_GOAL, NODE_NAVGOAL, NODE_NONE, NODE_START, gentity_s::noWaypointTime, gentity_s::NPC, NPC_ClearBlocked(), NPCAI_BLOCKED, NPCInfo, NULL, entityState_s::number, Q_irand(), qboolean, qfalse, qtrue, gentity_s::r, gentity_s::s, gNPC_t::shoveCount, level_locals_t::time, trap_Nav_AddFailedEdge(), trap_Nav_AddFailedNode(), trap_Nav_GetBestNodeAltRoute2(), trap_Nav_GetBestPathBetweenEnts(), trap_Nav_GetNodePosition(), trap_Nav_NodesAreNeighbors(), trap_Nav_ShowPath(), vec3_t, VectorCopy, VectorNormalize(), VectorSubtract, gentity_s::waypoint, WAYPOINT_NONE, entityState_s::weapon, and WP_SABER.

Referenced by NPC_GetMoveDirectionAltRoute().

00579 {
00580         int                     bestNode = WAYPOINT_NONE;
00581         qboolean        foundClearPath = qfalse;
00582         vec3_t          origin;
00583         navInfo_t       tempInfo;
00584         qboolean        setBlockedInfo = qtrue;
00585         qboolean        inBestWP, inGoalWP, goalWPFailed = qfalse;
00586         int                     numTries = 0;
00587 
00588         memcpy( &tempInfo, info, sizeof( tempInfo ) );
00589 
00590         //Must have a goal entity to move there
00591         if( self->NPC->goalEntity == NULL )
00592                 return WAYPOINT_NONE;
00593 
00594         if ( self->waypoint == WAYPOINT_NONE && self->noWaypointTime > level.time )
00595         {//didn't have a valid one in about the past second, don't look again just yet
00596                 return WAYPOINT_NONE;
00597         }
00598         if ( self->NPC->goalEntity->waypoint == WAYPOINT_NONE && self->NPC->goalEntity->noWaypointTime > level.time )
00599         {//didn't have a valid one in about the past second, don't look again just yet
00600                 return WAYPOINT_NONE;
00601         }
00602         if ( self->noWaypointTime > level.time &&
00603                 self->NPC->goalEntity->noWaypointTime > level.time )
00604         {//just use current waypoints
00605                 bestNode = trap_Nav_GetBestNodeAltRoute2( self->waypoint, self->NPC->goalEntity->waypoint, bestNode );
00606         }
00607         //FIXME!!!!: this is making them wiggle back and forth between waypoints
00608         else if ( (bestNode = trap_Nav_GetBestPathBetweenEnts( self, self->NPC->goalEntity, NF_CLEAR_PATH )) == NODE_NONE )
00609         {//one of us didn't have a valid waypoint!
00610                 if ( self->waypoint == NODE_NONE )
00611                 {//don't even try to find one again for a bit
00612                         self->noWaypointTime = level.time + Q_irand( 500, 1500 );
00613                 }
00614                 if ( self->NPC->goalEntity->waypoint == NODE_NONE )
00615                 {//don't even try to find one again for a bit
00616                         self->NPC->goalEntity->noWaypointTime = level.time + Q_irand( 500, 1500 );
00617                 }
00618                 return WAYPOINT_NONE;
00619         }
00620         else
00621         {
00622                 if ( self->NPC->goalEntity->noWaypointTime < level.time )
00623                 {
00624                         self->NPC->goalEntity->noWaypointTime = level.time + Q_irand( 500, 1500 );
00625                 }
00626         }
00627 
00628         while( !foundClearPath )
00629         {
00630                 inBestWP = inGoalWP = qfalse;
00631                 /*
00632                 bestNode = trap_Nav_GetBestNodeAltRoute( self->waypoint, self->NPC->goalEntity->waypoint, bestNode );
00633                 */
00634 
00635                 if ( bestNode == WAYPOINT_NONE )
00636                 {
00637                         goto failed;
00638                 }
00639 
00640                 //see if we can get directly to the next node off bestNode en route to goal's node...
00641                 //NOTE: shouldn't be necc. now
00642                 /*
00643                 int oldBestNode = bestNode;
00644                 bestNode = NAV_TestBestNode( self, self->waypoint, bestNode, qtrue );//, self->NPC->goalEntity->waypoint );// 
00645                 //NOTE: Guaranteed to return something
00646                 if ( bestNode != oldBestNode )
00647                 {//we were blocked somehow
00648                         if ( setBlockedInfo )
00649                         {
00650                                 self->NPC->aiFlags |= NPCAI_BLOCKED;
00651                                 trap_Nav_GetNodePosition( oldBestNode, NPCInfo->blockedDest );
00652                         }
00653                 }
00654                 */
00655                 trap_Nav_GetNodePosition( bestNode, origin );
00656                 /*
00657                 if ( !goalWPFailed )
00658                 {//we haven't already tried to go straight to goal or goal's wp
00659                         if ( bestNode == self->NPC->goalEntity->waypoint )
00660                         {//our bestNode is the goal's wp
00661                                 if ( NAV_HitNavGoal( self->r.currentOrigin, self->r.mins, self->r.maxs, origin, trap_Nav_GetNodeRadius( bestNode ), FlyingCreature( self ) ) )
00662                                 {//we're in the goal's wp
00663                                         inGoalWP = qtrue;
00664                                         //we're in the goalEntity's waypoint already
00665                                         //so head for the goalEntity since we know it's clear of architecture
00666                                         //FIXME: this is pretty stupid because the NPCs try to go straight
00667                                         //              towards their goal before then even try macro_nav...
00668                                         VectorCopy( self->NPC->goalEntity->r.currentOrigin, origin );
00669                                 }
00670                         }
00671                 }
00672                 */
00673                 if ( !inGoalWP )
00674                 {//not heading straight for goal
00675                         if ( bestNode == self->waypoint )
00676                         {//we know it's clear or architecture
00677                                 //trap_Nav_GetNodePosition( self->waypoint, origin );
00678                                 /*
00679                                 if ( NAV_HitNavGoal( self->r.currentOrigin, self->r.mins, self->r.maxs, origin, trap_Nav_GetNodeRadius( bestNode ), FlyingCreature( self ) ) )
00680                                 {//we're in the wp we're heading for already
00681                                         inBestWP = qtrue;
00682                                 }
00683                                 */
00684                         }
00685                         else
00686                         {//heading to an edge off our confirmed clear waypoint... make sure it's clear
00687                                 //it it's not, bestNode will fall back to our waypoint
00688                                 int oldBestNode = bestNode;
00689                                 bestNode = NAV_TestBestNode( self, self->waypoint, bestNode, qtrue );
00690                                 if ( bestNode == self->waypoint )
00691                                 {//we fell back to our waypoint, reset the origin
00692                                         self->NPC->aiFlags |= NPCAI_BLOCKED;
00693                                         trap_Nav_GetNodePosition( oldBestNode, NPCInfo->blockedDest );
00694                                         trap_Nav_GetNodePosition( bestNode, origin );
00695                                 }
00696                         }
00697                 }
00698                 //Com_Printf( "goalwp = %d, mywp = %d, node = %d, origin = %s\n", self->NPC->goalEntity->waypoint, self->waypoint, bestNode, vtos(origin) );
00699 
00700                 memcpy( &tempInfo, info, sizeof( tempInfo ) );
00701                 VectorSubtract( origin, self->r.currentOrigin, tempInfo.direction );
00702                 VectorNormalize( tempInfo.direction );
00703 
00704                 //NOTE: One very important thing NAVNEW_AvoidCollision does is
00705                 //              it actually CHANGES the value of "direction" - it changes it to
00706                 //              whatever dir you need to go in to avoid the obstacle...
00707                 foundClearPath = NAVNEW_AvoidCollision( self, self->NPC->goalEntity, &tempInfo, setBlockedInfo, 5 );
00708 
00709                 if ( !foundClearPath )
00710                 {//blocked by an ent
00711                         if ( inGoalWP )
00712                         {//we were heading straight for the goal, head for the goal's wp instead
00713                                 trap_Nav_GetNodePosition( bestNode, origin );
00714                                 foundClearPath = NAVNEW_AvoidCollision( self, self->NPC->goalEntity, &tempInfo, setBlockedInfo, 5 );
00715                         }
00716                 }
00717 
00718                 if ( foundClearPath )
00719                 {//clear!
00720                         //If we got set to blocked, clear it
00721                         NPC_ClearBlocked( self );
00722                         //Take the dir
00723                         memcpy( info, &tempInfo, sizeof( *info ) );
00724                         if ( self->s.weapon == WP_SABER )
00725                         {//jedi
00726                                 if ( info->direction[2] * info->distance > 64 )
00727                                 {
00728                                         self->NPC->aiFlags |= NPCAI_BLOCKED;
00729                                         VectorCopy( origin, NPCInfo->blockedDest );
00730                                         goto failed;
00731                                 }
00732                         }
00733                 }
00734                 else
00735                 {//blocked by ent!
00736                         if ( setBlockedInfo )
00737                         {
00738                                 self->NPC->aiFlags |= NPCAI_BLOCKED;
00739                                 trap_Nav_GetNodePosition( bestNode, NPCInfo->blockedDest );
00740                         }
00741                         //Only set blocked info first time
00742                         setBlockedInfo = qfalse;
00743 
00744                         if ( inGoalWP )
00745                         {//we headed for our goal and failed and our goal's WP and failed
00746                                 if ( self->waypoint == self->NPC->goalEntity->waypoint )
00747                                 {//our waypoint is our goal's waypoint, nothing we can do
00748                                         //remember that this node is blocked
00749                                         trap_Nav_AddFailedNode( self, self->waypoint );
00750                                         goto failed;
00751                                 }
00752                                 else
00753                                 {//try going for our waypoint this time
00754                                         goalWPFailed = qtrue;
00755                                         inGoalWP = qfalse;
00756                                 }
00757                         }
00758                         else if ( bestNode != self->waypoint )
00759                         {//we headed toward our next waypoint (instead of our waypoint) and failed
00760                                 if ( d_altRoutes.integer )
00761                                 {//mark this edge failed and try our waypoint
00762                                         //NOTE: don't assume there is something blocking the direct path
00763                                         //                      between my waypoint and the bestNode... I could be off
00764                                         //                      that path because of collision avoidance...
00765                                         if ( d_patched.integer &&//use patch-style navigation
00766                                                 ( !trap_Nav_NodesAreNeighbors( self->waypoint, bestNode )
00767                                                 || NAVNEW_TestNodeConnectionBlocked( self->waypoint, bestNode, self, self->NPC->goalEntity->s.number, qfalse, qtrue ) ) )
00768                                         {//the direct path between these 2 nodes is blocked by an ent
00769                                                 trap_Nav_AddFailedEdge( self->s.number, self->waypoint, bestNode );
00770                                         }
00771                                         bestNode = self->waypoint;
00772                                 }
00773                                 else
00774                                 {
00775                                         //we should stop
00776                                         goto failed;
00777                                 }
00778                         }
00779                         else 
00780                         {//we headed for *our* waypoint and couldn't get to it
00781                                 if ( d_altRoutes.integer )
00782                                 {
00783                                         //remember that this node is blocked
00784                                         trap_Nav_AddFailedNode( self, self->waypoint );
00785                                         //Now we should get our waypoints again
00786                                         //FIXME: cache the trace-data for subsequent calls as only the route info would have changed
00787                                         //if ( (bestNode = trap_Nav_GetBestPathBetweenEnts( self, self->NPC->goalEntity, NF_CLEAR_PATH )) == NODE_NONE )//!NAVNEW_GetWaypoints( self, qfalse ) )
00788                                         {//one of our waypoints is WAYPOINT_NONE now
00789                                                 goto failed;
00790                                         }
00791                                 }
00792                                 else
00793                                 {
00794                                         //we should stop
00795                                         goto failed;
00796                                 }
00797                         }
00798 
00799                         if ( ++numTries >= 10 )
00800                         {
00801                                 goto failed;
00802                         }
00803                 }
00804         }
00805 
00806 //finish:
00807         //Draw any debug info, if requested
00808         if ( NAVDEBUG_showEnemyPath )
00809         {
00810                 vec3_t  dest, start;
00811 
00812                 //Get the positions
00813                 trap_Nav_GetNodePosition( self->NPC->goalEntity->waypoint, dest );
00814                 trap_Nav_GetNodePosition( bestNode, start );
00815 
00816                 //Draw the route
00817                 G_DrawNode( start, NODE_START );
00818                 if ( bestNode != self->waypoint )
00819                 {
00820                         vec3_t  wpPos;
00821                         trap_Nav_GetNodePosition( self->waypoint, wpPos );
00822                         G_DrawNode( wpPos, NODE_NAVGOAL );
00823                 }
00824                 G_DrawNode( dest, NODE_GOAL );
00825                 G_DrawEdge( dest, self->NPC->goalEntity->r.currentOrigin, EDGE_PATH );
00826                 G_DrawNode( self->NPC->goalEntity->r.currentOrigin, NODE_GOAL );
00827                 trap_Nav_ShowPath( bestNode, self->NPC->goalEntity->waypoint );
00828         }
00829 
00830         self->NPC->shoveCount = 0;
00831 
00832         //let me keep this waypoint for a while
00833         if ( self->noWaypointTime < level.time )
00834         {
00835                 self->noWaypointTime = level.time + Q_irand( 500, 1500 );
00836         }
00837         return bestNode;
00838 
00839 failed:
00840         //FIXME: What we should really do here is have a list of the goal's and our
00841         //              closest clearpath waypoints, ranked.  If the first set fails, try the rest
00842         //              until there are no alternatives.
00843 
00844         trap_Nav_GetNodePosition( self->waypoint, origin );
00845 
00846         //do this to avoid ping-ponging?
00847         return WAYPOINT_NONE;
00848         /*
00849         //this was causing ping-ponging
00850         if ( DistanceSquared( origin, self->r.currentOrigin ) < 16 )//woo, magic number
00851         {//We're right up on our waypoint, so that won't help, return none
00852                 //Or maybe find the nextbest here?
00853                 return WAYPOINT_NONE;
00854         }
00855         else
00856         {//Try going to our waypoint
00857                 bestNode = self->waypoint;
00858 
00859                 VectorSubtract( origin, self->r.currentOrigin, info.direction );
00860                 VectorNormalize( info.direction );
00861         }
00862         
00863         goto finish;
00864         */
00865 }

void NAVNEW_PushBlocker gentity_t self,
gentity_t blocker,
vec3_t  right,
qboolean  setBlockedInfo
 

Definition at line 84 of file g_navnew.c.

References trace_t::allsolid, gentity_s::client, gentity_s::clipmask, CONTENTS_BOTCLIP, entityShared_t::currentOrigin, d_patched, trace_t::fraction, gentity_t, vmCvar_t::integer, level, entityShared_t::maxs, entityShared_t::mins, gentity_s::NPC, entityState_s::number, gclient_s::pushVec, gclient_s::pushVecTime, gentity_s::r, gentity_s::s, gNPC_t::shoveCount, trace_t::startsolid, STEPSIZE, level_locals_t::time, trap_Trace(), vec3_origin, vec3_t, VectorCopy, VectorMA, and VectorScale.

Referenced by NAVNEW_Bypass().

00085 {//try pushing blocker to one side
00086         trace_t tr;
00087         vec3_t  mins, end;
00088         float   rightSucc, leftSucc, moveamt;
00089 
00090         if ( self->NPC->shoveCount > 30 )
00091         {//don't push for more than 3 seconds;
00092                 return;
00093         }
00094 
00095         if ( !blocker->s.number )
00096         {//never push the player
00097                 return;
00098         }
00099 
00100         if ( !blocker->client || !VectorCompare( blocker->client->pushVec, vec3_origin ) )
00101         {//someone else is pushing him, wait until they give up?
00102                 return;
00103         }
00104 
00105         VectorCopy( blocker->r.mins, mins );
00106         mins[2] += STEPSIZE;
00107 
00108         moveamt = (self->r.maxs[1] + blocker->r.maxs[1]) * 1.2;//yes, magic number
00109 
00110         VectorMA( blocker->r.currentOrigin, -moveamt, right, end );
00111         trap_Trace( &tr, blocker->r.currentOrigin, mins, blocker->r.maxs, end, blocker->s.number, blocker->clipmask|CONTENTS_BOTCLIP);
00112         if ( !tr.startsolid && !tr.allsolid )
00113         {
00114                 leftSucc = tr.fraction;
00115         }
00116         else
00117         {
00118                 leftSucc = 0.0f;
00119         }
00120         
00121         if ( leftSucc >= 1.0f )
00122         {//it's clear, shove him that way
00123                 VectorScale( right, -moveamt, blocker->client->pushVec );
00124                 blocker->client->pushVecTime = level.time + 2000;
00125         }
00126         else
00127         {
00128                 VectorMA( blocker->r.currentOrigin, moveamt, right, end );
00129                 trap_Trace( &tr, blocker->r.currentOrigin, mins, blocker->r.maxs, end, blocker->s.number, blocker->clipmask|CONTENTS_BOTCLIP );
00130                 if ( !tr.startsolid && !tr.allsolid )
00131                 {
00132                         rightSucc = tr.fraction;
00133                 }
00134                 else
00135                 {
00136                         rightSucc = 0.0f;
00137                 }
00138                 
00139                 if ( leftSucc == 0.0f && rightSucc == 0.0f )
00140                 {//both sides failed
00141                         if ( d_patched.integer )
00142                         {//use patch-style navigation
00143                                 blocker->client->pushVecTime = 0;
00144                         }
00145                         return;
00146                 }
00147 
00148                 if ( rightSucc >= 1.0f )
00149                 {//it's clear, shove him that way
00150                         VectorScale( right, moveamt, blocker->client->pushVec );
00151                         blocker->client->pushVecTime = level.time + 2000;
00152                 }
00153                 //if neither are enough, we probably can't get around him, but keep trying
00154                 else if ( leftSucc >= rightSucc )
00155                 {//favor the left, all things being equal
00156                         VectorScale( right, -moveamt, blocker->client->pushVec );
00157                         blocker->client->pushVecTime = level.time + 2000;
00158                 }
00159                 else
00160                 {
00161                         VectorScale( right, moveamt, blocker->client->pushVec );
00162                         blocker->client->pushVecTime = level.time + 2000;
00163                 }
00164         }
00165 
00166         if ( setBlockedInfo )
00167         {
00168                 //we tried pushing
00169                 self->NPC->shoveCount++;
00170         }
00171 }

qboolean NAVNEW_ResolveEntityCollision gentity_t self,
gentity_t blocker,
vec3_t  movedir,
vec3_t  pathDir,
qboolean  setBlockedInfo
 

Definition at line 399 of file g_navnew.c.

References CalcTeamDoorCenter(), gentity_s::classname, entityShared_t::currentOrigin, gentity_t, MIN_DOOR_BLOCK_DIST_SQR, NAVNEW_Bypass(), NAVNEW_CheckDoubleBlock(), NPC_SetBlocked(), Q_stricmp(), qboolean, qfalse, qtrue, gentity_s::r, vec3_t, VectorNormalize(), and VectorSubtract.

Referenced by NAVNEW_AvoidCollision().

00400 {
00401         vec3_t  blocked_dir;
00402         float blocked_dist;
00403 
00404         //Doors are ignored
00405         if ( Q_stricmp( blocker->classname, "func_door" ) == 0 )
00406         {
00407                 vec3_t center;
00408                 CalcTeamDoorCenter ( blocker, center );
00409                 if ( DistanceSquared( self->r.currentOrigin, center ) > MIN_DOOR_BLOCK_DIST_SQR )
00410                         return qtrue;
00411         }
00412 
00413         VectorSubtract( blocker->r.currentOrigin, self->r.currentOrigin, blocked_dir );
00414         blocked_dist = VectorNormalize( blocked_dir );
00415 
00416         //Make sure an actual collision is going to happen
00417 //      if ( NAVNEW_PredictCollision( self, blocker, movedir, blocked_dir ) == qfalse )
00418 //              return qtrue;
00419         
00420         //First, attempt to walk around the blocker or shove him out of the way
00421         if ( NAVNEW_Bypass( self, blocker, blocked_dir, blocked_dist, movedir, setBlockedInfo ) )
00422                 return qtrue;
00423 
00424         //Can't get around him... see if I'm blocking him too... if so, I need to just keep moving?
00425         if ( NAVNEW_CheckDoubleBlock( self, blocker, blocked_dir ) )
00426                 return qtrue;
00427 
00428         if ( setBlockedInfo )
00429         {
00430                 //Complain about it if we can
00431                 NPC_SetBlocked( self, blocker );
00432         }
00433 
00434         return qfalse;
00435 }

qboolean NAVNEW_SidestepBlocker gentity_t self,
gentity_t blocker,
vec3_t  blocked_dir,
float  blocked_dist,
vec3_t  movedir,
vec3_t  right
 

Definition at line 222 of file g_navnew.c.

References trace_t::allsolid, AngleNormalize360(), AngleVectors(), gentity_s::clipmask, CONTENTS_BOTCLIP, entityShared_t::currentOrigin, trace_t::fraction, gentity_t, gNPC_t::lastSideStepSide, level, entityShared_t::maxs, entityShared_t::mins, gentity_s::NPC, NULL, entityState_s::number, qboolean, qfalse, qtrue, gentity_s::r, gentity_s::s, gNPC_t::sideStepHoldTime, sqrt(), trace_t::startsolid, STEPSIZE, level_locals_t::time, trap_Trace(), vec3_t, VectorClear, VectorCopy, VectorMA, vectoyaw(), and YAW.

Referenced by NAVNEW_Bypass().

00223 {//trace to sides of blocker and see if either is clear
00224         trace_t tr;
00225         vec3_t  avoidAngles;
00226         vec3_t  avoidRight_dir, avoidLeft_dir, block_pos, mins;
00227         float   rightSucc, leftSucc, yaw, avoidRadius, arcAngle;
00228 
00229         VectorCopy( self->r.mins, mins );
00230         mins[2] += STEPSIZE;
00231 
00232         //Get the blocked direction
00233         yaw = vectoyaw( blocked_dir );
00234 
00235         //Get the avoid radius
00236         avoidRadius = sqrt( ( blocker->r.maxs[0] * blocker->r.maxs[0] ) + ( blocker->r.maxs[1] * blocker->r.maxs[1] ) ) + 
00237                                                 sqrt( ( self->r.maxs[0] * self->r.maxs[0] ) + ( self->r.maxs[1] * self->r.maxs[1] ) );
00238 
00239         //See if we're inside our avoidance radius
00240         arcAngle = ( blocked_dist <= avoidRadius ) ? 135 : ( ( avoidRadius / blocked_dist ) * 90 );
00241 
00242         /*
00243         float dot = DotProduct( blocked_dir, right );
00244 
00245         //Go right on the first try if that works better
00246         if ( dot < 0.0f )
00247                 arcAngle *= -1;
00248         */
00249 
00250         VectorClear( avoidAngles );
00251 
00252         //need to stop it from ping-ponging, so we have a bit of a debounce time on which side you try
00253         if ( self->NPC->sideStepHoldTime > level.time )
00254         {
00255                 if ( self->NPC->lastSideStepSide == -1 )//left
00256                 {
00257                         arcAngle *= -1;
00258                 }//else right
00259                 avoidAngles[YAW] = AngleNormalize360( yaw + arcAngle );
00260                 AngleVectors( avoidAngles, movedir, NULL, NULL );
00261                 VectorMA( self->r.currentOrigin, blocked_dist, movedir, block_pos );
00262                 trap_Trace( &tr, self->r.currentOrigin, mins, self->r.maxs, block_pos, self->s.number, self->clipmask|CONTENTS_BOTCLIP );
00263                 return (tr.fraction==1.0&&!tr.allsolid&&!tr.startsolid);
00264         }
00265 
00266         //test right
00267         avoidAngles[YAW] = AngleNormalize360( yaw + arcAngle );
00268         AngleVectors( avoidAngles, avoidRight_dir, NULL, NULL );
00269 
00270         VectorMA( self->r.currentOrigin, blocked_dist, avoidRight_dir, block_pos );
00271                 
00272         trap_Trace( &tr, self->r.currentOrigin, mins, self->r.maxs, block_pos, self->s.number, self->clipmask|CONTENTS_BOTCLIP );
00273 
00274         if ( !tr.allsolid && !tr.startsolid )
00275         {
00276                 if ( tr.fraction >= 1.0f )
00277                 {//all clear, go for it (favor the right if both are equal)
00278                         VectorCopy( avoidRight_dir, movedir );
00279                         self->NPC->lastSideStepSide = 1;
00280                         self->NPC->sideStepHoldTime = level.time + 2000;
00281                         return qtrue;
00282                 }
00283                 rightSucc = tr.fraction;
00284         }
00285         else
00286         {
00287                 rightSucc = 0.0f;
00288         }
00289 
00290         //now test left
00291         arcAngle *= -1;
00292 
00293         avoidAngles[YAW] = AngleNormalize360( yaw + arcAngle );
00294         AngleVectors( avoidAngles, avoidLeft_dir, NULL, NULL );
00295 
00296         VectorMA( self->r.currentOrigin, blocked_dist, avoidLeft_dir, block_pos );
00297                 
00298         trap_Trace( &tr, self->r.currentOrigin, mins, self->r.maxs, block_pos, self->s.number, self->clipmask|CONTENTS_BOTCLIP );
00299 
00300         if ( !tr.allsolid && !tr.startsolid )
00301         {
00302                 if ( tr.fraction >= 1.0f )
00303                 {//all clear, go for it (right side would have already succeeded if as good as this)
00304                         VectorCopy( avoidLeft_dir, movedir );
00305                         self->NPC->lastSideStepSide = -1;
00306                         self->NPC->sideStepHoldTime = level.time + 2000;
00307                         return qtrue;
00308                 }
00309                 leftSucc = tr.fraction;
00310         }
00311         else
00312         {
00313                 leftSucc = 0.0f;
00314         }
00315 
00316         if ( leftSucc == 0.0f && rightSucc == 0.0f )
00317         {//both sides failed
00318                 return qfalse;
00319         }
00320 
00321         if ( rightSucc*blocked_dist >= avoidRadius || leftSucc*blocked_dist >= avoidRadius ) 
00322         {//the traces hit something, but got a relatively good distance
00323                 if ( rightSucc >= leftSucc )
00324                 {//favor the right, all things being equal
00325                         VectorCopy( avoidRight_dir, movedir );
00326                         self->NPC->lastSideStepSide = 1;
00327                         self->NPC->sideStepHoldTime = level.time + 2000;
00328                 }
00329                 else
00330                 {
00331                         VectorCopy( avoidLeft_dir, movedir );
00332                         self->NPC->lastSideStepSide = -1;
00333                         self->NPC->sideStepHoldTime = level.time + 2000;
00334                 }
00335                 return qtrue;
00336         }
00337 
00338         //if neither are enough, we probably can't get around him
00339         return qfalse;
00340 }

qboolean NAVNEW_TestNodeConnectionBlocked int  wp1,
int  wp2,
gentity_t ignoreEnt,
int  goalEntNum,
qboolean  checkWorld,
qboolean  checkEnts
 

Definition at line 520 of file g_navnew.c.

References CONTENTS_BODY, CONTENTS_BOTCLIP, CONTENTS_MONSTERCLIP, CONTENTS_SOLID, DEFAULT_MAXS_2, DEFAULT_MINS_2, trace_t::entityNum, ENTITYNUM_NONE, trace_t::fraction, gentity_t, MASK_NPCSOLID, entityShared_t::maxs, entityShared_t::mins, entityState_s::number, playerMaxs, playerMins, qboolean, qfalse, qtrue, gentity_s::r, gentity_s::s, STEPSIZE, trap_Nav_GetNodePosition(), trap_Trace(), vec3_t, VectorCopy, and VectorSet.

Referenced by NAVNEW_MoveToGoal().

00521 {//see if the direct path between 2 nodes is blocked by architecture or an ent
00522         vec3_t  pos1, pos2, mins, maxs;
00523         trace_t trace;
00524         int             clipmask = MASK_NPCSOLID|CONTENTS_BOTCLIP;
00525         int ignoreEntNum;
00526         vec3_t playerMins, playerMaxs;
00527 
00528         if ( !checkWorld && !checkEnts )
00529         {//duh, nothing to trace against
00530                 return qfalse;
00531         }
00532         VectorSet(playerMins, -15, -15, DEFAULT_MINS_2);
00533         VectorSet(playerMaxs, 15, 15, DEFAULT_MAXS_2);
00534 
00535         trap_Nav_GetNodePosition( wp1, pos1 );
00536         trap_Nav_GetNodePosition( wp2, pos2 );
00537 
00538         if ( !checkWorld )
00539         {
00540                 clipmask &= ~(CONTENTS_SOLID|CONTENTS_MONSTERCLIP|CONTENTS_BOTCLIP);
00541         }
00542         if ( !checkEnts )
00543         {
00544                 clipmask &= ~CONTENTS_BODY;
00545         }
00546         if ( ignoreEnt )
00547         {
00548                 VectorCopy( ignoreEnt->r.mins, mins );
00549                 VectorCopy( ignoreEnt->r.maxs, maxs );
00550                 ignoreEntNum = ignoreEnt->s.number;
00551         }
00552         else
00553         {
00554                 VectorCopy( playerMins, mins );
00555                 VectorCopy( playerMaxs, mins );
00556                 ignoreEntNum = ENTITYNUM_NONE;
00557         }
00558         mins[2] += STEPSIZE;
00559         //don't let box get inverted
00560         if ( mins[2] > maxs[2] )
00561         {       
00562                 mins[2] = maxs[2];
00563         }
00564 
00565         trap_Trace( &trace, pos1, mins, maxs, pos2, ignoreEntNum, clipmask );
00566         if ( trace.fraction >= 1.0f || trace.entityNum == goalEntNum )
00567         {//clear or hit goal
00568                 return qfalse;
00569         }
00570         //hit something we weren't supposed to
00571         return qtrue;
00572 }

void NPC_ClearBlocked gentity_t self  ) 
 

Definition at line 34 of file g_navnew.c.

References gNPC_t::blockingEntNum, ENTITYNUM_NONE, gentity_t, gentity_s::NPC, and NULL.

Referenced by NAVNEW_MoveToGoal().

00035 {
00036         if ( self->NPC == NULL )
00037                 return;
00038 
00039         //self->NPC->aiFlags &= ~NPCAI_BLOCKED;
00040         self->NPC->blockingEntNum = ENTITYNUM_NONE;
00041 }

void NPC_SetBlocked gentity_t self,
gentity_t blocker
 

Definition at line 43 of file g_navnew.c.

References gNPC_t::blockedSpeechDebounceTime, gNPC_t::blockingEntNum, gentity_t, level, MIN_BLOCKED_SPEECH_TIME, gentity_s::NPC, NULL, entityState_s::number, random, gentity_s::s, and level_locals_t::time.

Referenced by NAVNEW_AvoidCollision(), and NAVNEW_ResolveEntityCollision().

00044 {
00045         if ( self->NPC == NULL )
00046                 return;
00047 
00048         //self->NPC->aiFlags |= NPCAI_BLOCKED;
00049         self->NPC->blockedSpeechDebounceTime = level.time + MIN_BLOCKED_SPEECH_TIME + ( random() * 4000 );
00050         self->NPC->blockingEntNum = blocker->s.number;
00051 }

void TAG_ShowTags int  flags  ) 
 

Definition at line 41 of file g_nav.c.

Referenced by NAV_ShowDebugInfo().

00042 {
00043 
00044 }