Game Development Reference
In-Depth Information
do
foreach
Node
n
adjacent to
currentNode
if
closedSet
contains
n
continue
else
n.parent
=
currentNode
if
openSet
does
not
contain
n
compute
n.h
add
n
to
openSet
end
end
loop
//end foreach
Note how any nodes already in the closed set are ignored. Nodes in the closed
set have previously been fully evaluated, so they don't need to be evaluated any
further. For all other adjacent nodes, the algorithm sets their parent to the current
node. Then, if the node is not already in the open set, we compute the
h
(
x
) value
and add the node to the open set.
Once the adjacent nodes have been processed, we need to look at the open set.
If there are no nodes left in the open set, this means we have run out of nodes
to evaluate. This will only occur in the case of a pathfinding failure. There is no
guarantee that there is always a solvable path, so the algorithm must take this into
account:
if
openSet
is empty
break
//break out of main loop
end
However, if we still have nodes left in the open set, we can continue. The next
thing we need to do is find the lowest
h
(
x
) cost node in the open set and move it
to the closed set. We also mark it as the current node for the next iteration of our
loop.
