Game Development Reference

In-Depth Information

Z at 16 beats B at 16.9, so Z is examined next. Z cannot improve C's numbers, so

C stays on the closed list. Z puts Y on the open list with B because Y is a new node.

We are done with Z, so it joins C on the closed list. Again, we examine the open

list for the most promising node.

Y at 16 also beats B at 16.9, so we examine Y. Y cannot improve on Z's numbers,

so Z stays on the closed list. X is new, so it goes on the open list. Y is done, so Y

joins Z and C on the closed list.

From the open list, B at 16.9 beats X at 17, so we examine B next. B cannot

improve C's numbers, so C stays on the closed list. A is new, so B adds A to the

open list with X. B gets put on the closed list with C, Z, and Y.

On the open list, X at 17 beats A at 17.7, so we examine X next. X cannot improve

Y's numbers, so Y stays on the closed list. X cannot improve A's numbers, so X

does not update A on the open list. W is new, so X puts W on the open list.

X joins Y, Z, C, and B on the closed list.

On the open list, A at 17.7 beats W at 18, so A is examined next. Here is where we

will encounter the effects of an inadmissible heuristic. The catapult method of

crossing the river is far faster than the heuristic expects anyone to ever go. This is

where the heuristic gives an
inadmissible
estimate of the cost. Node A cannot

improve B's numbers, so B stays on the closed list. Node A
can
improve X's

numbers, so X is updated and moved from the closed list back to the open list to

join W.

An A* implementation that has the normal optimization of ignoring nodes on

the closed list would not have touched X again. Nor would it have taken the effort

to see if it could improve the numbers of any node on the closed list as we did in

the preceding paragraphs. Node A goes onto the closed list with B, C, Y, and Z.

The open list is again checked. X at 16.5 beats the existing W at 18, so X is given

another chance. X cannot improve A or Y, so they remain on the closed list. X can

improve W on the open list, so W goes from 18 to 17.5. X goes to the closed list

with all the other nodes except W. Since the goal node has the best score on the

open list, it is used as it is.

This example shows that the world does not end if the heuristic is sometimes

inadmissible. It can have easily happened that with an inadmissible heuristic, A*

will not find the shortest path, regardless of whether it reexamines nodes on the

closed list or not (see Exercise 2 at the end of this chapter). This is the penalty for