学步园

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.

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.