towards a better layout of WalkPath() functions

[Pierre-Marie Baty]

Okay, I've managed to write a pottable BotWalkPath() function. It's just in alpha stage but I'd need your comments on its layout (generally speaking, since you're not supposed to know all the details of my code yet). It would be great if we could agree on the best layout for such a function since it is a very common problem for all bots, how to reach their next waypoint efficiently. Also I have a problem. But first things first, here's the function :

void BotWalkPath (player_t *pPlayer)
{
   // this function makes the bot pointed to by pBot follow recursively the series of navlinks
   // that made up the path it wants to follow, until it either reaches its end, or that it finds
   // out that the distance to the next navlink in the list is increasing instead of decreasing,
   // indicating that the path is failing (either the bot falled down a cliff or whatever) ; in
   // this case, the bot is told to start thinking of a new path immediately.
 
   pathmachine_t *pathmachine = &pPlayer->Bot.BotBrain.PathMachine; // quick access to pathmachine
   bot_move_t *BotMove = &pPlayer->Bot.BotMove; // quick access to bot's legs
   int path_index;
   navlink_t *current_navlink;
   Vector v_bot2currentlink;
   float currentlink_distance;
   navlink_t *next_navlink;
   Vector v_bot2nextlink;
   float nextlink_distance;
 
   path_index = BotMove->path_index; // quick access to path index
 
   // first off, has the bot reached its destination ?
   if (path_index == pathmachine->path_count)
   {
	  pPlayer->Bot.bot_task = BOT_TASK_IDLE; // bot doesn't need to follow a path anymore
	  pathmachine->path_count = 0; // reset the path
	  BotMove->path_index = 0;
	  return;
   }
 
   // bot isn't arrived yet
 
   // bot needs to know where it's heading to, that is, it needs to know both the link it's
   // currently reaching, AND the link after this one, in order to know when to skip to it. So
   // get a quick access to current and next navlink (also check for end of path on next navlink)
   current_navlink = pathmachine->path[path_index];
   next_navlink = pathmachine->path[(path_index + 1 < pathmachine->path_count ? path_index + 1 : path_index)];
 
   v_bot2currentlink = current_navlink->v_origin - pPlayer->v_origin; // get vector from bot to current link
   v_bot2nextlink = next_navlink->v_origin - pPlayer->v_origin; // get vector from bot to next link
 
   currentlink_distance = v_bot2currentlink.Length (); // get distance from bot to next link
   nextlink_distance = v_bot2nextlink.Length (); // get distance from bot to link after next link
 
   // does the current navlink involve a ladder ?
   if (current_navlink->reachability & REACHABILITY_LADDER)
   {
	  // has the bot NOT identified the ladder yet ?
	  if (FNullEnt (pPlayer->Bot.pTransportEntity))
		 BotFindTransportEntity (pPlayer, REACHABILITY_LADDER); // if so, find the involved ladder
   }
 
   // does the link involve a fall ?
   if (current_navlink->reachability & REACHABILITY_FALLEDGE)
   {
	  // a priori, nothing to do but to let ourselves fall down the pit...
   }
 
   // does the link involve an elevator ?
   if (current_navlink->reachability & REACHABILITY_ELEVATOR)
   {
	  // has the bot NOT identified the elevator yet ?
	  if (FNullEnt (pPlayer->Bot.pTransportEntity))
		 BotFindTransportEntity (pPlayer, REACHABILITY_ELEVATOR); // if so, find the involved elevator
	  // TODO: check for a button
	  // TODO: wait for the elevator to stop before getting on it
	  // TODO: wait for the elevator to stop before leaving it
   }
 
   // does the link involve a bobbing platform ?
   if (current_navlink->reachability & REACHABILITY_PLATFORM)
   {
	  // has the bot NOT identified the platform yet ?
	  if (FNullEnt (pPlayer->Bot.pTransportEntity))
		 BotFindTransportEntity (pPlayer, REACHABILITY_PLATFORM); // if so, find the involved platform
	  // TODO: check for a button
	  // TODO: wait for the platform to be close enough to us before getting on it
	  // TODO: wait to be close enough to destination before leaving the platform
   }
 
   // does the link involve a conveyor ribbon ?
   if (current_navlink->reachability & REACHABILITY_CONVEYOR)
   {
	  // has the bot NOT identified the conveyor yet ?
	  if (FNullEnt (pPlayer->Bot.pTransportEntity))
		  BotFindTransportEntity (pPlayer, REACHABILITY_CONVEYOR); // if so, find the involved conveyor
	  // TODO: check for a button
	  // TODO: wait to be close enough to destination before leaving the conveyor
   }
 
   // does the link involve a train ?
   if (current_navlink->reachability & REACHABILITY_TRAIN)
   {
	  // has the bot NOT identified the train yet ?
	  if (FNullEnt (pPlayer->Bot.pTransportEntity))
		 BotFindTransportEntity (pPlayer, REACHABILITY_TRAIN); // if so, find the involved train
	  // TODO: check for the presence of the train
	  // TODO: wait for the train to be close enough to us before getting on it
	  // TODO: wait to be close enough to destination before leaving the train
   }
 
   // if time to, update the bot's distance to its next link
   if (BotMove->nextlink_distance_updatetime < server.time)
   {
	  BotMove->nextlink_distance = currentlink_distance; // update distance
	  BotMove->nextlink_distance_updatetime = server.time + 1.0; // next update in 1s
   }
 
   // is the path failing ?
/*   if ((currentlink_distance > BotMove->nextlink_distance + 16) || pPlayer->Bot.is_stuck)
   {
	  if (ListenserverIsWatching (pPlayer))
		 printf ("PATH FAILED!!! CAN'T WALK PATH!!!\n");
 
	  current_navlink->reachability |= REACHABILITY_BAD; // then destroy this link, it's a bad one...
	  pathmachine->path_count = 0; // reset the path
	  BotMove->path_index = 0;
	  BotMove->nextlink_distance_updatetime = 0;
	  pPlayer->Bot.bot_task = BOT_TASK_FINDPATH; // tell the bot to figure out a new path
	  return;
   }*/
 
   // if we are watching this bot, display the path it is following
   if (ListenserverIsWatching (pPlayer))
   {
	  //UTIL_DrawPath (pListenserverPlayer, pathmachine, 600);
	  UTIL_DrawLine (pListenserverPlayer, pPlayer->v_origin, current_navlink->v_origin, 1, 255, 255, 255);
	  UTIL_DrawLine (pListenserverPlayer, current_navlink->v_origin, next_navlink->v_origin, 1, 0, 0, 255);
   }
 
   // walk the path, Neo.
   BotMoveTowardsPosition (pPlayer, current_navlink->v_origin);
 
   // avoid any obstacles while we're at it
   BotAvoidObstacles (pPlayer);
 
   // can the bot look around while wandering ? (don't do so for ladders...)
   if (!(current_navlink->reachability & REACHABILITY_LADDER))
	  BotLookAround (pPlayer); // yes, look around
   else
	  BotSetIdealAngles (pPlayer, UTIL_VecToAngles (v_bot2currentlink)); // should rather look at destination
 
   // has the bot reached its current link OR has the bot bypassed it already ?
   if (((current_navlink->v_origin - pPlayer->v_origin).Length () < 60)
	   || (AngleOfVectors (v_bot2currentlink, v_bot2nextlink) > 60))
	  BotMove->path_index++; // skip to the next one in the list
 
	return; // enough for this frame
}

