Game Development Reference
In-Depth Information
How it works...
The node bean that we created stores information about the state of the node, which is set
by the pathfinder as it passes, or considers passing a node. The
g
value is the total cost to
this node, along the current path, from the starting node.
h
is the estimated value left to the
goalNode
. In this recipe, it's the shortest distance possible. To be the most effective, it
should be as close to the actual distance as possible, without exceeding it. This is to guaran-
tee that it finds the shortest path.
F
is simply
g
and
h
added together, becoming the total es-
timated cost of the path using this node, and is the value used by the algorithm to consider.
These values are stored as integers, rather than floats. This is better both for memory and
processing purposes. We get around lower-than-one distances by multiplying them with
100.
It also keeps track of whether it's currently open or closed. It's quicker to query the node it-
self, than seeing if the list contains it. The node actually has three states, either open,
closed, or the standard, neither which is when it has not yet been considered for the path.
The parent of a node defines from which other node the path came to this node.
openList
contains all the nodes the pathfinder is currently considering. It starts with
only the
startNode
, adding all its neighbors, since none are either open or closed at this
stage. It also sets the parent of the node, calculates the cost to get to this node, and estim-
ates the cost left to the goal (if it has not been calculated before). It only needs to do this
once per node, as long as the goal is not moving.
Now,
openList
has a few new nodes to work with, and the current node is removed from
the list. At the end of the
while
loop, we sort
openList
according to
f-cost
of the
nodes, so that it always starts looking at the node with the lowest total cost. This is to make
sure it doesn't spend any unnecessary time looking at paths which are not optimal.
The algorithm can be considered to be successful once the
goalNode
has been put in
openList
and is set to closed. We can't end searching just because the
goalNode
enters
openList
. Since we also reconsider nodes if we find a shorter path to the node, we want
to check all the
goalNodes
neighbors as well before ending the search.
If there is no path available to the
goalNode
,
openList
will become empty before the
goalNode
is closed, and the search will fail.
