Understanding Waypointing

He@dShot · **Understanding Waypointing -** 06-09-2008

Can someone explain to me how the bot's waypointing system works ? (HPB bots) ???

Cheeseh · **Re: Understanding Waypointing -** 08-09-2008

It depends what part of the waypointing you need to know. e.g.

How waypoints are stored in the game
How waypoints are stored on a waypoint file
How waypoints are added/deleted from the waypoints array
How paths are generated for each waypoint
How to find the best waypoint path
How bots navigate between waypoints
How bots move towards its "current waypoint"

Or all of them

I had a lot of trouble with waypoints when I started making bots up, I specifically had a hard time figuring out how a bot goes from one waypoint to another for some reason!

How waypoints are stored in the game

All waypoints are stored in a large array e.g. call it "waypoints".

Each waypoints has co-ordinates on the map (x,y,z) (Vector type).

They also have Flags. The flags are a bitmask of additional information that is useful for a bot to navigate properly (Or if it is a special waypoint), for example a crouch waypoint, or a ladder waypoint, or a sniper waypoint. There are also special waypoints in HPB Bot called 'aiming' waypoints, useful for sniper waypoints and sentry waypoints to show the direction of a nearby waypoint. There is another special flag called DELETED that tells the bots that the waypoint in the array is invalid and can be overwritten by a new waypoint.

Each waypoint also has a list of other waypoints that can be reached from the current waypoint. This is used for path finding.

The waypoint code structure looks something like:

Code:

// Example values
#define FL_CROUCH 1
#define FL_LADDER 2
#define FL_AIMING 4
#define FL_SNIPER 8
#define FL_SENTRY 16
#define FL_DELETE 32

#define MAX_WAYPOINTS 1024

#define MAX_PATH 8

int num_waypoints = 0;

typedef struct
{
  Vector origin;
  int flags;
  int path[MAX_PATH]; // Waypoint paths
  short num_path; // number of waypoint paths
}waypoint_t;

waypoint_t waypoints[MAX_WAYPOINTS];

bool waypointHasFlag ( int Index, int Flag )
{
  return (waypoints[Index] & Flag) == Flag;
}

How waypoints are stored on a waypoint file

Waypoints are stored in a file in binary format. First a waypoint header is stored in the file.

Code:

typedef struct
{
   int waypoint_version;
   char map[64];
   char bot[32];
   int num_waypoints;
}waypoint_header;

bool loadwaypoints ( void )
{
  char filename[256];

  char mapname[64];
  char botname[32];

  strncpy(mapname,STRING(gpGlobals->mapname),63);
  mapname[63] = 0;

  strncpy(botname,"he@dsh0t's bot",31);
  botname[31] = 0;

  sprintf(filename,"%s.wpt",STRING(gpGlobals->mapname));

  FILE *bfp = fopen(filename,"rb");

  if ( !bfp )
    return false; // fail

  waypoint_header hdr;

  fread(bfp,&hdr,1,sizeof(waypoint_header));

  if ( hdr.waypoint_version != WAYPOINT_VERSION )
    return false; // wrong waypoint version

  if ( strcmp(hdr.map,mapname) )
   return false; /// wrong map

  if ( strcmp(hdr.bot,botname) )
   return false; // wrong bot

  num_waypoints = hdr.num_waypoints;

  for ( int i = 0; i < num_waypoints; i ++ )
    fread(bfp,&waypoints[i],1,sizeof(waypoint_t));

  fclose(bfp);

   return true; // okay
}

void savewaypoints ( void )
{
  waypoint_header hdr;

  hdr.waypoint_version = WAYPOINT_VERSION;
  strncpy(hdr.map,STRING(gpGlobals->mapname),63);
  hdr.map[63]=0;
  strncpy(hdr.bot,"he@dsh0t's bot",31); 
  hdr.bot[31]=0;
  hdr.num_waypoints = num_waypoints;

  char filename[256];
   
  sprintf(filename,"%s.wpt",STRING(gpGlobals->mapname));

  FILE *bfp = fopen("wb",filename);

  fwrite(bfp,&hdr,1,sizeof(waypoint_header));

  int i;

  for ( i = 0; i < MAX_WAYPOINTS; i ++ )
  {
    if ( !waypointHasFlag(i,FL_DELETED) )
       fwrite(bfp,&waypoints[i],sizeof(waypoint_t));
  }

  fclose(bfp);
}

