Game Development Reference
In-Depth Information
compute
n.h
add
n
to
openSet
end
end
loop
// All possibilities were exhausted
if
openSet
is empty
break
end
// Select new current node
currentNode
= Node with lowest
h
in
openSet
remove
currentNode
from
openSet
add
currentNode
to
closedSet
until
currentNode
==
endNode
// If the path was solved, reconstruct it using a
stack reversal
if
currentNode
==
endNode
Stack
path
Node
n
= endNode
while
n
is not
null
push
n
onto
path
n
=
n.parent
loop
else
// Path unsolvable
end
If we want to avoid the stack reversal to reconstruct the path, another option is to
instead calculate the path from the goal node to the start node. This way, the linked
list that we end up with will be in the correct order from the start node to the goal
node, which can save some computation time. This optimization trick is used in
the tower defense game in
Chapter 14
, “
Sample Game: Tower Defense for PC/
Mac
”(thoughitdoesnotimplementgreedy-bestfirstasitspathfindingalgorithm).
