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

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.

<!-- /* AD rectangle 300x250 */--><!-- /* OpenX Javascript Tag v2.8.1 */--><!-- /* * The backup image section of this tag has been generated for use on a * non-SSL page. If this tag is to be placed on an SSL page, change the * 'http://69.59.137.121/openx/www/delivery/...' * to * 'https://69.59.137.121/openx/www/delivery/...' * * This noscript section of this tag only shows image banners. There * is no width or height in these banners, so if you want these tags to * allocate space for the ad before it shows, you will need to add this * information to the <img> tag. * * If you do not want to deal with the intricities of the noscript * section, delete the tag (from <noscript>... to </noscript>). On * average, the noscript tag is called from less than 1% of internet * users. */-->

<noscript>&lt;a href='http://69.59.137.121/openx/www/delivery/ck.php?n=a5dc8883&amp;amp;cb=INSERT_RANDOM_NUMBER_HERE' target='_blank'&gt;&lt;img src='http://69.59.137.121/openx/www/delivery/avw.php?zoneid=28&amp;amp;cb=INSERT_RANDOM_NUMBER_HERE&amp;amp;n=a5dc8883' border='0' alt='' /&gt;&lt;/a&gt;</noscript>

A complete vehicle pathfinding solution is outside the scope of this paper, however we will present a brief overview that may work for some games.

Firstly, modify the flood fill algorithm to use the bounding volume of the largest vehicle regardless of its orientation. During the run-time path solve, take the turn radius of the vehicle into consideration when evaluating portals. In other words, we know which portal the vehicle is coming from, so discard any destination portals that would cause the vehicle to turn sharper then it is able.

	Take turn radius into consideration when evaluating portals.

Once the path is generated, it may be problematic for a vehicle to follow. This is because orientation is important when dealing with vehicles; however our sector/portal system doesn't implicitly handle this very well. Consider the following diagram.

	Orientation is important when traversing the path. Once in Sector B, the vehicle will never make the turn to Sector C.

In the sector/portal system, the vehicle will beeline from the Sector A's entrance to Sector B. This orients the vehicle in such a way that it will be impossible for the vehicle to make the following turn into the portal for Sector C. However, if the vehicle would "arc" out into Sector A, it would be possible to make both Sector B and Sector C. Unfortunately there is no way of knowing this is required unless we search ahead on the path.

A simple solution to this problem, which works well with the system we've described so far, is to spline the path. However, none of the classical "true" splines will work for this situation; which is fine -- we'll create our own custom curve.

Our goal: create a continuous curved line that will cause the vehicle to arc around corners while still obeying the vehicle's turn radius restrictions. Such a path can be created using only a straight line and the vehicle's turning circle. Unlike "true" splines, this path is not continuous in the mathematical sense, but composed of three distinct continuous parts, which, when placed end-to-end, form a continuous path. The three parts are: the exit curve from the previous point, a straight line from the exit curve to the enter curve of the next point, and the enter curve of the next point. Note: The starting and ending points only contain two parts (there is no previous part for the starting point, nor is there a next point for the ending point). Consider the following diagram:

	The vehicle curve is composed of three distinct parts: the exit curve, a straight line, and the enter curve.

To build this curve, overlay the vehicle's turning circle onto each node of the path. We will assume the optimal center of this turn arc will lie at the point halfway between the angles formed by the (prev_node - curr_node) and (next_node - curr_node) vectors. This causes the actual node point to lie on the perimeter of the turning arc.

For each turning circle on the path, find the "in" and "out" tangent points. The "in" tangent point is the closest point of tangency from the previous point to the turn arc. The "out" tangent point is the closet point of tangency from the next point to the turn arc. Now, simply connect the dots. The path is as follows: straight-line from starting point to the "in" tangent point on the turn arc of the next path node; follow the turn arc to "out" tangent point; straight line from this point to the "in" tangent point of the turn arc of the next path node, etc, etc.

Once finished, this algorithm yields a continuous curve that follows the turning restrictions of the vehicle following the path.

	The vehicle curve ensures the vehicle will not attempt any impossible turns.

Keep in mind that this curve may cause the vehicle to drive outside the "safe" areas of the path, thus potentially colliding with objects along the way.

Conclusion

By taking advantage of a simple flood fill algorithm, we can overcome the Herculean task of automatically generating connectivity data through complex polygon soup. With a few tricks and extensions we can easily incorporate doors, ladders, and elevators; spline the result of the path solve to yield a more organic looking path; dynamically alter the pathfind data to allow the AI to replicate a player's actions; incorporate innate waypaths to force a specific behavior from the AI; and distribute the run-time path solve over multiple frames to balance the CPU load.

Special thanks to Eric Cosky for the original concept of the flood fill algorithm, a brilliant idea that proves the worth of brainstorming with a friend before jumping into a complex problem. Also, thanks to Colin Mclaughlan for suggesting the concept of dynamic temporary "jump" portals.