Game Development Reference
In-Depth Information
With that, we are done with node B. Nodes A and Z have the same estimated cost,
so we could investigate either one next. Since it doesn't matter which we choose,
let's look at node A next. The only new neighbor to add to our list is node X.
Getting from node A to node X costs 20 (since we have to take the ferry), so we
add that to 8, the known cost for node A, giving us a g of 28. Since node X is the
goal, h is zero.
Node X (via A): f=g þ h=28 þ 0=28
When we compare the 28 to the values we have, we find that we have paths with a
potentially lower cost. Node Z is claiming 12 for its estimated total cost. As long
as that path can stay under 28, we will continue pursuing it. Going from Z to Y
adds 4 to g, the known cost thus far to the goal.
Node Y: f=g þ h=8 þ 4=12
That finishes node Z. The path using node Y is still below our 28, so we continue.
Going on to X from Y adds 4 to g, the known cost thus far to the goal. Since X is
the goal, we have the following:
Node X (via Y): f=g þ h=12 þ 0=12
There are no paths left that might come in lower, so we have the shortest path. By
using best-first, A* can still pursue blind alleys, but it abandons them as soon as
their cost rises above alternatives. It does not foresee obstacles, but it will avoid
them as they appear.
Implementing A* is harder than understanding how it works. The details in this
section will be of particular interest to those readers who will need to implement
their own A*. We will go over the lists used to make A* work, and we will
comment on how admissibility of the heuristic has a performance impact.
We keep two lists in A*: the open list and the closed list. The open list holds nodes
that might need further examination. We need to be able to easily find the node
with the best fitness from the open list because that is always the next node to
examine. To hold nodes that are no longer on the open list, we have the closed
list. Once we have put the neighbors of a node on the open list, we can take that
node off the open list and put it on the closed list. The two lists make things easier
to juggle.