GDC 2002: Polygon Soup for the Programmer's Soul: 3D Pathfinding
September 4, 2015
Press Releases
September 4, 2015
PR Newswire
View All

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

GDC 2002: Polygon Soup for the Programmer's Soul: 3D Pathfinding

April 5, 2002 Page 1 of 3

One of the fundamental goals of an AI system is to avoid making the unit appear "dumb." At the root of this challenge lies one of the hardest problems to overcome efficiently and believably: pathfinding. Today, 3D graphics and sound technologies begin to reach a level of realism that is easily destroyed by seeing an AI unit walk face-first into a solid wall, slide along the perimeter and ultimately get stuck on an errant polygon. Traditional technologies that worked well for games a few years ago fall apart when faced with the complexity of today's 3D environments.

This paper addresses the pitfalls of attempting to pathfind the arbitrary world we call "polygon soup." It covers automatic data generation and compression, a run-time distributed algorithm, organic post-process modifiers, and solutions for tricky situations such as doors, ladders, and elevators.

Where to Get Good Data

There are numerous good algorithms for determining a path given a connectivity graph. For simple 2D games the connectivity graph was a side affect of the tiling system used to create the map. For 3D games, especially those constructed from arbitrary geometry, no such simple solution exists. So the problem exists, where do we get good data?

Imagine importing the outline of a stained glass window into your favorite paint program. The image consists of large, irregularly shaped regions of pure white space. Your task: color each of these regions to complete the stained glass window. Now, which tool is best for the job, the pencil (which would require you to color each and every pixel independently) or the paint bucket (which can recursively flood a whole region with color)? Should be an easy decision, right? So why is it that many level designers are forced to manually populate their levels with numerous pathfind nodes, sectors, grids, zones, planes, subdivisions, portals or whatever whoseewhatsit is popular that day? Now, visualize an automated system that could discover all possible traversable locations in your most complicated environment with a single click of the mouse. Can you picture it? Great! Let's build it.

To solve this Herculean task we'll borrow a simple idea from our paint program metaphor, namely, the recursive flood fill. The only tools we'll need are a good collision detection system and the knowledge of a single point in the polygon soup where a unit can stand. The algorithm works as follows:

Use the collision detection system to determine if the unit can exist at the start point. If the area is valid, add that point to a list. This will be our task list. Now, loop over all the entries in the task list (which is currently one). For each entry in the list, simulate the unit taking a step in each of the four cardinal directions (north, east, south, and west). If one of these points passes the collision check, add it to the task list. Retain the connection information between these two points (point A can walk to point B).

There, you're done, once this algorithm finishes you'll have a complete connectivity graph of the current game level. Of course there are always details…

Detail 1: Of shapes and areas.
When doing the collision checks we aren't really dealing with points, but volumes. This is because we are attempting to simulate an object, and objects have volume. We need to decide what volume yields the best results. Different collision systems use different representations for an object's collision volume; some use cylinders, some spheres, while others use boxes. In order to cover space continuously, without leaving gaps between areas, we'll use boxes.

 Circular shapes form gaps when arranged adjacently, while boxes cover space continuously.

At this point you should begin to see the familiar form the data is taking, a grid! However, this isn't the simple 2D grid you may be imagining. If you ignore the elevation of each box, the grid is uniform, however because we simulate walking from one grid cell to the next, it can take us up or down slopes, across bridges and over and under overpasses. This means that for any given coordinate on the "plane" there can exist more then one grid cell (consider elevation). A good example of this is a spiral staircase. The algorithm will fill up and around each turn of the staircase as if it were on a flat plane, however if you stood at the top and cast a ray down the course of the staircase you would encounter a grid cell at every turn of the stairwell.

Detail 2: Size does matter.
It is very important that the cell size is appropriate for the object pathfinding the level. Too large and the object will not be able to path through doors that are not orthogonal, too small and you'll find your computer running out of RAM before it finishes flood filling. As a suggestion, make an axis-aligned bounding box from the object's collision volume. This box should completely contain the object regardless of its orientation. Now, divide the X and Y dimensions by 2, thus giving you a "tall, skinny" box.

 A good sized cell is generally a quarter of the object's maximized collision box.

The reason for this derives from the fact that the grid is axis-aligned (non-rotated). If a door or other passageway is rotated, and during game play the object fits through the door because it rotates as well, then a non-rotated pathfind cell will collide with the door.

Detail 3: It's not what you know, but who you know.
At a minimum, each cell of the grid only needs to know which neighbors are traversable. This can be accomplished via a simple data structure that has four pointers, one to each of its neighbors. If a pointer is NULL, that direction cannot be traversed.

class CPathCell
{
.
.
.
CPathCell * NorthCell;
CPathCell * SouthCell;

CPathCell * EastCell;
CPathCell * WestCell;
};

This simple data structure completes a connectivity graph - we now have enough information to pathfind between any two cells in the level.

Detail 4: No bonus for extra work.
Be careful to avoid reprocessing cells that you already know are traversable. For example, we start with cell A and successfully simulate stepping to cell B. When it comes time to process cell B, we already know cell A has been processed so it should not be added back into the list. However, we still need to simulate stepping from cell B to cell A - just because we can walk from A to B does not guarantee we can walk from B to A (i.e. stepping from A to B takes you off a small cliff).

