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