Game Development Reference
In-Depth Information
n.g
=
new_g
n.f
=
n.g
+
n.h
// n.h for this node
will not change
end
else
n.parent
=
currentNode
compute
n.h
compute
n.g
n.f
=
n.g
+
n.h
add
n
to
openSet
end
loop
if
openSet
is
empty
break
end
currentNode
=
Node
with lowest
f
in
openSet
remove
currentNode
from
openSet
add
currentNode
to
closedSet
until
currentNode
==
endNode
// Path reconstruction from
Listing 9.1
.
...
The tower defense game covered in
Chapter 14
provides a full implementation of
the A* algorithm over a hex-based grid.
Dijkstra's Algorithm
One final pathfinding algorithm can be implemented with only a minor modific-
ation to A*. In
Dijkstra's algorithm
, there is no heuristic estimate—or in other
words:
This means that Dijkstra's algorithm can be implemented with the same code as
A* if we use zero as the heuristic. If we apply Dijkstra's algorithm to our sample