Detail 4: Isn't this a lot of memory?
Simply put, yes it is. Therefore it is extremely important to keep your data structures as tight as possible. For instance we've seen upwards of 10 million cells generated for a large level.

Keep in mind that this is a preprocess step, we're simply generating the data. Before we can use this data it must be compressed into a format that is feasible for run-time application.

Doors, Elevators, and Ladders - Oh my!

It is extremely satisfying to give an AI the command, "Goto (x,y,z)", and watch as the unit performs a complex series of steps. For example, given a single destination, an AI could walk to the front door of a building, open the door, walk to the elevator, wait for the elevator to arrive, take the elevator to the roof, exit the elevator, walk to the ladder at the base of the tower, and climb to the top of the tower.

Even more satisfying is to have this information about the "teleport" mechanisms automatically detected during the data generation step. To arrive at this goal, we'll need to know the location of each door, elevator, ladder, or other teleport mechanism, and it's enter and exit zones. The algorithm now works as follows:

During flood fill, grab an unprocessed cell from the task list. Perform the simulation as before, if the cell passes, check to see if it is completely contained within the enter zone of one of the teleport mechanisms. If this cell is indeed inside an enter zone, create a new cell in the center of the exit zone and perform a collision check to ensure it is safe to stand there. If the new cell passes this test, add it back into the task list - this will ensure the simulation continues on the other side of the mechanism.

Avoid the temptation to store the connection between the "enter" cell and the "exit" cell. This extra data will unnecessarily bloat the size of each one of the cells in your 10 million cell flood fill. The connection information can easily be determined after the flood fill is complete. This issue is addressed later when discussing data compression.

What to do if you can't devote 500MB of RAM to Pathfind

Now that we have a nice simple algorithm for generating the connectivity graph of a level, it is time to start inspecting the data. Let's say each cell requires approximately 50 bytes of data, and we've generated somewhere on the order of 10 million cells, that means we have 500MB of pathfind data. When problem solving, the more data the better, but half a gigabyte is just plain ridiculous! It's time to compress the data down to something more manageable.

Let's examine a simple scenario. If cell A connects to cell B, and cell B connects to cell A, then do we really need two cells? No we do not; we can combine the two cells into a sector and throw away the original cells. We define a sector to be a convex polyhedron of freely traversable space. Given our particular dataset and purpose, a box is the most effective convex polyhedron.

To expand on this compression scheme, consider the following diagram.

Cell A connects to B and C, cell C connects to A and D, cell D connects to C and B, cell B connects to D and A. Here, we can combine all four cells into a single sector and discard the original cells. To generalize, we can combine any rectangular set of contiguous, connected cells into a single sector. Ultimately, we'll want to compress all the cells into sectors. The sector then becomes the basic data type used during runtime to solve a path.

Once a sector is generated, it is necessary to retain the connection information its composite cells originally contained. To accomplish this, retain the edge cells and discard the interior cells of the sector. These edge cells share connection information with cells in other sectors, in effect, linking sectors together.

 To retain a sector's connection data, keep the edge cells.

After all the sectors have been built, you can then combine a sector's edge cells that share a common destination sector into a portal. We define a portal to be a connection between sectors; i.e. to get from sector A to sector B walk from your current position in sector A through the AB portal. The portal's physical shape is the bounding volume of its composite edge cells.

 Portals are connections between two sectors.

Portals can be one-way or two-way. If the edge cells in sector A are connected to the edge cells in sector B, and the same cells in sector B are connected to the sector A cells, then the portal is two-way. Otherwise the portal is one-way.

Once the portal is created, it is added to the list portal-list of the sector that contained the edge cells. If this is a two-way portal, it is added to the portal-list of both sectors.

Doors, Elevators, and Ladders - Again!

Earlier we discussed how to flood fill across teleport mechanisms such as doors, elevators and ladders. Now that we've converted all our cells into sectors and portals, it's time to incorporate information about these mechanisms so that our AI can use them.

To build a portal for a given mechanism, first intersect its entrance and exit zones with the existing pathfind sectors. If the intersection test yields at least one sector for the entrance and exit zones then we can create a portal between the two. The entrance portal's bounding box is the volume created by intersecting the entrance zone with the pathfind sector. The exit portal's bounding box should follow the same formula.

Store any specific information about the mechanism the AI will need to know in order to operate it in the portal. For example, if a door is locked, save the type of key that's needed to open the lock. When the path solver is attempting to resolve the path, it can ignore the portal if the AI is not carrying the required key.

Page 1 of 3

### Related Jobs

IPKeys Technologies — Eatontown, New Jersey, United States
[09.04.15]

Sr. Game Programmer
OMAX Corporation — kent, Washington, United States
[09.04.15]

Senior Programmer (15-238-GM)
Disruptor Beam, Inc. — Framingham, Massachusetts, United States
[09.04.15]

Unity/DevOps Engineer
UBER Advanced Technologies Center — Pittsburgh, Pennsylvania, United States
[09.04.15]

SOFTWARE ENGINEER -- SIMULATION