Features

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

Vehicles

Arbitrary vehicle pathfinding is an order of magnitude more difficult then traditional bipedal pathfinding. Humans can turn on a dime, whereas vehicles have a turn radius. Humans follow the same rules regardless of orientation, whereas vehicles act differently in drive and reverse. Humans can stop on a dime, whereas vehicles skid. Humans do not tip over when running too fast, whereas vehicles can roll.

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.

______________________________________________________

[Back To] Getting Good Data

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service