When saving the header is simply setup with the correct values put in the waypoint_version, current map and your bot name, and the number of waypoints on the map. The header is simply written to the binary file first and then there is a loop that loops from 0 to num_waypoints.

When loading the waypoints the header is read first and the header is checked for its validity, if it is valid then all waypoints are read sequentially.

How waypoints are added/deleted from the waypoints array

Code:

void addWaypoint ( edict_t *pEdict, int flags )
{
   if ( pEdict->v.flags & FLAGS_CROUCH )
        flags |= FL_CROUCH;

   if ( pEdict->v.movetype = MOVETYPE_FLY )
       flags |= FL_LADDER;

   // find a waypoint

   for ( int i = 0; i < MAX_WAYPOINTS; i ++ )
  {
     if ( waypoints[i].flags & FL_DELETED )
     {
          waypoints[i].flags = flags;
          waypoints[i].origin = pEdict->v.origin;

          // Find nearby reachable waypoints!!
          findPathsForWaypoint(i);

          num_waypoints++; // one new waypoint
          break;
     } 
  }
}

void deleteWaypoint ( int index )
{
   waypoints[i].flags |= FL_DELETED;
}

I'll write more later, please ask which area you need help with

He@dShot · **Re: Understanding Waypointing -** 08-09-2008

Hmm...this helped a lot ! These basic explanations made me understand more about the waypoint system...What I can't understand is what kind of mathematical or geometrical algorithms are used to figure out how bots find the nearest waypoint to some point, how they find out a retreat wpt...say just around a corner and stuff :d and what are paths ? wouldn't it be simplier without the paths ? or is that used for path experience...say that it tell s the bot that some area is dangerous being campers or snipers there....am I close ?

Cheeseh · **Re: Understanding Waypointing -** 09-09-2008

Paths are required to allow bots to know what other waypoints are reachable from a selected waypoint.

for example, one waypoint will have a list of waypoint indexes to all other waypoints it can go to.

waypoint index,

0 : 1
1 : 2 // this waypoint goes to 2
2 : 3,4 // this waypoint goes to either 3 or 4
3 : 1 // this waypoint goes back to 1
4 : 1

paths can usually be symmetric i.e. if a waypoint is reachable in one direction then it is reachable in the other. But this may not be the case in some situations such as a waypoint on the top of a ledge and a waypoint on the ground. The waypoint on the ledge will have a path to the waypoint on the ground, but the waypoint on the ground should not have a path to the waypoint on the ledge, unless the waypoint has a special type (e.g. FL_FLY) and the mod allows players to fly!

How paths are generated for each waypoint

Paths are generated by looping through each waypoint in the "waypoints" array and using things called tracelines that trace a line, funnily enough

, from one waypoint to another to determine if it is visible.

Code:

#define REACHABLE_RANGE 500 // 500 units away

void findPathsForWaypoint ( int index )
{
  short paths = 0; // paths found so far for this waypoint
  traceResult tr;

  for ( i = 0; i < MAX_WAYPOINTS; i ++ )
  {
     if ( i == index )
       continue; // skip the waypoint we are already looking at!!!

     if ( waypoints[i].flags & FL_DELETED )
      continue; // invalid waypoint!

     if ( (waypoints[index].origin - waypoints[i].origin).Length() < REACHABLE_RANGE ) // waypoint within a small range
    {
     UTIL_TraceLine(&tr,waypoints[index].origin,waypoints[i].origin,...); // more parameters needed in here but u should get an example from somewhere

     if ( tr.flFraction >= 1.0 )
     {
        // Visible
        if ( paths < MAX_PATH )
        {
           waypoints[index].path[paths++] = i; // add this waypoint to a path
        }
     }

    }
  }
}

Similalry the pathwaypoint create1/remove1 and create2/remove2 commands will add/remove a path from one waypoint to another.

