Game Development Reference
In-Depth Information
known cost and the estimate of the remaining cost supplied by the heuristic to
give f=(g þ h), the ''fitness'' of the node in A* terms. The fitness is used to
decide what node to pursue next. This is where the best-first part of the algorithm
comes into play; fitness tells us the best node to examine next. Let us examine the
values we have so far.
We started with node C, but because it is not the goal and we have added all its
neighbors to the list of nodes to examine, we are done with C. After we dealt with
node C, we had B and Z to pick from.
Node B: f=g þ h=4 þ 5.66 = 9.66
Node Z: f=g þ h=4 þ 8=12
At this point, we can offer some commentary on our heuristic. At node B, we
estimated 5.66 as the cost to X. The actual value using the ferry is 24. Even if there
had been a bridge instead of the ferry, the actual would have been 8. This amount
of underestimation is making B look more enticing than it is. We will waste time
exploring from B before we decide to abandon it and go through Z.
If we know that our nodes exhibit a regular grid pattern and lack diagonals, we
can use the ''Manhattan distance'' as our heuristic. Instead of using Pythagoras'
theorem to compute the hypotenuse of a right triangle from the lengths of the
sides, we simply add the lengths. On the streets of a city with a grid pattern of
streets, this is the distance that will be covered to get from one place to another.
In our example, using Manhattan distance makes the estimate for node B equal 8.
A larger but admissible estimate makes us more likely to abandon suboptimal
nodes earlier, and that is a serious performance gain. In this case, it puts node B
and Z on equal footing. Tuning the heuristic to the particulars of the application
is an important optimization. Let us return to the algorithm using our original
heuristic.
Node B is more promising at this stage, so it will be examined first. We will keep
Z around in case B does not work out. Node B is not our destination, so we have
to add its neighbors (in this case, just node A) to the list of nodes to examine. We
do not add nodes we have already visited, such as node C; driving in circles never
makes a path shorter. Getting to node A adds 4 to the known cost to the goal, g,
and the estimated cost (h) to get from node A to node X is 4 (because that is the
straight-line distance to cross the river).
Node A: f=g þ h=8 þ 4=12