Game Development Reference

In-Depth Information

Figure 10.1

Transportation graph between river towns.

On some major rivers such as the Rhine, there are few bridges and many ferry

stops. Let us consider a journey from C to X in Figure 10.1. Presume that all the

towns are regularly spaced to make the math simpler. It takes only four minutes

to drive on the roads between two neighboring towns, but using the ferry takes

20 minutes. If you could drive it, B and X would be 5.66 minutes apart, taking the

diagonal into account.

A* starts at the beginning and evaluates the nodes around it. So if the trip is from

C to X, the algorithm starts with C, which has neighbors B and Z. Because we

start at node C, the cost to get there is 0. In A* terms, this is g, the known lowest

cost to get to a node. This is the first of the core concepts of A*: knowing the

actual cost to get someplace. The cost to get to B is 4. Because the bridge and the

road are equally fast, the cost g to get to Z is also 4.

Is it faster to take B or Z to get to X? We do not know, but we can use a heuristic

to make a guess. In A* terms, the heuristic is h, the estimated cost to the goal. For

this example we will use straight-line driving time, which is directly proportional

to distance, as our heuristic. Obviously we cannot use the actual driving time; if

we do not yet know what the shortest path is, how can we know how long it will

take to drive?

The heuristic h tells us that Z is 8 minutes away from X, and using a direct

diagonal path, B is 5.66 minutes away from X. Our heuristic is reasonable, but it

does mislead us from time to time. No actual cost is lower than our heuristic, a

required given if the algorithm is to function optimally. A* uses the sum of the