Game Development Reference
In-Depth Information
float
h
end
The
parent
member variable is used to track which node was visited prior to
the current one. Note that in a language such as C++, the parent would be a point-
er, whereas in other languages (such as C#) classes may inherently be passed by
reference. The
parent
member is valuable because it will be used to construct
a linked list from the goal node all the way back to the starting node. When our
algorithm is complete, the parent linked list will then be traversed in order to re-
construct the final path.
The float
h
stores the computed
h
(
x
) value for a particular node. This will be con-
sulted when it is time to pick the node with the lowest
h
(
x
).
The next component of the algorithm is the two containers that temporarily store
nodes: the open set and the closed set. The
open set
stores all the nodes that cur-
rently need to be considered. Because a common operation in our algorithm will
be to find the lowest
h
(
x
) cost node, it is preferred to use some type of sorted con-
tainer such as a binary heap or priority queue for the open set.
The
closed set
contains all of the nodes that have already been evaluated by the
algorithm. Once a node is in the closed set, the algorithm stops considering it as
a possibility. Because a common operation will be to check whether or not a node
is already in the closed set, it may make sense to use a data structure in which a
search has a time complexity better than
O
(
n
), such as a binary search tree.
Nowwehavethenecessarycomponentsforagreedybest-firstsearch.Supposewe
have a start node and an end node, and we want to compute the path between the
two. The majority of the work for the algorithm is processed in a loop. However,
before we enter the loop, we need to initialize some data:
currentNode
=
startNode
add
currentNode
to
closedSet
The current node simply tracks which node's neighbors will be evaluated next. At
the start of the algorithm, we have no nodes in our path other than the starting
node. So it follows that we should first evaluate the neighbors of the starting node.
In the main loop, the first thing we want to do is look at all of the nodes adjacent
to the current node and then add some of them to the open set:
