Game Development Reference
In-Depth Information
A* Pathfinding
Now that we've covered the greedy best-first algorithm, we can add a bit of a
wrinkle to greatly improve the quality of the path. Instead of solely relying on the
h
(
x
) admissible heuristic, the
A* algorithm
(pronounced A-star) adds a
path-cost
component. The path-cost is the actual cost from the start node to the current node,
and is denoted by
g
(
x
). The equation for the total cost to visit a node in A* then
becomes:
f
(
x
) =
g
(
x
) +
h
(
x
)
In order for us to employ the A* algorithm, the
Node
struct needs to additionally
store the
f
(
x
) and
g
(
x
) values, as shown:
struct
Node
Node
parent
float
f
float
g
float
h
end
When a node is added to the open set, we must now calculate all three components
instead of only the heuristic. Furthermore, the open set will instead be sorted by
the full
f
(
x
) value, as in A* we will select the lowest
f
(
x
) cost node every iteration.
There is only one other major change to the code for the A* algorithm, and that is
the concept of
node adoption
. In the best-first algorithm, adjacent nodes always
have their parent set to the current node. However in A*, adjacent nodes that are
already in the open set need to have their value evaluated to determine whether the
current node is a superior parent.
The reason for this is that the
g
(
x
) cost of a particular node is dependent on the
g
(
x
) cost of its parent. This means that if a more optimal parent is available, the
g
(
x
) cost of a particular node can be reduced. So we don't want to automatically
replace a node's parent in A*. It should only be replaced when the current node is
a better parent.
In
Figure 9.8(a)
,
we see the current node (in teal) checking its adjacent nodes. The
node to its left has
g
= 2. If that node instead had teal as its parent, it would have
g
= 4, which is worse. So in this case, the node in teal has its adoption request
