Pierre-Marie's navmesh tutorial
for FPS bots
applied to Half-Life

      Here we go. Sorry for the delay, but as usual I was kidnapped to some party again, and could not reasonably write any decent thing afterwhile, fuzzyness and headache forbidding.

      Okay pupils, take a sheet of paper, stick your bubblegum under the desk, don't trick your neighbour and look at your teacher. [classroom rumble]

      First off, forget everything you think you know about the word "navmesh".
      Navmesh. What the crap is that ? what does it do ? what does it eat ? is it friendly ?

      Good. Now we can start.

      Let's identify our problem. We have bots, sort of players without a player behind, and we want to make them intelligent. We want to write an AI that looks like AI. Well, no matter how intelligently your bot will chat, fire its weapon, or look around, if it doesn't move at all, it won't fail to look stupid.

      So we've got to figure out how humans navigate. Kind of a joke: everybody would think it's a simple thing. To go there I head up there, then there, then there. It's the path. But look, that's not the question: HOW do you "head up there", so that you actually arrive there at all ? Well, because I see where I walk. Aha, good remark indeed. To get to somewhere, we walk towards what we see. But what about blind people ? Well, I suppose they draw mentally their surroundings so that they can "see" their world, anyway. Okay, so, to get to somewhere, we walk towards what we KNOW, rather than what we SEE.

      First theorem: the bot needs to KNOW its space.

      how to make this at all ? Look, I'm in my room, sitting in front of my computer. I don't see 5 percent of my room where I actually am, but I know pretty well how the room extends behind my back. I know where it stops. I know that 3 meters away behind my back, there's a wall. And that 2.5 meters away on my left, there's another wall. But actually, I don't care a shit about the walls, what I do care about is the FLOOR. Because that's what supports me. That's where I can move. I know that in the square that makes my room, I can be standing anywhere on the floor, I'll be in a safe place.

      So we need to make our bots know how their space is organized. Into rooms. Sectors. Where they can walk, sort of.

      In short, we need bots to feature a memory in which they will put squares, triangles, rectangles, that will be the "rooms" and the "alleys" of their world.

      But look, do we really need to build these squares and these triangles ourselves, when we know the game engine also use squares and triangles to draw the world on the video card ? What if we just took those we need, those that represent a walkable surface in the world ?

      Okay, now I hear a pupil who asks me: "but look, mr. teacher, these squares and these triangles the engine uses don't necessarily represent the rooms and the alleys like we see them ?"

      Good point, kid. I'll remember to evaluate your next paper favorably. But where's the problem, actually ? If the game engine needs 3 squares and 2 triangles to represent the floor of my room, where is it a problem for us ? Can't I say: "I'm in the northwest part of my room" rather than just "I'm in my room" ? It's just a level of granularity behind. The ONLY problem it would be for, is when it comes for us to think about a path to another room. Look, I want to go and trick my little sister in her room. To go there, I know I have to :

• leave my room to enter the garage,


• leave the garage to enter the staircase,


• leave the staircase to enter the entrance corridor,


• leave the entrance corridor to enter the rooms corridor,


• and finally leave the rooms corridor to enter my little sister's room so that I can trick her until she screams out mommy mommy Pierre-Marie is doing nothing but tricking me.

      Would it be impossible to think rather this way ? I need to :

• leave the northwest part of my room to enter the west part of it,


• then leave it to enter the south part of the garage,


• then leave it to enter the southeast part of it,


• then leave it to enter the bottom half of the staircase,


• then leave it to enter the top half of it,


• then enter the northwest part of the entrance corridor,


• then enter its center part,


• then enter the south part of the rooms corridor,


• then cross its center and north part,


• and then leave the corridor to enter my little sister room's southwest part,


• then cross its center,


• then reach its northwest part where my little sister is currently doing her schoolwork.

      So we have 2 choices. Either we use directly the squares and triangles the engine is displaying, or we do extensive computations beforehand to merge them together so as to have squares and triangles that describe better what we see (i.e, "rooms" and "alleys").

      Personally I suck at math... [pupils: hee hee hee]

      I hear pupil Tub making fun of me, because Tub is good at math and he would probably do a lot of preprocessing on these squares and trianges to build more natural ones. And he would probably succeed, and he would probably show it proudly to the other bot coders when he meets them in Amsterdam. But hey, I suck at math, and I'm lazy, so I will take the first solution. I will consider the barebones level geometry.

      How to get it ? A difficult question indeed. Unless we hook directly into the video memory, I'm afraid we'll have to extract it from the data file that makes the level. Here we go, then.

      Let's take the FPS game, "Half-Life".

      Half-Life has been built out of the Quake 2 source code, we know that because there are parts of ID software's source code in the Half-Life SDK, and like Quake, it uses the Binary Space Partition format to store the level's data. BSP, in short.

      Hey look, Mr. botman already made a lovely set of tools to hack BSP files! And there's source code! w00t!

      Let's toy around a little with them, so we see which one is the most interesting for us :

• there's a BSP viewer, with a real 3D rendering engine, and certainly lots of complicated stuff inside. Scary.


• there's a BSP slicer, that cuts the map in slices and plots the polygons for each slice into a BMP file. Interesting.


• and there's also a BSP otherstuffmaker, which makes a lot of miscellaneous other stuff. Too miscellaneous.

      We'll definitely want to look at the BSP slicer, for it does just what we need: plotting the ground.

      Indeed, we want to plot the ground ; but we don't want to slice the map at all. Or rather, we want to make just one slice, so that the world is not sliced. So let's hack the source code and simplify it all.

      Now it appears that Mr. botman doesn't seem to check whether the polygon he draws is a floor, a ceiling or a wall. It's understandable, though : if it's a wall, and the resulting BMP file is meant to be looked from the top down, we just won't see it. And if it's a ceiling, it will look the same as the floor. We really need to add some code to prevent walls and ceilings to be plotted. How to do that ?

      Well, have you noticed that in Half-Life, you can basically walk on any surface which slope does not exceed 45 degree ?
      Here's the criterium we need. Now, to figure out the slope of a polygon, there are several methods.

