Pierre-Marie's navmesh tutorial
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".
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 :
Would it be impossible to think rather this way ? I need to :
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 :
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 ?
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 :
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.
Typically 2 solutions, as usual:
We'll definitely want the 2nd solution, don't you think ?
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 ?
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.mins and dmodels.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.
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...
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.
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 :
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:
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 ?)
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...
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.
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.
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 :
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 :
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.
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) :
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 - <email@example.com>