How bots move towards its "current waypoint"

The bot needs to find the waypoint index in the waypoint array of the nearest waypoint first. The waypoint index is stored as its "current waypoint index". To do this it must loop through all waypoints in the waypoint array.

Code:

int findNearestWaypoint ( edict_t *pEdict )
{
   int wptindex = -1; // -1 = invalid waypoint index!!!
   int distance=REACHABLE_RANGE;

   for ( int i = 0; i < MAX_WAYPOINTS; i ++ )
   {
      if ( waypoints[i].flags & FL_DELETED ) // invalid waypoint!
        continue; // skip
     
     // within range!?
      if ( (waypoints[i].origin - pEdict->v.origin).Length() <= distance )
      {
        traceResult tr; // check if its visible (and not through a wall!!!)
        UTIL_TraceLine(&tr,pEdict->v.origin,waypoints[i].origin,...); // more parameters needed in here but u should get an example from somewhere

        if ( tr.flFraction >= 1.0 )
        {
           // Visible
           wptindex = i; // new nearest waypoint!
        }
      }
   }
}

Once the bot has a current waypoint, it must walk towards it

Code:

// find a waypoint
if ( pBot->current_waypoint_index == -1 )
   pBot->current_waypoint_index = findNearestWaypoint(pBot->pEdict);
else // we've already got one!
   walkTowardsWaypoint();

The bot must continuously check if it has reached the current waypoint.

To do this there is a function in HPBBot i think called BotNavigate(), this is called every frame.

It always checks if

Code:

#define WAYPOINT_TOUCH_DISTANCE 32

...


if ( (waypoints[pBot->current_waypoint_index].origin - pBot->pEdict->v.origin).Length() < WAYPOINT_TOUCH_DISTANCE )
{
   pBot->current_waypoint_index = NextWaypointInPath(pBot);
}
else
{
   //doNothing... or check if stuck

   int wptflags = waypoints[pBot->current_waypoint_index].flags;

   if ( wptflags & FL_CROUCH )
      pBot->v.button |= IN_DUCK; /// crouch!! we are going towards a crouch waypoint !!
}

How to find the best waypoint path

The bot must find a path from one place to another , for xample, in TFC the bot might want to find a flag and return it to the base. To do this, in the HPB_BOT, there are special flags called

Code:

FL_CAPTURE_POINT
FL_FLAG

There is also a special function, something like this which searchs for a random waypoint with these properties.

Code:

#define MAX_RAND_ARRAY 8

int findRandomWaypointWithFlags ( int Flags )
{
    int i;
    int numwpt = 0;

    int randomArray[MAX_RAND_ARRAY];

   randomArray[0] = -1; // set as invalid just now

    for ( i = 0 ; i < MAX_WAYPOINTS; i ++ )
    {
       if ( waypoints[i].flags & FL_DELETED) 
          continue; // skip

       if ( waypoints[i].flags & Flags )
       {
          if ( numwpt < MAX_RAND_ARRAY )
              randomArray[numwpt++] = i;
       }
    }
   
    return randomArray[RANDOM_LONG(0,numwpt)];
}

When it finds a destination waypoint to go to by using this function, the bot should use a path finding algorithm to find a route from its current waypoint (nearest waypoint) to its goal.

See the wiki on path-finding http://wiki.bots-united.com (username : wiki , password: nospam)

Using certain types of path finding algorithms can be intensive to CPU so usually a path is generated and the result of waypoint indexes the bot should go to in sequence is stored in the bot. Whenever the bot reaches its next waypoint, the bots new waypoint becomes the next waypoint in the path list.

retreating, cover waypoints, camping

The HPB Bots dont retreat. Some bots do, its a heavier subject. This requires extra information, such as a waypoint visibility table, which tells the bot which waypoints are visible from another. Just like the findRandomWaypointWithFlags function, we could loop though all waypoints again and see which one is not visible from a threat. and get the nearest one, then make that our goal, and run towards it for cover, when the bot reaches the goal, maybe it should crouch too!

Some bots have special camping flags that tell the bot to crouch and wait for a while before moving off again.

hope it helps