1. Either we call ourselves Tub and we are good at math, in which case we'll take joyfully all the vertices, that's to say the corners of our polygon, and we'll happily put complicated equations to work that will tell us the plane this polygon lies on, and given the slope of the plane, by some scary twisted math again, we'll either discard it if it's too sloppy or keep it if it's rather flat.



2. Else we call ourselves John Dumbass and we suck at math, and we rummage around a bit in order to see if there's not a simpler method. Oooooooh look what we've just found: there are structures that seem to talk about planes ! And there seems to be coordinates for the plane normal as well ! Good but... heck, these are separate structures, how do I know which polygon belongs to which plane ? Need to sort that out. Let's see... hey, there's a "planenum" field in the "dface_t" polygon structure ! What if it was the index of the plane in the planes array ? Let's check that right away... YEP! Now we know which plane a polygon belongs to, and what is its normal. No need to be good at math to figure out that if the normal's Z coordinate gets low or gets negative, the plane is too sloppy to be walkable ; or even, it's a ceiling : take a sheet of paper and pierce it with a pen, move that sheet in front of your eyes in different positions and you'll see that the Z (vertical) coordinate of the pen (which is the sheet's "normal"), needs to be above a certain value for the sheet to have less than a 45° angle. Take your trusty calculator and your old math schoolbook, and look for the "trigonometry" chapter. It tells you what you need to know : using cosine and its siblings, you work out that the minimum Z for a plane's normal floats around the value 0.707106, if you want that plane to be walkable. And now, we can use this as a test in the code to allow certain polygons to be plotted and others not !

      Okay, now as output we've got a BMP file in which only the map's floors are plotted. But we don't want a BMP file, we want a list of squares and triangles. So we need first to agree on the walkable surface structure we'll use that will best fit our needs.

      First off, no need to be good at math to understand that a surface needs to be described by its corners. This triangle goes from here to there, then to there and back. Hence, we need to have an array of vectors that will hold our surface's corners. And we also need to know how many corners it has, to see if it's a square, a triangle or anything else :

// walkable surface structure definition
typedef struct
{
   Vector *v_corners; // pointer to array of face edges vector locations (mallocated)
   int corner_count; // number of edges this face has
} walkface_t;

      You could eventually have declared a static array for v_corners, that would have held up to, let's say, 8 corners, but it's wasting memory, so I preferred to mallocate() it.
      Okay, now we know how to store the sufficient info needed to describe a walkable polygon. And pupils scream: "Let's have them all in some array, then !"... eh, wait, kids. What size will you declare your array ? Hmmm ?

      Typically 2 solutions, as usual:

1. You're a forestry worker who doesn't give a crap about resource consumption, so you blindly declare a 1 gigabyte-sized array to store your walkfaces and ensure you'll have enough space to store them all,


2. You're crafty enough and you cycle through all the polygons first and count the ones you need, and then you mallocate() just enough memory to store them. And of course, you don't forget to free() it when your program stops.

      We'll definitely want the 2nd solution, don't you think ?

walkface_t *walkfaces; // pointer to map's walkable faces memory space (mallocated)
int walkfaces_count; // number of walkable faces in this map

      Good. Let's put this to work. Back to botman's BSP slicer, we see that he stores the bounds of the edges of his polygons in a 2 elements vector array ("v"). Well, that's just what we need. Once we ensured the segment currently being plotted into the BMP file belongs to a polygon that is walkable, we just have to count the number of corners there are in the polygon, slap a malloc() call on it that will make space in our v_corners array for us, and all we have to do then is to stuff our walkface with the corner's coordinates, and the walkfaces array with this walkface.

      Et voilà! We are now the proud owners of a walkfaces array that describes accurately the map meshes our bots can navigate on! We have built a "navmesh" ! [pupils: wwwwwwwoooooowwwwww]

      Now once all this has been tidied up, it becomes fairly easy to incorporate it into the bot code. As soon as a new map starts, we're left to open the BSP file ourselves, and then using our hacked version of botman's code, build the navmesh. Eventually, the caviar on top of the toast is to make a function that will save and load back this navmesh on a file on disk. Fear an exam on such a function in a near future, pupils.

      Okay! Now we have a (very basic) navmesh our bots can use. But how to use it, actually ?
      Let's see.

      Look at our navmesh : it currently holds about 5000 walkfaces. That's quite much, isn't it ? Yeah, indeed, that's much. Too much if we want to look for a particular walkface at a particular location. Imagine: if we wanted to know which walkface is behind a particular bot, it would take ages to test all of them. Hence I propose we optimize things a bit.

      What would a human do ? I mean, how would a human think of a particular room in a castle as big as Versailles, for example ? Well, just hear them talking : "today I visited the Salon Louis XIII, the paintings are awesome! - Salon Louis XIII ? Where is that again ? - It's on the southeast building of the castle - Ah, okay. I see". Wait, I don't know whether there is a Salon Louis XIII in Versailles (although there must probably be one), and I don't know the crap where it is. It was just for the example. But one of the situations where it comes even more clearly is when humans talk about oversea navigation. Where are the Kerguelen islands located on the globe ? Where are the Bermuda ? Now navys can't just say "it's in the top half of the Atlantic", for that top half of the Atlantic is quite vast, already. So for ages navy people had a very interesting method: slicing the world into sectors, which of them are bounded by "parallels" and "meridians", i.e, respectively imaginary horizontal and vertical lines. So they just talk about the sector that is comprised between the 4th and 5th parallel, and the 17th and 18th meridian, and everyone agrees. Every navy knows what countries and islands are between the 4th and 5th parallel, and the 17th and 18th meridian. Okay, I don't, but hey, I'm not a navy.

      Why wouldn't we use a similar method to split our navmesh ? We would have a bidimensional array in which each bucket would represent a sector in the world, and inside each bucket, a mallocated list of pointers to the walkfaces that belong to this sector !

      Kind of funny, actually: botman was slicing his world at flat, and us, we undid it and now we have to redo it because we need to slice it vertically. [pupils: mmmmeeeeeeehhhhhhh]

      Let's call this array, the map "topology". One could perhaps think of a better name, but nevermind.

      We also need to declare the number of parallels and number of meridians there will be in the map. Either we make them static, with a #define somewhere, or even better: we make these adaptative to the size of the map itself ! This way, we can ensure our sectors won't be too small if the map is relatively small, and by limiting them to some maximal value, we can also ensure we won't ever get more than a fixed number of parallels and meridians. Now you ask, "very nice, mr. teacher, but how do you get the size of the world ?" Listen pupils, the size of the world is just the size of the bounding box of the worldspawn entity, which is the first model you load in the BSP file. Look at botman's code: when he reads successively all the "lumps" that make up a BSP file, he fills an array called "dmodels". Well, the first dmodel is the world.

      Look at the dmodels structure : we've got the "mins" and "maxs" vectors, which, in the ID software terminology, are at 99.99999% likely to be the bottom left and top right corners of some bounding box... which means ? which simply means that dmodels[0].mins and dmodels[0].maxs hold the limits of the worldspawn entity's bounding box. We've found what we need.

      Eventually, would the information not be available this way (if you intend to port your navmesh to a game engine other than Half-Life), there is another method : if, during the time when you cycle through all the map's polygons and count the number of walkfaces, you check for their vertices and keep track of the one which is the most on the left, and the one which is the most on the right, and that you do so respectively for the X and Y axis, you'll end up with 4 values : where the map starts on the X axis, where the map ends on the X axis, where it starts on the Y axis and where it ends on the Y axis. Now substract start to end, and you'll get the size of the world.

      Choose the method you want ; for me, since the information I need is directly available through the first bucket of the "dmodels" array, it'll be method #1.

// map topology granularity
#define MAX_MAP_PARALLELS 64
#define MAX_MAP_MERIDIANS 64


// topologic sector structure definition
typedef struct
{
   walkface_t **faces; // mallocated array of pointers to walkable faces located in this sector
   int faces_count; // number of walkable faces in this array
} sector_t;


int parallels_count; // number of parallels dividing this map into sectors
int meridians_count; // number of meridians dividing this map into sectors
sector_t topology[MAX_MAP_PARALLELS][MAX_MAP_MERIDIANS]; // map spatial topology


// compute the number of sectors this map should have (300 units-sized sectors by default)
parallels_count = (dmodels[0].maxs.x - dmodels[0].mins.x) / 300;
meridians_count = (dmodels[0].maxs.y - dmodels[0].mins.y) / 300;

// don't allow the parallels and meridians count to be higher than the maximal value allowed
if (parallels_count > MAX_MAP_PARALLELS)
   parallels_count = MAX_MAP_PARALLELS; // bound the number of parallels up to MAX_MAP_PARALLELS
if (meridians_count > MAX_MAP_PARALLELS)
   meridians_count = MAX_MAP_MERIDIANS; // bound the number of meridians up to MAX_MAP_MERIDIANS

      Very good, now we need to fill that topology array. While we'll be parsing all the polygons, we'll need from time to time to dispatch some pointers to them into the right buckets of this 2D array. That's why realloc() will come in handy. But for a heap of good reasons, and especially a failsafe one, it's best to mallocate the minimal space for each bucket. Because in case we were to access an empty bucket, we wouldn't want to fall on an unitialized pointer. So...

// also allocate the minimal space for each bucket of the map topology hashtable
for (i = 0; i < parallels_count; i++)
   for (j = 0; j < meridians_count; j++)
   {
      topology[i][j].faces = (walkface_t **) malloc (sizeof (walkface_t *));
      if (topology[i][j].faces == NULL)
         TerminateOnError ("malloc() failure on %d bytes for 1st-time sector [%d,%d] allocation\n",
                           sizeof (walkface_t *), i, j);
      topology[i][j].faces[0] = &walkfaces[0]; // failsafe pointer
      topology[i][j].faces_count = 0; // reset the faces count: no walkface yet in this sector
   }

      Now we're ready to dispatch our walkfaces into the right buckets of our topology hashtable. While we're cycling through each BSP polygon to translate it into the corresponding walkface, once this is done we're left to cycle through each sector and see if this walkface belongs to it. In case yes, we stuff a pointer to the walkface in the right bucket of the 2D array.

// for each latitude/longitude sector of the map topology array...
for (i = 0; i < parallels_count; i++)
   for (j = 0; j < meridians_count; j++)
   {
      // does this face belong to this topologic sector ?
      if (WalkfaceBelongsToSector (walkface, i, j))
      {
         // reallocate enough space for this sector to hold one walkface more
         topology[i][j].faces = (walkface_t **) realloc (topology[i][j].faces,
                                                        (topology[i][j].faces_count + 1)
                                                        * sizeof (walkface_t *));
         if (topology[i][j].faces == NULL)
            TerminateOnError ("realloc() failure on %d bytes for sector [%d, %d] allocation\n",
                              (topology[i][j].faces_count + 1) * sizeof (walkface_t *), i, j);

         // now store a pointer to this walkable face in this topological sector
         topology[i][j].faces[topology[i][j].faces_count] = walkface;
         topology[i][j].faces_count++; // this topological sector holds now one face more
      }
   }

      Aha, I hear you stop me, you're curious about that WalkfaceBelongsToSector() function, aren't you ? Yeah, that's right, we need some function that will tell us if some walkface belongs to some sector or not. How to tell this for sure ? Mmh, I'm afraid here, there'll be a bit of math involved. We can enumerate several rules, from the most obvious one, that's to say the fastest to compute, to the most mathematic one, i.e, the most CPU-intensive. Look :

• First, a walkface belongs to a particular sector if any of its segment's bounds are comprised within the sector. This is the obvious.


• Second, a walkface belongs to a particular sector if any of its segments crosses completely the sector, either horizontally or vertically. This is easily seeable.


• Third, a walkface belongs to a particular sector if any of its segments crosses any of the four segments that make up the sector's square. This is math, we've got to compute the lines equations and look for a possible intersection point.


• Fourth, a walkface belongs to a particular sector if the walkface is WAY bigger than the sector and the sector is completely comprised within the walkface. This is not the most obvious case, but beware not to forget it ! To verify this, we'll use botman's method. Botman says (listen carefully): "if the sum of the angles between a corner of the sector and all the corners of the walkface make up 360, then the corner of the sector is within the walkface". Draw any convex polygon on a sheet of paper. Now take a point anywhere on the sheet, and sum up the angles between this point and all the successive corners of the polygon. If your point is within the polygon, you'll find 360. Else, you'll find some other value. w00t botman, w00t!

      The implementation of it all can look like the following function. Since it's one that needs only to be called on map start, when we split the navmesh in sectors, it doesn't particularly need to be blazingly fast. Note that I haven't made this up all myself, I've been given help by botman and Cheesy. But the comments are mine, and I've written the final function. Look:

bool WalkfaceBelongsToSector (const walkface_t *pFace, int sector_i, int sector_j)
{
   // this function returns TRUE if the walkface pointed to by pFace belongs to the topological
   // sector whose position in the global array is [sector_i][sector_j], FALSE otherwise.

   // Math code courtesy of Paul "Cheesemonster" Murphy (HUGE thanks mate !).

   int corner_index;
   float sector_left, sector_right, sector_top, sector_bottom, y, a, x, b, angle;
   Vector v_bound1, v_bound2, segment_left, segment_right;

   // first compute the left, right, top and bottom coordinates indices of the sector
   sector_left = v_worldmins.x + sector_i * ((v_worldmaxs.x - v_worldmins.x)
                                             / parallels_count);
   sector_right = v_worldmins.x + (sector_i + 1) * ((v_worldmaxs.x - v_worldmins.x)
                                                    / parallels_count);
   sector_bottom = v_worldmins.y + sector_j * ((v_worldmaxs.y - v_worldmins.y)
                                               / meridians_count);
   sector_top = v_worldmins.y + (sector_j + 1) * ((v_worldmaxs.y - v_worldmins.y)
                                                  / meridians_count);

   angle = 0; // reset angle which will hold the sum of angles to face corners

   // loop though the corners of this face...
   for (corner_index = 0; corner_index < pFace->corner_count; corner_index++)
   {
      // locate the first vertice of this edge
      v_bound1 = pFace->v_corners[corner_index];

      // locate the second vertice of this edge
      if (corner_index < pFace->corner_count - 1)
         v_bound2 = pFace->v_corners[corner_index + 1]; // next corner in the array
      else
         v_bound2 = pFace->v_corners[0]; // loop back to corner zero at last corner

      // now we have one of the edges of the face, let's see if this segment is included within
      // the sector, completely crosses it, or crosses at least one of the sector's boundaries ;
      // in this case, our face will belong to this sector indeed. But beware! face could STILL
      // belong to sector if it was much larger than the sector itself, and the sector would be
      // COMPLETELY comprised within the face (in this case, the sector would have one face and
      // only one, this face). To check for that extra situation, we use a method that Jeffrey
      // 'botman' Broome inspired us, i.e, we take one of the corner of the sector, and see if the
      // sum of the angles that are (edge N bound 1 -> corner of sector -> edge N bound 2) for
      // each edge N of the face, is 360 ; in this case, the corner of the sector will be just
      // on top of face, and it'll mean that face belongs to the specified sector. That's why we
      // first go for the inclusion/intersection check, and after that we go for the angles.

      // its obvious it is in sector, if one or both points are inside the box
      if (((v_bound1.x >= sector_left) && (v_bound1.x <= sector_right)
           && (v_bound1.y >= sector_bottom) && (v_bound1.y <= sector_top))
          || ((v_bound2.x >= sector_left) && (v_bound2.x <= sector_right)
              && (v_bound2.y >= sector_bottom) && (v_bound2.y <= sector_top)))
         return (TRUE); // if so, segment belongs to sector

      // at this point, NONE of the segment bounds are inside the box

      // is this segment vertical ?
      if (v_bound1.x == v_bound2.x)
      {
         // is this vertical segment comprised between left and righ boundaries of the sector ?
         if ((v_bound1.x >= sector_left) && (v_bound1.x <= sector_right))
         {
            // if so, it belongs to sector if, and only if, the bottom bound is lower than the
            // bottom limit of the sector and the top bound is higher than the top limit of it.

            // is the first bound the bottom bound ?
            if (v_bound1.y < v_bound2.y)
            {
               if ((v_bound1.y <= sector_bottom) && (v_bound2.y >= sector_top))
                  return (TRUE); // segment crosses the sector completely
            }
            else
            {
               if ((v_bound2.y <= sector_bottom) && (v_bound1.y >= sector_top))
                  return (TRUE); // segment crosses the sector completely
            }
         }

         // if this is not the case, either the segment is :
         // - completely on the left of the sector
         // - completely on the right of the sector
         // - completely beyond the top of the sector
         // - or it is completely under the bottom of it.
      }

      // else is this segment horizontal ?
      else if (v_bound1.y == v_bound2.y)
      {
         // is horizontal segment comprised between the bottom and top boundaries of the sector ?
         if ((v_bound1.y >= sector_bottom) && (v_bound1.y <= sector_top))
         {
            // if so, it belongs to sector if, and only if, the left bound is beyond the left
            // limit of the sector and the right bound is beyond the right limit of it.

            // is the first bound the left bound ?
            if (v_bound1.x < v_bound2.x)
            {
               if ((v_bound1.x <= sector_left) && (v_bound2.x >= sector_right))
                  return (TRUE); // segment crosses the sector completely
            }
            else
            {
               if ((v_bound2.x <= sector_left) && (v_bound1.x >= sector_right))
                  return (TRUE); // segment crosses the sector completely
            }
         }

         // if this is not the case, either the segment is :
         // - completely on the left of the sector
         // - completely on the right of the sector
         // - completely beyond the top of the sector
         // - or it is completely under the bottom of it.
      }

      // else segment is neither horizontal nor vertical, but just bent (grr)
      else
      {
         // we have to compute the bastard's equation.

         // arrange the bounds of the segment in the right order relatively to the X axis
         if (v_bound1.x < v_bound2.x)
         {
            segment_left = v_bound1;
            segment_right = v_bound2;
         }
         else
         {
            segment_left = v_bound2;
            segment_right = v_bound1;
         }

         // the equation of a line is under the form y = ax + b, we need to find a and b.
         a = (v_bound2.x - v_bound1.y) / (v_bound2.x - v_bound1.x); // compute the slope : a
         b = v_bound1.y - a * v_bound1.x; // compute the Y offset at origin : b

         // at this point, none of the segment bounds are inside the box ; but now, we do know its
         // equation, so we can check if the segment intersects either of the sector's boundaries.

         // compute coordinates of intersection point of line and sector's LEFT bound
         // coordinates are : (x, y)
         x = sector_left;
         y = a * x + b;

         // does this intersection point belongs to both segments ?
         if ((x >= segment_left.x) && (x <= segment_right.x)
             && (y >= segment_left.y) && (y <= segment_right.y)
             && (y >= sector_bottom) && (y <= sector_top))
            return (TRUE); // the segment crosses the sector's LEFT boundary

         // compute coordinates of intersection point of line and sector's RIGHT bound
         // coordinates are : (x, y)
         x = sector_right;
         y = a * x + b;

         // does this intersection point belongs to both segments ?
         if ((x >= segment_left.x) && (x <= segment_right.x)
             && (y >= segment_left.y) && (y <= segment_right.y)
             && (y >= sector_bottom) && (y <= sector_top))
            return (TRUE); // the segment crosses the sector's LEFT boundary

         // at this point, none of the segment bounds are inside the box NOR does it intersects
         // the left and right boundaries of the sector ; let's turn its equation upside down so
         // that we have x = f(y)

         // compute coordinates of intersection point of line and sector's TOP bound
         // coordinates are : (x, y)
         y = sector_top;
         x = (y - b) / a;

         // does this intersection point belongs to both segments ?
         if ((x >= segment_left.x) && (x <= segment_right.x)
             && (y >= segment_left.y) && (y <= segment_right.y)
             && (x >= sector_left) && (x <= sector_right))
            return (TRUE); // the segment crosses the sector's TOP boundary

         // compute coordinates of intersection point of line and sector's BOTTOM bound
         // coordinates are : (x, y)
         y = sector_bottom;
         x = (y - b) / a;

         // does this intersection point belongs to both segments ?
         if ((x >= segment_left.x) && (x <= segment_right.x)
             && (y >= segment_left.y) && (y <= segment_right.y)
             && (x >= sector_left) && (x <= sector_right))
            return (TRUE); // the segment crosses the sector's BOTTOM boundary
      }

      // at this point, we are assured that none of the segment bounds are inside the box AND
      // that it intersects NONE of the four segments that make the boundaries of the sector.

      // now sum up all the angles corner - point - next corner to see if we have 360 (thx botman)
      angle += fabs (AngleOfVectors ((Vector (v_bound1.x, v_bound1.y, 0)
                                      - Vector (sector_left, sector_bottom, 0)),
                                     (Vector (v_bound2.x, v_bound2.y, 0)
                                      - Vector (sector_left, sector_bottom, 0))));

      // and go looping again for the next edge of the face...
   }

   // okay, here, NONE of the segment inclusion/intersection checks succeeded, so it's time to
   // check whether we're in that particular case where the sector is completely included within
   // the face, using the angle method we computed earlier.

   // if the resulting angle is close to 360, then the point is likely to be on the face
   if (fabs (WrapAngle (angle - 360)) < 0.1)
      return (TRUE); // sector is included within this face, so face belongs to sector

   return (FALSE); // all our checks failed, face can't possibly belong to sector, return FALSE.
}

      See, it's a rather long function. But not that much if you strip all the comments, and it's pretty fast to execute. Now we can test if a walkface belongs to a particular sector, we can fill our topology hashtable with pointers to walkfaces that belong to each sector, and we've got a navmesh that is splitted in sectors using a 2D lookup table. Isn't that nice ?

      You may want to know how to find the sector a particular location belongs to. It's very simple ; there was the reverted algorithm for it in the above function, but looks like you've missed it. You first need to know the x and y position ratio in the world compared to the x and y full size of the world ; that's to say, you need to know the percentage far from the left side of the world your location is, and the percentage far from the bottom side of the world it is too. Then, take this ratio, and multiply it by the number of parallels for the X side, and by the number of meridians for the Y side. It gives you the X and Y indices in the topology array your location belongs to. Beware of a bug ! if your location is 100% on one side of the world (on the x axis) or 100% on the other side (y axis), you'll land into an unexistent bucket, out of the array ! You need to check for this eventuality, and in this case, return the last horizontal or vertical bucket's index.

      Now you'll want to go deeper and find the actual walkface that is below a particular spot in the world... (this is pretty much the point of the navmesh, isn't it ?)

walkface_t *WalkfaceUnder (Vector v_location)
{
   // this function returns the ground face under v_location on the floor.

   int face_index, corner_index;
   float angle;
   sector_t *pSector;
   walkface_t *pFace = NULL;
   Vector v_lowered_location, v_bound1, v_bound2;

   // get a quick access to a lowered version of v_location
   v_lowered_location = DropToFloor (v_location); // drop v_location on the floor using a TraceLine

   // get a pointer to the sector it is in the topology hashtable
   pSector = SectorUnder (v_lowered_location);

   // loop through all the face we know to be in this topological sector
   for (face_index = 0; face_index < pSector->faces_count; face_index++)
   {
      pFace = pSector->faces[face_index]; // quick access to the face

      angle = 0; // reset angle sum

      // loop though the corners of this face...
      for (corner_index = 0; corner_index < pFace->corner_count; corner_index++)
      {
         // locate the first vertice of this corner
         v_bound1 = pFace->v_corners[corner_index];

         // locate the second vertice of this corner
         if (corner_index < pFace->corner_count - 1)
            v_bound2 = pFace->v_corners[corner_index + 1]; // next corner in the array
         else
            v_bound2 = pFace->v_corners[0]; // loop back to corner zero at last corner

         // sum up all the angles corner - location - next corner and check if we have 360
         angle += fabs (AngleOfVectors ((v_bound1 - v_lowered_location),
                                        (v_bound2 - v_lowered_location)));
      }

      // if the resulting angle is close to 360, then the point is likely to be on the face
      if (fabs (WrapAngle (angle - 360)) < 0.1)
         return (pFace); // assume location vector is on this face
   }

   return (NULL); // not found a face to which location vector could belong...
}

      As you can see, this is simply done by checking the candidate walkfaces in the right sector of our 2D topology table, using botman's angle sum method.

      Oh, while we're at it, were you to want to convert a walkface pointer into its index in the walkfaces array (the navmesh) ? Well, if you substract the address of the start of the array to the address of your walkface pointer, you'll get the hex offset from the start of the array where your walkface is. And if you want to know the index, just split that offset by the size of a walkface element. You see, nothing really biggy so far. But hey, look behind us: by doing "nothing biggy", we've "just" made a navmesh out of the BSP tree optimized with a bidimensional lookup table !

      Now it's time to wonder about what's coming next. Our bots have now a mean to represent the world, to "know where they are", and to know where they can go. Every walkface in the bot's navmesh is like a room in my house where I can go. But still, you have to admit, if the rooms in my house don't have doors, and if I don't know where these doors are, all my rooms will look like locked prisons and I'll have big trouble going to my little sister's room to trick her, don't you think ?

      Indeed, we need another sort of information for the bots to be able to navigate from one walkface to another. That is, we need to know where the "passage points" between each walkfaces are.

      We're about to commit some modification to our navmesh. Is it the only modification we should make at this point ?

      Look, for example, is it wise to allow all the bots to use the same information about these passage points ? Some bots may know that a passage from here to there exist, because they saw a player in this passage, or because they experienced it themselves ; but others may not, really. We don't want our bots to be prescient like Paul Atreides on planet Dune, do we ? Whee, now you're arguing about the memory space this would waste. Okay ! Okay, let's see. Our walkfaces array makes up as much as... 200 kilobytes at most. Ridiculous. Multiply this by 32 bots in game, and you get as much as... 6.4 megabytes. Really, do you think it's too much ? Well, you decide for yourself, but for me, knowing that nowadays we stuff as much as 512 megabytes of RAM into our computers, I can hardly see why I would prevent myself from using this nice feature, that is, that each bot have its own image of the navmesh. And hey, I could quote heaps of advantages that this feature would give us : that having some individual path memory would affect the bot's personality to a whole new level, that it's just impossible to do more human-like, that in case one bot was to plot a non optimal path it wouldn't affect the whole population... etc, etc.

      Convinced ? Good.

      Hence, let's declare the bot's navigation memory, which will, among other things, hold the passage points between walkfaces and a couple of variables used by the pathfinder. It's just an array, which has the same number of elements as the global navmesh array. The two arrays, that is, the global navmesh on one hand, and the bot's image of it on the other hand, will be strictly parallel.

      Somewhere in the bot structure...

