Game Development Reference
In-Depth Information
Figure 9.7
Greedy best-first snapshots.
Once the goal node (in red) is added to the closed set, we would then have a linked
list from the end node all the way back to the starting node. This list can then be
reversed in order to get the path illustrated earlier in
Figure 9.6
.
The full listing for the greedy best-first algorithm follows in
Listing 9.1
. Note that
this implementation makes the assumption that the
h
(
x
) value cannot change dur-
ing the course of execution.
Listing 9.1
Greedy Best-First Algorithm
curentNode
=
startNode
add
currentNode
to
closedSet
do
// Add adjacent nodes to open set
foreach
Node
n
adjacent to
currentNode
if
closedSet
contains
n
continue
else
n.parent
=
currentNode
if
openSet
does
not
contain
n