Game Development Reference
In-Depth Information
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,
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.