O'Reilly logo

Programming Game AI by Example by Mat Buckland

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

//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()) )
{
e1->SetDestination(e2->Destination());
e2 = path.erase(++e1, ++e2);
e1 = e2;
--e1;
}
else
{
++e2;
}
}
++e1;
}
}
You can see both of these algorithms in action by running the
Raven_PathSmoothing demo.
Ü
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.
Precalculated Paths
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?
created by the map editor and stored along with the map data. A lookup
table must include routes from every node in the navgraph to every other
node in the navgraph. This can be calculated using Dijkstra’s algorithm to
create the shortest paths tree (SPT) for every node in the graph. (Remem
-
ber, the SPT is a sub-tree of the navgraph rooted at the target node that
contains the shortest path to every other node.) The information is then
extracted and stored in a two-dimensional array of integers.
For example, given the graph shown in Figure 8.19, the corresponding
lookup table is as shown in Figure 8.20. The entries in the table show the
next node the agent should travel to on the path from start to destination.
For instance, to determine the least cost path from C to E, we cross-
reference C with E, giving node B. Node B is then cross-referenced with
the destination to give D, and so on, until the table entry is equivalent to
the target node. In this instance, we get the pathC-B-D-E,which is the
shortest path from C to E.
360 | Chapter 8
Paths as Nodes or Paths as Edges?
Figure 8.19. A simple graph
Figure 8.20. The shortest paths lookup table
for the graph shown in Figure 8.19
The source code to create such a table can be found in the file common/
graph/HandyGraphFunctions.h. It will create an all-pairs lookup table for
any graph type with an interface similar to
SparseGraph. It looks like this:
template <class graph_type>
std::vector<std::vector<int> > CreateAllPairsTable(const graph_type& G)
{
enum {no_path = -1};
//create a 2D table of elements all set to the enumerated value no_path
std::vector<int> row(G.NumNodes(), no_path);
std::vector<std::vector<int> > shortest_paths(G.NumNodes(), row);
for (int source=0; source<G.NumNodes(); ++source)
{
//calculate the SPT for this node
Graph_SearchDijkstra<graph_type> search(G, source);
std::vector<const GraphEdge*> spt = search.GetSPT();
//now that we have the SPT it's easy to work backward through it to find
//the shortest paths from each node to this source node
for (int target = 0; target<G.NumNodes(); ++target)
{
if (source == target)
{
shortest_paths[source][target] = target;
}
else
{
int nd = target;
while ((nd != source) && (spt[nd] != 0))
{
shortest_paths[spt[nd]->From][target]= nd;
nd = spt[nd]->From;
}
}
}//next target node
}//next source node
return shortest_paths;
}
Precalculated Costs
Sometimes it’s necessary for a game agent to calculate the cost of traveling
from one place to another. For example, together with other features, an
agent may factor in the cost of a game object when deciding if it wants to
pick up that item. A search to determine these costs for each item type each
AI update step will be very expensive if the navigation graph is large
Practical Path Planning | 361
Paths as Nodes or Paths as Edges?

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

Start Free Trial

No credit card required