To me the best layout of WalkPath() functions are:
1°) identify the link
2°) identify extra entities that the bot can use to reach the next link
3°) decide of the action to take regarding to these
4°) if not explicitly told not to, walk towards the next waypoint

Commentaries ?

Note that in BotMoveTowardsPosition(), only forward/strafe keys are involved. The bot does NOT make its body angle face the waypoint while the view angles are looking elsewhere (it's unnatural). Which brings me to the problem: I need a reliable way to tell that the path is failing. How do you guys do for detecting that your bot's next waypoint has become unreachable ?

I think the simplest way would be for the bot to compare its current x,y,x location to its x,y,x location the last time the function was called.

If (ABS(CurrX-PrevX) + ABS(CurrY-PrevY) + ABS(CurrZ-PrevZ) < MinimumWalkSpeed) And ImTryingToMove Then
OhCrapImStuck
Else
CoolImNotStuck
EndIF

ABS()=absolute value function

I'm a VB coder and don't speak C/C++ very well. But that seems to me to be the simplest most reliable way to solve the problem. BTW, PrevX, PrevY, and PrevZ should be declared static and updated with the bot's current x,y,z coordinates as the last step before the function exits. If testing to see if jumping unsticks the bot, do the above, but without the Z coordinate (assuming jumping causes the Z coordinate to change).

[botmeister]

Based on the bots speed and the distance to the next way point, you could calculate how long it should take in the worst case to reach the next point (in time units or frame counts). If the worst case time elapses (assuming there's no battles inbetween, or changes in speed) then you can assume the bot is not succeeding.

Another thing you could do by itself, or in combination with the first method, is calculate the distance from where the current bot position is to the next navpoint position. You could then check to see if the distance is shrinking over time (or over frames) or not. Using this method, you will have the ability to decide if the path is making fast progress, slow progress, negative progress, or zero progress.

[Pierre-Marie Baty]

@A$$A$$IN: this is indeed the simplest method, however it is unpractical because it won't work on a certain number of case. For example, if the bot falls down the Aztec bridge, the bot will still be in movement but the path will have failed. Also, if a path between 3 nodes make less than a 90 degree angle (circling around a wall, for example), the bot will reach the waypoint then face back and start walking the other side, and this might trigger your stuck check algorithm. One more common situation, is when the bot is already walking, then is told to walk another path that starts right behind it ; the bot's speed will decrease, stop, and then increase backwards and that doesn't mean the bot is stuck. I'm long experienced in tweaking stuck checking algorithms like this one, and unfortunately I never could reach any acceptable result.

@botmeister: your first idea looks promising! I hadn't thought about this one yet. I'll try it. Your second idea though is the traditional way to go for such algorithms when the bot faces its next waypoint perfectly, and thus is ASSURED to reach it. However mine don't, they use the strafe keys instead, and this causes problems when they come closer to the waypoint as the distance can really vary much, decreasing then increasing several times in a second, but it doesn't mean the bot is stuck though.

[botmeister]

they use the strafe keys instead, and this causes problems when they come closer to the waypoint as the distance can really vary much, decreasing then increasing several times in a second, but it doesn't mean the bot is stuck though.

If I understand you correctly, your bots will "zig zag" from side to side as they approach the next navpoint? If so, they must still make progress towards the navpoint over multiple frames or they will never reach it.

I am not suggesting that you abort as soon as you detect the bot's distance is getting larger, but that you abort only if the bot is not making adequate progress over a period of time. But how to choose the period of time?

I think you could estimate the maximum time to reach the navpoint (ETA) then check over time, relative to the ETA, to see if the bot is actually closing in on the navpoint or not. You could for example, choose a period of time that's 1/2 of the ETA, but I suspect it will be more complicated than that. If the bot is not closing in quickly enough, then you could abort before the ETA expires, thus saving time on an unreachable navpoint.