## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Ü
NOTE It’s worth mentioning that a kind of two-tiered hierarchical path
-
finding is implicit when a world is partitioned using a navmesh. (Note how
the high-level graph in Figure 8.25 closely resembles the navmesh shown in
Figure 8.3).
Getting Out of Sticky Situations
A problem players of computer games witness far too regularly is that of
NPCs getting stuck. This can happen for all sorts of reasons. In particular,
it occurs frequently when an environment contains lots of agents and the
geometry has bottlenecks. A bottleneck could be a small space between
two obstacles, a narrow doorway, or a tight corridor. If too many agents
simultaneously attempt to navigate a bottleneck, then some of them may be
pushed backward and end up wedged against a wall or obstacle. Let’s have
a look at this happening with a simple example.
Figure 8.26 shows a bot — we’ll call him Eric — following the path A
to B to C. It also shows a number of other bots traveling in the opposite
direction. Eric is in for a nasty surprise.
In Figure 8.27, Eric has reached waypoint A so it’s removed from the list
and B assigned as the next waypoint. Unfortunately, as this happens, the
other bots arrive and start to jostle Eric back through the doorway.
In Figure 8.28, Eric has been pushed all the way back out of the doorway,
but he still keeps seeking to waypoint B. Silly old Eric.
374 | Chapter 8
Getting Out of Sticky Situations
Figure 8.26
Figure 8.27
Finally Eric ends up wedged against the wall, struggling furiously, still
hopelessly trying to seek to his next waypoint as shown in Figure 8.29.
Tsk, tsk.
Obviously we don’t want this sort of thing to happen, so any AI worth its
salt should make regular tests for such situations and plan accordingly. But
how to do this? Well, one way is for the agent to calculate the distance to
its current waypoint each update step. If this value remains about the same
or consistently increases, then it’s a fair bet the agent is either stuck or
being pushed backward by the separation force from neighboring agents.
Another way is to calculate an expected arrival time for each waypoint and
replan if the current time exceeds the expected. This is the approach
adopted in Raven. It is very simple to implement. Whenever a new edge is
pulled off the path, the expected time to traverse it is calculated as follows
(in pseudocode):
Edge next = GetNextEdgeFromPath(path)
//in a simple navgraph the edge cost is the length of the edge
ExpectedTimeToReachPos = next.cost / Bot.MaxSpeed
//factor in a margin of error
MarginOfError = 2.0;
ExpectedTimeToReachPos += MarginOfError;
Practical Path Planning
| 375
Getting Out of Sticky Situations
Figure 8.28
Figure 8.29

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required