Game Development Reference

In-Depth Information

To start with, we added C to the open list. Each step involves removing the fittest

node from the open list and checking its children to see if they get updated and

belong on the open list. In the evaluation of node C, we removed C from the open

list after we added nodes B and Z to the open list and updated their values. B and

Z had not been looked at before, so their values were set, and they went onto the

open list. New nodes always go on the open list. Neighboring nodes already on

the open list will have their numbers updated only if the new numbers are better.

Neighboring nodes on the closed list go back on the open list only if their

numbers improve, but this will never happen if the heuristic is good, and the cost

always increases with additional steps. Since most applications have the cost

increase with each step, the only concern is with the heuristic.

For simplicity, we did not show in the discussion the fact that when we evaluated

node B, the algorithm considered going back to node C since node C is a

neighbor of node B. Node C was given a 0 value for g when we started. A path that

goes from node C to node B back to node C will want to give C a g value of 8,

which is worse than what is already there. For path finding related to travel in

time or space, the costs always increase, so looping paths will automatically be

worse than non-looping paths. C is a neighbor of B, but C will not go back onto

the open list unless it can do so with better numbers than it already has. This

never happens in our example because cost is monotonic (taking another step

can only increase cost) and our heuristic is admissible. Because it never happens,

we can safely ignore any neighbor that has made it to the closed list. Real

implementations of A* would not have computed the cost of going to node C;

instead they would first see if node C was on the closed list, and if it was they

would ignore node C.

Being able to ignore nodes on the closed list is a huge performance win!
Once again,

this optimization is made possible by having an admissible heuristic and

monotonically increasing cost. Monotonically increasing cost is usually a given,

but admissibility of the heuristic is a design decision.

If the estimate provided by the heuristic is sometimes higher than the actual cost,

not only do we no longer have a guarantee that the path we get will be the shortest

one, but we may also find that we need to move nodes that are on the closed list

back to the open list in pursuit of the shortest path. It is extremely unlikely that

any real implementation of A* will ever allow backtracking by reexamining nodes

on the closed list.