Game Development Reference
In-Depth Information
one node in a graph. The lines connecting the nodes, called edges of the graph,
have costs associated with them. A roadmap showing only the distance between
cities is a familiar example of this kind of graph; the roads are drawn as simple
straight lines, and the cities are drawn as circles. Our discrete computer-game
world can be modeled as a graph like this. Outside of navigation, our game may
have a very finely detailed and continuous definition, but for navigation purposes
there are powerful motivations for minimizing the number of nodes in the graph.
A* is going to search for a path through the nodes, and having fewer nodes yields
a faster search.
As long as certain givens remain true, A* will produce the lowest-cost path
between the two nodes if any legal path exists. So what are the certain givens
about A* that need to remain true? The big one is the heuristic upon which A*
depends. A* uses a heuristic to make decisions using imperfect data. Perfect data
would be expensive to compute, and much of it would be thrown away. The
heuristic in A* tells the algorithm that from any point in the graph, the distance
to the goal is at least a certain amount. Of the two core concepts in A*, this is
the estimate part. For driving on roads, a good heuristic is the direct straight-line
overland distance to the goal.
There are two major requirements for a good heuristic. The first is that it needs to
be admissible, and the second is that it needs to be as close as possible to the
actual distance. An admissible heuristic is one that is never larger than the actual
distance.
As an example, imagine that our heuristic was the direct straight-line overland
distance. Because driving is restricted to roads, the actual path will generally be
longer than the heuristic. But we know that the actual path is rarely shorter
(a tunnel through a mountain could be shorter than the direct path over the
mountain). If we have no tunnels, the heuristic is admissible; if we have tunnels,
It should be easy to get a heuristic that never overestimates the actual distance
between two nodes, but we also want it to be as large as possible without going
over. We will see the importance of this when we get to some examples. If the roads
are all set on hillsides, none of themwill ever be anywhere near as short as a straight
line, so we should adjust the heuristic to something larger than the direct distance.
Both parts of a good heuristic have a profound impact on the performance of A*.
We can use Figure 10.1 to walk through an example of how A* works.