|
 Features
Path-Finding
on the Move
The typical
problem in path-finding is obstacle avoidance. The simplest approach to
the problem is to ignore the obstacles until one bumps into them. The
algorithm would look something like this:
while not at the goal
pick a direction to move toward the goal
if that direction is clear for movement
move there
else
pick another direction according to
an avoidance strategy
This approach
is simple because it makes few demands: all that needs to be known are the
relative positions of the entity and its goal, and whether the immediate
vicinity is blocked. For many game situations, this is good enough.
Different obstacle-avoidance
strategies include:
- Movement
in a random direction. If
the obstacles are all small and convex, the entity (shown as a green
dot) can probably get around them by moving a little bit away and trying
again, until it reaches the goal (shown as a red dot). Figure
1A shows this strategy at work. A problem arises with this method
if the obstacles are large or if they are concave, as is seen in Figure
1B-the entity can get completely stuck, or at least waste a
lot of time before it stumbles onto a way around. One way to avoid this:
if a problem is too hard to deal with, alter the game so it never comes
up. That is, make sure there are never any concave obstacles.
- Tracing
around the obstacle.
Fortunately, there are other ways to get around. If the obstacle is
large, one can do the equivalent of placing a hand against the wall
and following the outline of the obstacle until it is skirted. Figure
2A shows how well this can deal with large obstacles. The problem
with this technique comes in deciding when to stop tracing. A typical
heuristic may be: "Stop tracing when you are heading in the direction
you wanted to go when you started tracing." This would work in many
situations, but Figure
2B shows how one may end up constantly circling around without
finding the way out.
- Robust
tracing. A
more robust heuristic comes from work on mobile robots: "When blocked,
calculate the equation of the line from your current position to the
goal. Trace until that line is again crossed. Abort if you end up at
the starting position again." This method is guaranteed to find a way
around the obstacle if there is one, as is seen in Figure
3A. (If the original point of blockage is between you and the
goal when you cross the line, be sure not
to stop
tracing, or more circling will result.) Figure
3B shows the downside of this approach: it will often take more
time tracing the obstacle than is needed, making it look pretty simple-minded-though
not as simple as endless circling. A happy compromise would be to combine
both approaches: always use the simpler heuristic for stopping the tracing
first, but if circling is detected, switch to the robust heuristic.
 
Looking Before You
Leap
|
|
|
|
|
