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