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,

the heuristic is inadmissible.

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.