codemp/game/g_navnew.c

Go to the documentation of this file.
00001 #include "b_local.h"
00002 #include "g_nav.h"
00003 
00004 qboolean NAV_CheckAhead( gentity_t *self, vec3_t end, trace_t *trace, int clipmask );
00005 qboolean NAV_TestForBlocked( gentity_t *self, gentity_t *goal, gentity_t *blocker, float distance, int *flags );
00006 
00007 void G_Line( vec3_t start, vec3_t end, vec3_t color, float alpha );
00008 void G_Cube( vec3_t mins, vec3_t maxs, vec3_t color, float alpha );
00009 void G_CubeOutline( vec3_t mins, vec3_t maxs, int time, unsigned int color, float alpha );
00010 void G_DrawEdge( vec3_t start, vec3_t end, int type );
00011 void G_DrawNode( vec3_t origin, int type );
00012 void G_DrawCombatPoint( vec3_t origin, int type );
00013 void TAG_ShowTags( int flags );
00014 
00015 qboolean NAV_CheckNodeFailedForEnt( gentity_t *ent, int nodeNum )
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 }
00029 /*
00030 -------------------------
00031 NPC_UnBlocked
00032 -------------------------
00033 */
00034 void NPC_ClearBlocked( gentity_t *self )
00035 {
00036         if ( self->NPC == NULL )
00037                 return;
00038 
00039         //self->NPC->aiFlags &= ~NPCAI_BLOCKED;
00040         self->NPC->blockingEntNum = ENTITYNUM_NONE;
00041 }
00042 
00043 void NPC_SetBlocked( gentity_t *self, gentity_t *blocker )
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 }
00052 
00053 /*
00054 -------------------------
00055 NAVNEW_ClearPathBetweenPoints
00056 -------------------------
00057 */
00058 int NAVNEW_ClearPathBetweenPoints(vec3_t start, vec3_t end, vec3_t mins, vec3_t maxs, int ignore, int clipmask)
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 }
00078 
00079 /*
00080 -------------------------
00081 NAVNEW_PushBlocker
00082 -------------------------
00083 */
00084 void NAVNEW_PushBlocker( gentity_t *self, gentity_t *blocker, vec3_t right, qboolean setBlockedInfo )
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 }
00172 
00173 /*
00174 -------------------------
00175 NAVNEW_DanceWithBlocker
00176 -------------------------
00177 */
00178 qboolean NAVNEW_DanceWithBlocker( gentity_t *self, gentity_t *blocker, vec3_t movedir, vec3_t right )
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 }
00216 
00217 /*
00218 -------------------------
00219 NAVNEW_SidestepBlocker
00220 -------------------------
00221 */
00222 qboolean NAVNEW_SidestepBlocker( gentity_t *self, gentity_t *blocker, vec3_t blocked_dir, float blocked_dist, vec3_t movedir, vec3_t right )
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 }
00341 
00342 /*
00343 -------------------------
00344 NAVNEW_Bypass
00345 -------------------------
00346 */
00347 qboolean NAVNEW_Bypass( gentity_t *self, gentity_t *blocker, vec3_t blocked_dir, float blocked_dist, vec3_t movedir, qboolean setBlockedInfo ) 
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 }
00378 
00379 /*
00380 -------------------------
00381 NAVNEW_CheckDoubleBlock
00382 -------------------------
00383 */
00384 qboolean NAVNEW_CheckDoubleBlock( gentity_t *self, gentity_t *blocker, vec3_t blocked_dir )
00385 {
00386         //Stop double waiting
00387         if ( ( blocker->NPC ) && ( blocker->NPC->blockingEntNum == self->s.number ) )
00388                 return qtrue;
00389 
00390         return qfalse;
00391 }
00392 
00393 /*
00394 -------------------------
00395 NAVNEW_ResolveEntityCollision
00396 -------------------------
00397 */
00398 extern void CalcTeamDoorCenter ( gentity_t *ent, vec3_t center );
00399 qboolean NAVNEW_ResolveEntityCollision( gentity_t *self, gentity_t *blocker, vec3_t movedir, vec3_t pathDir, qboolean setBlockedInfo )
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 }
00436 
00437 /*
00438 -------------------------
00439 NAVNEW_AvoidCollision
00440 -------------------------
00441 */
00442 qboolean NAVNEW_AvoidCollision( gentity_t *self, gentity_t *goal, navInfo_t *info, qboolean setBlockedInfo, int blockedMovesLimit )
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 }
00519 
00520 qboolean NAVNEW_TestNodeConnectionBlocked( int wp1, int wp2, gentity_t *ignoreEnt, int goalEntNum, qboolean checkWorld, qboolean checkEnts )
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 }
00573 /*
00574 -------------------------
00575 NAVNEW_MoveToGoal
00576 -------------------------
00577 */
00578 int     NAVNEW_MoveToGoal( gentity_t *self, navInfo_t *info )
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 }