navnode_t *PathMemory; // pointer to the array of navigation nodes the bot remembers

      You may want to ask what a "navnode" is ? Well, virtually, a navnode is the bot's image of a walkface. Hence it needs to be a struct, in which there is at least a pointer to the walkface it describes, an array of passage points to other navnodes, and some dynamic data that may be used by the pathfinder, or for whatever use else.

// navigation node structure definition
struct navnode_t
{
   walkface_t *walkface; // the walkable face this node concerns
   struct navlink_t links[8]; // array of navigation links (entry points from other navnodes)
   char links_count; // number of navigation links in this navigation node

   // dynamic data
   int whatever_variable;
   float yet_another_variable;
   Vector one_more_for_the_road;
   //etc, etc.
};

      The "links" array holds the passage points to other navnodes, it is filled up to links_count. Did you notice it has the type "navlink_t" ? Yeah, cause we don't know yet how to arrange the data that will describe best what we want ; but one thing is certain, it'll be a struct, for it will need to hold several different types of data. We'll see how it needs to be declared soon. Patience, kids...

      Anyway you see, there's one more level of abstraction. All the bots share the same global navmesh, but they do not know it all. Only what they know of it is usable in their PathMemory. navnodes that are usable in the PathMemory array are navnodes which have links to each other ; that is, navnodes that represent walkfaces on which the bot saw players plot a path, or for which the bot experienced a path itself.

      I guess I gotta draw some sketch at this point.

               Bot1            Bot2            Bot3            Bot4            Bot5
             navnodes        navnodes        navnodes        navnodes        navnodes
          (PathMemory[])  (PathMemory[])  (PathMemory[])  (PathMemory[])  (PathMemory[]) 
                |               |               |               |               |
                |               |               |               |               |
                +---------------+---------------+---------------+---------------+
                                                |
                                                |
                                             navmesh
                                          (walkfaces[])

      Let me insist on the explanation again, people. the navmesh (the global walkfaces array) and the bot's memory of it (the PathMemory navnodes array) are strictly parallel. This means, navnode #354 in bot's memory corresponds to walkface #354 in the navmesh. And this means also that EVERY walkface pointer in the bot's image of the navmesh is filled. There is NO walkface pointer in any slot of the bot's PathMemory array that points to nowhere. All of them are filled, all of them are valid. It's only that these navnodes become of some use for the bot, when there are LINKS to others.

      I may very well know each and every room in my house, this knowledge won't be of any use for me if I don't know any door to them. It's the same for bots and their navnodes. They may very well know every walkface of the map, if they don't know any entry points to them, their problem won't be taken much further.

      Once a bot sees a player moving from one walkface to another, or realizes itself that it can walk from this walkface to that other one, it fills one slot more in the navlinks array of the destination navnode. It knows now one entry point more for this navnode. And it knows which navnode came before this entry point.

      Look, I'll draw this on the blackboard again :

      walkface 1   ------->   player walks   ------>   walkface 2
                               _
                               /|
                              /
                       Bot sees player
                        :
                        :.........> Bot adds one link to navnode 2
                                                  :
                                                  :.....> passage point = player's location
                                                          comes from navnode 1
                                                          normal reachability (player is walking)

      Bingo! This tells us directly how we have to arrange that famous navlink structure, the one we didn't know how to arrange when we declared it into the navnode. We need to store :

