Game Development Reference
In-Depth Information
denied.
Figure 9.8(b)
shows the final path as computer by A*, which is clearly su-
perior to the greedy best-first solution.
Figure 9.8
A* path.
Apart from the node adoption, the code for the A* algorithm ends up being very
similar to best-first, as shown in
Listing 9.2
.
Listing 9.2
A* Algorithm
currentNode
=
startNode
add
currentNode
to
closedSet
do
foreach
Node
n
adjacent to
currentNode
if
closedSet
contains
n
continue
else if
openSet
contains
n
// Check for adop-
tion
compute
new_g
// g(x) value for n with
currentNode as parent
if
new_g
<
n.g
n.parent
=
currentNod
e