The margin of error is used to take into account any reactive behavior the
bot undertakes during its journey, such as veering to the side to avoid
another bot or jostling in doorways and narrow passages. This margin
should be small enough to prevent your agents from looking dumb, yet
large enough to prevent the agents from frequently requesting new paths
from the path planner.
NOTE You can observe bots getting stuck if you run the Raven_BotsGetting
Stuck demo. In the demo several bots are exploring the map. An arrow is drawn
from their current position to their current destination. As they jostle around the
doorways some of them will get stuck, a few of them permanently.
This chapter has presented many methods and techniques related to path
planning. Most of the ideas have been incorporated into the Raven game
framework so you can see them working in situ and examine the code to
see how it all works together. Please note that this is only by way of exam-
ple. You wouldn’t normally use all these techniques at one time. Just use
whatever your game demands and no more.
Practice Makes Perfect
When moving to a target position, the Raven bots fill the gap created by the
time required to undertake a graph search by seeking to that position. This
is cheap and easy to implement, but in games with hundreds of agents or
huge navgraphs the delay may be too long for this approach to be effective.
Given too long a delay, the agents will start walking stupidly into walls and
other obstacles. Also there are times when the best path to a position
involves walking away from, or perpendicular to, the target before bending
back around to face it. See Figure 8.30.
376 | Chapter 8
Figure 8.30. Problem situations
Seeking in situations like this for any length of time is a definite no-no.
What agents must do instead is determine a partial path to the target posi
tion. That is to say, the A* algorithm must be modified to return the path to
the node closest to the target after a user-defined number of search cycles
or search depth has been reached. The agent can then follow this path until
the complete path is created. This will produce much better-looking behav
ior and reduce the chances of making the agent look stupid.
Your mission, should you choose to accept it, is to modify the
PathPlanner project to produce partial paths between the source and target
Practical Path Planning | 377
This page intentionally left blank.