//source node of e1 to the destination node of e2. If the agent can move
//between those positions then any edges between e1 and e2 are
//replaced with a single edge.
while (e2 != path.end())
//check for obstruction, adjust and remove the edges accordingly
if ( m_pOwner->canWalkBetween(e1->Source(), e2->Destination()) )
e2 = path.erase(++e1, ++e2);
e1 = e2;
You can see both of these algorithms in action by running the
NOTE If your map makes use of graph edges annotated with special behav-
iors or if your agents have other constraints like a restricted turning circle, the
smoothing algorithms must be modified to prevent deletion of important edges.
See the Raven project source for an example.
Methods for Reducing CPU Overhead
Load spikes take place when the amount of processor cycles required by a
game engine is in excess of the number of cycles available. If a game has
oodles of AI controlled agents running around, all able to request paths at
any time, then load spikes can occur when too many of them simulta
neously request searches. When this happens, the fluid flow of the game
will be interrupted as the CPU attempts to keep up with the demands put on
it, thus creating a jerky, stuttering motion. Obviously this is a bad thing and
should be avoided wherever possible. The next few pages will be devoted
to methods that lessen the likelihood of load spikes by reducing the
per-update overhead of path planning requests.
If your game environment is static and you have memory to spare, a good
option for lessening the CPU load is to use precalculated lookup tables,
enabling paths to be determined extremely quickly. These may be calcu
lated at any convenient time, such as when a map is read from file or
Practical Path Planning | 359
Paths as Nodes or Paths as Edges?