1. The vector location of the passage point


2. The navnode it is from (NOT the navnode this entry point belongs to, rather the navnode that LED to this entry point)


3. The type of reachability it is (that is, if one needs to run, open a door, press a button, wait for an elevator, etc).

// navigation link structure definition
struct navlink_t
{
   struct navnode_t *node_from; // pointer to the navigation node beyond this entrypoint
   char reachability; // type of reachability it is (normal, ladder, edge fall, elevator, etc.)
   Vector v_origin; // vector origin of this link (passage between 2 nodes) in the virtual world
};

      Et voilà! We've just given our little bots an individual knowledge of the navmesh, and they KNOW how to use it.

      Do you want to know why the navlink should rather be added to the destination node and describe the node it comes FROM, than being added to the start node and describe the node it goes TO ?

      It's a crafty pathfinder trick. Hehe. [pupils immediate attention]

      You know, pathfinders are fat expensive machines, that eat piles of CPU cycles and spread into memory like yoghurt. If we start a pathfinding cycle, we're never sure when the beast will decide it'll have finished. That's why, in FPS games where the frame rate is important, modern game makers start to timeslice their pathfinders : instead of lowering the quality of the algorithm for the sake of the framerate, they allow the pathfinding process to extend on several frame. By doing this, they save a lot of quality in the resulting path and they ensure the game will always run smoothly.

      But there's something none of them thought of. [pupils attention reaches paroxysm]

      Imagine : you're in a very complicated level of the game, with lots of AI characters and lots of special FX. Your framerate has gone down to 20 ; that is, one frame lasts 1/20th second. Now imagine an AI character requests a complex pathfinding that will last 10 frames. Possible, indeed. 10 frames... how long does that last ? Compute the result yourself : at 20 fps, 10 frames last half a second.

      Now will the AI character be quietly sitting down for 10 frames, half a second, waiting for the pathfinder to finish ? Prolly not ; the character will certainly be moving, and most of the time it'll be moving as fast at it can. Now take this very common situation : the AI changes its mind. It wanted to go somewhere, but now it wants to go elsewhere. That's to say, while it was walking a path, some new event decided it to walk another path. The bot called its pathfinder, and half a second later, the pathfinder returns the new path. And what do we see ? The bot walks back to where it was half a second before, then change direction and starts its new path from there !

      Nothing looks more stupid. [pupils: hee hee hee]

      To avoid this tragedy, the wicked trick is simply to compute the path in the reverse order. The start node (the bot) becomes the goal node, and the goal node (where the bot wants to go) becomes the start node ; and while doing it, we tell the pathfinder to update the goal node (which is now the bot) dynamically. By doing this, at the last frame of the pathfinding session, the goal node will still be on bot's actual, current feet position. And while it'll be finding the path, the pathfinder will be spreading towards a goal that MOVES... until it is reached.

      Guys, this is absolute l33tage. (et le laitage, c'est bon)

      Here's why we store navlinks as a node's entry points, and not as a node's exit points. [pupils: wwwwwwooooooooowwwww]

      And now, kids, here's the last part of today's lesson, before tomorrow's lesson (which will be about pathfinders)... we're left to see how a bot LEARNS paths. Still following ?

      We saw already that a bot remembers the paths it sees, and those it experiences itself. That's why we need to write a function that will be called every frame, to monitor players and bots. Either we call it in the function that makes the bot see, or we simply cycle through all players at the end of each frame and make the bots in sight update their navigation links. Which method is the best ?

      Well, since anyway we'll need to cycle through all players and call the relatively costy WalkfaceUnder() function for them at least once, better cycle through all players and call WalkfaceUnder() once AND THEN for each player cycle through all bots in sight, than the other way around. We'd need to call WalkfaceUnder() for each player as many times as there are bots in game, if we did it the other way around. Definitely method #2.

      In order to check if a player (or a bot) has moved onto a new walkface, we need to keep track of the walkface it is currently supposed to be on. That's why, supposing we already have a structure that holds some info about our players, we'll just add a pointer to the walkface supporting him to it, and we'll fill it at the end of each frame, when there'll be nothing left to do before returning to the engine. Also, since we'll need to remember if this player has pressed a button or behaved a particular way in order to reach the new walkface (stood still on an elevator, opened a door, swimmed, etc...) we can add an integer in which each bit will represent a special type of reachability, that we'll set once we detect the player is opening a door, swimming, or whatever. When it'll be time to make up a navlink between the previous and the current walkface, we can then store this integer as the navlink "reachability". Not omitting to reset it once it has been stored away, of course.

typedef struct
{
   walkface_t *pFaceAtFeet; // pointer to the last face this player was walking on
   int face_reachability; // type of reachability from this player's last walkface to the new one
   // other stuff below
} player_t;

player_t players[MAX_PLAYERS_SUPPORTED_BY_ENGINE];

      Here's for our player structure declaration. Now, a function that could monitor player moves for bots could look like this (keep your eyes open, kids, for this is the most important function of the navigation learning system) :

void ShowTheWayAroundToBots (edict_t *pPlayer)
{
   // this is the function that makes the bots monitor the player's movement. When a player
   // incidentially calls this function, he builds an information structure about his movement,
   // so that all the bots who can see him can remember that this player passed from one place
   // to another, where and how he did. Typically, each frame a player moves, this function is
   // called upon him, in order to keep track of the "reachability" of his goal (either he needs
   // to climb a ladder, wait on a platform, fall in a pit or anything else), and then, when it
   // is detected that he just reached another walkface, all the bots in sight are told to update
   // their navigation links array so that they remember this path later. I just wasn't feeling
   // like doing heaps and lots of unreliable math at server boot time to build the navigation
   // arrays straight out of the navmesh. Crafty, eh ? =)

   walkface_t *new_face;
   navnode_t *new_node, *node_from;
   int player_index, bot_index, face_index;
   char link_index;

   player_index = ENTINDEX (pPlayer) - 1; // get this player's index (entity indices start at 1)

   // is this player falling fast enough to get some damage ?
   if ((pPlayer->v.flFallVelocity > MAX_SAFEFALL_SPEED)
       && !(pPlayer->v.flags & (FL_ONGROUND | FL_PARTIALGROUND)))
      players[player_index].face_reachability |= REACHABILITY_FALLEDGE; // remember it

   // else is this player moving abnormally fast (meaning he's using the longjump) ?
   else if (pPlayer->v.velocity.Length2D () > 500)
      players[player_index].face_reachability |= REACHABILITY_LONGJUMP; // remember it

   // else is this player completely surrounded by water (i.e, swimming) ?
   else if (pPlayer->v.waterlevel == 3)
      players[player_index].face_reachability |= REACHABILITY_SWIM; // remember it

   // else is this player climbing a ladder ?
   else if ((pPlayer->v.velocity.z != 0) && (pPlayer->v.movetype == MOVETYPE_FLY)
            && !(pPlayer->v.flags & (FL_ONGROUND | FL_PARTIALGROUND)))
      players[player_index].face_reachability |= REACHABILITY_LADDER; // remember it

   // else if the engine knows a ground entity for this player...
   else if (!FNullEnt (pPlayer->v.groundentity))
   {
      // is this player riding an elevator ?
      if ((pPlayer->v.velocity.z != 0)
          && (strcmp ("func_door", STRING (pPlayer->v.groundentity->v.classname)) == 0))
         players[player_index].face_reachability |= REACHABILITY_ELEVATOR; // remember it

      // else is this player riding a bobbing platform ?
      else if ((pPlayer->v.velocity != g_vecZero)
               && (strcmp ("func_train", STRING (pPlayer->v.groundentity->v.classname)) == 0))
         players[player_index].face_reachability |= REACHABILITY_PLATFORM; // remember it

      // else is this player standing on a conveyor ?
      else if ((pPlayer->v.velocity != g_vecZero)
               && (strcmp ("func_conveyor", STRING (pPlayer->v.groundentity->v.classname)) == 0))
         players[player_index].face_reachability |= REACHABILITY_CONVEYOR; // remember it

      // else is this player riding a train ?
      else if ((pPlayer->v.velocity != g_vecZero)
               && (strcmp ("func_tracktrain", STRING (pPlayer->v.groundentity->v.classname)) == 0))
         players[player_index].face_reachability |= REACHABILITY_TRAIN; // remember it
   }

   // now if the player is standing on some ground...
   if (pPlayer->v.flags & (FL_ONGROUND | FL_PARTIALGROUND))
   {
      // check for the face this player is walking on currently
      new_face = WalkfaceUnder (pPlayer); // get this player's ground face

      // now ensure we know both where the player came from AND where it is right now,
      // and check if this player has just moved onto another walkface
      if ((players[player_index].pFaceAtFeet != NULL) && (new_face != NULL)
          && (new_face != players[player_index].pFaceAtFeet))
      {
         // cycle through all bot slots to find the bots who have this player in sight
         for (bot_index = 0; bot_index <= gpGlobals->maxClients; bot_index++)
         {
            if (!bots[bot_index].is_active || FNullEnt (bots[bot_index].pEdict))
               continue; // discard unused slots

            if ((bots[bot_index].pEdict != pPlayer)
                && !FVisible (pPlayer->v.origin, bots[bot_index].pEdict))
               continue; // discard this bot if it doesn't have our player in sight

            // find new node player just reached (index is the same as destination face index)
            new_node = &bots[bot_index].PathMemory[WalkfaceIndexOf (new_face)];

            // loop through all the entrypoints the bot knows for this face's node
            for (link_index = 0; link_index < new_node->links_count; link_index++)
               if (new_node->links[link_index].node_from->walkface
                   == players[player_index].pFaceAtFeet)
                  break; // break when entrypoint to this face already exists in bot's nav brain

            // it's time to update this bot's path memory

            // if there are already too much navlinks for this node, erase one
            if (link_index == 8)
               link_index = RANDOM_LONG (0, 7); // pick a slot at random

            // find the starting face index (it's the same as the navnode index) and find the
            // starting node (it's the node at the starting face)
            face_index = WalkfaceIndexOf (players[player_index].pFaceAtFeet);
            node_from = &bots[bot_index].PathMemory[face_index];

            // write the new navlink (destination, reachability, origin). This is written
            // directly in bot's memory since we linked the pointer to there just above.
            new_node->links[link_index].node_from = node_from;
            new_node->links[link_index].reachability = players[player_index].face_reachability;
            new_node->links[link_index].v_origin = pPlayer->v.origin;

            // have we found NO previous entrypoint for this face ?
            if ((link_index == new_node->links_count) && (new_node->links_count < 8))
               new_node->links_count++; // this node holds now one link more (up to 8)
         }

         players[player_index].face_reachability = 0; // reset his walkface reachability now
      }

      // remember the face this player has been standing on for the next call of this function
      if (new_face != NULL)
         players[player_index].pFaceAtFeet = new_face; // but discard NULL walkfaces
   }

   return; // finished the one-man show :)
}

      Here we are. Not too complicated ? Well, that's all that is needed. By calling such a function every frame for every player, you make your bots watch the players' movements and learn from them. Each of your bots has now the ability to learn paths INDIVIDUALLY, and the ability to know its walkable space EXACTLY. You've built a 3D navmesh optimised with a 2D lookup table out of the map's BSP file, and you've inferred your bots with knowledge of their spatial environment. You do realize not all game companies can boast of having such features implemented in their *comercial* game AI, right ?

      Final fun kids, you're left to write functions that will display visually the walkfaces, navnodes and navlinks your bots are walking on, with colorful beams. I suppose it's a piece of cake for you ? Well, have fun now. The lesson is over.

      In the next chapter, we'll try to tame another wild beast : the parallelized, time-sliced A* pathmachine. Don't be afraid, It'll be tied and it can't bite.

Pierre-Marie Baty - <pm@bots-united.com>
Source code presented here adapted with simplification from the RACC project (http://racc.bots-united.com)
Open source, no copyright except what is owned by Valve Software of the Half-Life SDK.