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.