| Pathfinding and the Art of Tweaking |
|
"There's an art to tweaking." This is one of my favorite quotes from Josh Eustis. Josh did the sound effects and music for Cylindrix and Dead Reckoning, two games for which I was the AI programmer. Josh is a local Techno musician whose studio was located in Goldtree's office during the development of Dead Reckoning. It was a funny contrast: a perfectly groomed stylish DJ hanging around with a bunch of nocturnal pizza-eating game developers. He was fun to have around because he had an amazing command of the English language, complete with slang. Although his "tweaking" comment was in reference to music, it applies to game AI as well. There are several components of the Dead Reckoning AI: the state machine, the "motor skills" (movement), memory, knowledge of the state of the 3D world (sensory), and finally pathfinding. All of these components deserve special attention in their own right, but in this article I will focus on the 3D pathfinding. The reason I focus on this is that I do not believe I have ever seen a game other than Dead Reckoning approach this problem. Descent2 is the only one I can think of, and it is essentially limited to navigating tunnels (only 1 or 2 possible exits and not too many obstructions in the rooms). Before getting into the hairy details of true 3D pathfinding, I will explain how I avoided it entirely in my first game. Cylindrix: 3D Pathfinding done lite For the first game, Cylindrix, the pathfinding was fairly straightforward. All of the cylinders were mathematically generated, and followed a few basic rules. All of the obstructions were solid objects attached to the surface of the cylinder that grew thinner towards the center of the cylinder and terminated at a flat top. All of the geometry was very exact, and there were no tricks. This uniform geometry is why we initially called all of the obstructions "pylons". Because of the geometry we were able to implement a nice hack...we broke the world up into a series of 2D planes. At any time, the AI vehicle would be in only one plane, and any destination by its nature would be in an unobstructed "chunk" of the world. Because of this, the AI could actually move around in this plane and reach any unobstructed point in the world. In addition, the world was fairly small, so the overhead required to compute a path in these 2D planes was negligible. I was able to get away with a very inefficient pathfinding algorithm that I made up. We avoided adding "floating pylons" so we could continue using this simplistic pathfinding model.
Here we see a simplified Cylindrix level. Note how all of the geometry is attached to the cylinder and there are no "floating" objects.
Here the pylons are projected onto a 2D plane and the 3D space is "sliced" into a series of 2D grids, perfect for a 2D pathfinding algorithm.
Once we determine which plane the AI vehicle is on, we can simply use that "slice" of the 3D grid. From there we can use a 2D pathfinding algorithm. Note that the depth of the destination is irrelevant since the game was designed such that an obstruction cannot be between two vehicles in the z direction.
This demonstrates an important point: The way you model your worlds will greatly affect the amount of time necessary to implement an acceptable pathfinding scheme. I don't necessarily mean the 3D modeling, but more the game model. Is your game a first person 3D shooter? If so you may be able to get away with strictly 2D pathfinding if you set up the world correctly. If your character is essentially moving on a 2D plane (ala Doom), it is a prime candidate for 2D pathfinding. This is one place where the tweaking comes in. In order to maintain this 2D-ness you may have to build contrived levels to avoid confusing the AI. An example would be organizing your level into a series of 2D planes with only a few ways to move between them (staircases). I imagine that a whole article could be written on keeping 3D levels "logically" 2D for the sake of the AI. So by the end of Cylindrix I thought I was the pathfinding master...the AI never got "stuck" like so often seen in games, and I was extremely proud of this. There was nowhere that the AI couldn't find you. You couldn't hide. To most people this may seem like a no-brainer, but avoiding "getting stuck" is (IMHO) the most difficult problem to address when dealing with real time 3D game AI.
Dead Reckoning: Pathfinding on steriods Enter Nicholas Marks. I spent a several months away from Goldtree during the infancy stages of the new game. The 3D programmer, Tony Thibault, created an entirely new engine for the new game. It supported arbitrary 3D geometry with texture mapping and all of the cool graphics things people said were lacking in Cylindrix. Early on I warned Nick about the way my AI worked...I asked him to keep the levels "2D" and avoid putting important things (like the energy square powerup) off of the surface of the cylinder. By the time I was brought in to implement the AI, the levels had become the most complex assortment of floating shapes I had ever seen, and the energy squares were placed anywhere from in the middle of the cylinder to inside of other objects! I had to admit that the levels looked awesome, and there was no way I was going to convince anyone to simplify them for the sake of the AI. So I set about the task of porting the Cylindrix AI over to the new game. For the most part, I was able to port all of the components of the Cylindrix AI over to Dead Reckoning with minor changes...they essentially worked. However, I ran in to a major problem when using my old pathfinding code in the new game. Before I discuss these problems I will address the data structures I use for the AI to interface with the 3D world. I find it undesirable to directly access "game data" from the AI. I avoid accessing any 3D data structures, vectors, or entity information directly from the AI. I have middleman functions that loop through data in the 3D world and copy the data into a format easily digestible to the AI. This shields the AI from changes in the internal representation of game data, and also aids in porting the AI to another game. There are many different places I use this idea in the state machine or whatnot, but I will explain specifically how I use it for pathfinding. All of the pathfinding algorithms I have seen use a grid-based data structure. All of the algorithms mentioned in the October 1996 Game Developer article "Smart Moves: Intelligent Path-Finding" use a grid. The Dead Reckoning engine deals with arbitrary 3D objects, and does not readily lend itself to a grid representation. The first chore in pathfinding was converting from an arbitrary 3D world to a nice 3-dimensional array of grid "blocks" for the AI to work with. Initially, I had wanted to dynamically compute whether a particular "block" was filled or empty. Unfortunately, doing this proved to be far too expensive. Our next idea was to compute a look-up table when the game started. Computing the lookup table ended up taking several minutes, which is unacceptable load time by any standards. Finally, we made every level file have a pre-generated grid file for the AI to use, and if the grid file is not found it would generate a new one (taking several minutes, but this is better than no pathfinding for the AI!). The basic algorithm we used for generating the grid is as follows: for( x in gridxResolution ) {
} (In retrospect it would have been much more efficient to loop through all of the polygons and "project" them into an empty grid, but we were under a deadline and this was the most obvious solution) In the above code, the IsObjectInBlock() function first uses a mathematical formula to calculate what the bounding box for the grid[x][y][z] block would be, based on the x,y,z coordinates of the block and the x,y,z dimensions of the 3D world, it then loops through all of the polygons in the passed 3D object to test whether they intersect this bounding box over a certain amount. If any polygons from any object intersect with a particular block in the grid, a "1" is stored there. If not, a "0" is stored there. I really had to tweak the x,y, and z resolutions of the grid. If they are too low, and the resolution of the grid is too low, the geometry of the world will be inadequately represented, and there will be impassable areas where there should be holes, and sharp corners of large objects may be omitted because they do not intersect a block enough, which would make the AI incapable of "seeing" the obstruction. If they are too high and the resolution increases, while the world is more accurately represented, computation of a path becomes extremely costly. What these values should be depends on the complexity and size of the world, and also whether the evil level designer hid powerups in the middle of another 3D object with tiny entrances! 3D "Block" primitives Once the problem of creating a 3D grid representation of the world was solved, we wrote some primitives for relating these blocks to the real (simulated) world. It is important for the AI to use a clearly defined interface whenever dealing with game data. It should never access the game data directly. I cannot reiterate this enough, because it abstracts the game engine for the AI, allowing it to handle changes in data representation, or even a whole new engine. A few of these primitives are noted below. int BlockOccupied3D( Block3D block ); This is the function used by the pathfinding algorithm to determine whether a particular node is occupied. This function simply looks in the grid data structure that was loaded from the grid file for the level. float BlockDistance3D( Block3D block1, Block3D block2 ); I use this function instead of the traditional " Manhattan Distance" in the A* algorithm (see below). This function computes the simulator world 3D center points of the two blocks, and then computes the distance between them. int BlockVisible3D( Block3D block, Vector vector ); I use this function when actually following the path to make the AI move more smoothly, see below. The A* pathfinding algorithm I used the A* algorithm for pathfinding in Dead Reckoning. I chose this algorithm because the article I mentioned earlier from Game Developer said it was a good performer in a variety of different situations. I've never seen any explanation of how to use it with a 3D grid, but making it work in 3D was fairly straightforward. The earlier Game Developer article has a description of the A* algorithm, but I will summarize it here for those of you who do not have that issue. The algorithm moves through the grid data structure from the given starting point to the given destination. Each "step" it makes it stores in a node. In this node data structure is stored the coordinates of the current block, the distance to the goal from this block, and this block's parent block. As the algorithm moves towards the destination, it stores these nodes into two stacks: the open and the closed stack. Once the destination block is reached, we traverse upwards through the nodes (using the pointer to the parent nodes) and we have our path! Insert the start point onto the open stack while( nodes left on open stack ) {
} In this algorithm the tricky part is actually in the InsertSorted() method of the openstack. You sort the nodes by their distance to the destination. This is the most important part of the algorithm, because the order in which the algorithm picks nodes to search is based on this sorting. Traditionally, (at least in the examples I've seen) you use the Manhattan Distance, which is the distance in grid blocks from the destination. I tweaked this distance function, and instead used the 3D distance of the centerpoint of the current block to the destination (using BlockDistance3D). For whatever reason this made the algorithm work better in my case...it consistantly searched less nodes than using the manhattan distance. A* + 5 AI's + Huge world = Expensive Just getting A* to reach the destination in 3D was a triumph, but that was only the tip of the iceberg. I ran into several performance issues almost immediately: Huge open lists, all 5 AI's computing a path at the same time, and finally actually following the path. The sheer number of nodes you must search to reach a destination in 3D is huge. The one thing you want to avoid is large, flat planes in the world that have important stuff on the other side of them. This causes a huge "ball" of nodes on one side of the plane (see deadreck3.jpg). As you linearly increase the size of a plane, you square the number of nodes you must search to get around it. (I never did the math so I may be off, but let's just say it increases really fast). When playing Dead Reckoning, you may notice that the Guardian cylinder is chock full of large flat planes with pylons in between them. Let's just say that the level designer liked to challenge me :) I quickly realized that I had to come up with some sort of tweak to speed up pathfinding. I basically implemented time-sharing of the pathfinding algorithm for the different AI's. I created a semaphore variable that one of the AI's could lock to keep the other AI's from using the pathfinding while it was computing a path. Below is a snippet of psuedocode demonstrating this concept: for( i in loop through all AI's ) {
} bSemaphore = 0; This allows only one AI to compute one path per frame. This keeps all 5 AI's from trying to compute a path in the same frame, which could potentially cause an erratic frame rate. In addition, I only allow the pathfinding algorithm a certain number of nodes it may process per frame. If the node list gets too large, it waits for the next frame to continue finding the path. This helps reduce the cost of a large number of nodes being processed. As a last resort for when the number of nodes gets out of hand, I have a cap on the number of nodes allowed open when computing a path. If this cap is hit without reaching the destination, the AI will simply fly straight towards its destination, hoping for better luck the next time around. Surprisingly, this almost never happens...or if it does it's when the user isn't looking ;) Once again, in order to get acceptable behavior out of the pathfinding I resorted to tweaking several max value variables. If the "max nodes per frame" is too low, it takes too long (human time) to compute a path, and AI's have to sit in line while the one is computing a path. If the value is too high, sporadic pausing can occur when the AI is attempting to compute a particularly hopeless path. If the node cap is too high, the time it takes to simply add a node to the open list can get huge, but if the value is too low the AI will be unable to compute more difficult paths. Once the path has been found, the AI must follow it. How this is done depends heavily on how the AI character is allowed to move. There is one trick that I have learned, however, that makes following paths much smoother. Rather than make your AI character physically move to each node in the path, figure out the last unobstructed node in the path. I use the abovementioned BlockVisible3D function to determine this in Dead Reckoning. Because BlockVisible3D is a very expensive function in Dead Reckoning (as visibility tests in 3D often are) I only allow each AI character to increment one node in the path per frame. This avoids calling it hundreds of times in one frame if the path is particularly long and unobstructed until the end. This is plenty fast enough, as it allows the AI to increment roughly 30 nodes in the path per second. Below is some psuedocode describing this (without the restriction on calling BlockVisible3D). LastVisibleNode = FirstNode CurrentNode = FirstNode while( BlockVisible3D( CurrentNode, AIPosition ) {
} //Now we have the node we should be heading towards FirstNode = LastVisibleNode;
Here the red spheres are the obstructions, the blue sphere is the start point, and the pink sphere is the destination. The path curves around the three obstructions. The four white spheres are nodes of the path that passed the visibility test, and the five yellow spheres are nodes that are not visible. The path following algorithm skips the first three nodes, even though it hasn't reached them, because they are visible. It sets it's target node as the last visible node in the path.
Debugging your pathfinding Debugging the pathfinding code was both the most frustrating and fun part of writing the Dead Reckoning AI. It was frustrating because every time I thought I had it solved, the levels would become ever more complex and special cases would pop up (this was invariably in the Guardian cylinder...I still have nightmares about that ankh). What made it so fun though was a cool debugging tool that we put into the engine. Since the 3D grid is a representation of the world, there is no reason that you cannot map a block back into the real world. And that is exactly what we did. In the screenshots of Dead Reckoning you can see a bunch of smiley-faced boxes snaking through the level. This is a graphical representation of where the A* algorithm looked during pathfinding. If you plan on implementing real time 3D pathfinding in your game, I highly recommend graphically displaying your paths in the 3D world. Without this visual aid, I would never have been able to tweak the pathfinding the way I did. This display makes it easy to see areas that the AI is having trouble dealing with, and you can make the choice of either adjusting the pathfinding or adjusting your level. Not only that, but it sure does impress your friends when they see the complex paths the AI has to generate when going anywhere. Tweaking, man, tweaking! Which brings me to my final point. I have developed a very different approach to AI than I started with four years ago. When I started programming Game AI I was "into" genetic algorithms, neural nets and other such "real" AI subjects. Over time I came to realize that it isn't high falootin' learning that people want out of games. People want the illusion of intelligence. It doesn't matter how you arrive at the result, what matters it the appearance of thought. The way you obtain this illusion is through complexity and tweaking. Unpredictability is important. It is important that the AI be capable of doing something that the user isn't expecting. When this happens, the user assumes an intelligent agent is causing the action. If there are enough different stimuli in your AI state machine, and enough different possible actions, you can tweak a believable AI out of it. When I watch people play Dead Reckoning, I love it when they try to hide in the ankh room, assuming that like all other game AI's the computer won't be able to find them, only to have three bad guys swarm into the room and kill them. Over the years people have figured out tricks to beat video games. People memorize patterns in Mortal Kombat, figure out ways to get bad guys stuck behind a corner, figure out that hogging the rocket launcher makes you win every time...people figure out all kinds of patterns. That is what the human mind does best. Good pathfinding nullifies many of the tricks people use to beat AI players in 3D games.
Look where the evil level designer hid the energy powerup! Not only is it an ankh, but it's an ankh in a room with a tiny entrance barely big enough to fit through. How will the poor AI vehicle handle it? The power of A* prevails! However, notice how many nodes were searched to find that entrance!
Here is the same path, but with the unused nodes deleted, what a nice path!
Here is a Dead Reckoning AI vehicle using an old fashioned Cylindrix style path hack. To find something on the surface of the cylinder it uses a "slice" of the 3D grid. (This hacked slice is shaped like a donut, so the curve is logically actually a flat plane to the AI) |
