Game Development Reference
In-Depth Information
Figure 10.2
A somewhat more varied transportation graph between river towns.
Let us change our example to see what happens if the heuristic is not always
admissible and we still want the shortest path. We will have to take some liberties
with the graph to make this happen, yielding the revised graph shown in
Figure 10.2. In order to shorten travel times, the cities at node A and node X have
commissioned a catapult service to fling travelers across the river extremely
quickly. This makes our heuristic inadmissible. The move to catapult service was
sparked by heavy rains that forced the cancellation of the ferry service and caused
major damage to the road between node B and node C. The roads to and from
node X also suffered some minor damage.
We wish that the code should not need to touch any node that it has already
touched, but the combination of an inadmissible heuristic and the desire for the
shortest path means we need to handle paths that split and then merge differently
than before. If a second path makes it to a merge point—a node we have already
touched—with a lower g value than what the merge point already has, then the
first path through the merge point is not the optimal path, and the merge
point goes back onto the open list with new values for g and f. This is the case in
Figure 10.2.
Again, we start at C. Our final goal is node W instead of node X. Node X is the
merge point. The numbers for the nodes are shown in the figure. Node C goes on
the open list first. Being the only node there, its neighbors, B and Z, which are not
on any list, go on the open list, and C goes on the closed list. We examine the
open list for the most promising node.
Search Nedrilad ::

Custom Search