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