Game Development Reference
In-Depth Information
Click here to view code image
currentNode = Node with lowest h in openSet
remove currentNode from openSet
add currentNode to closedSet
This is where having a sorted container for the open set becomes handy. Rather
than having to do an O ( n ) search, a binary heap will grab the lowest h ( x ) node in
O (1) time.
Finally, we have the exit case of the loop. Once we find a valid path, the current
node will be the same as the end node, at which point we can finish the loop.
Click here to view code image
until currentNode == endNode //end main do...until
loop
If we exit the do...until loop in the success case, we will have a linked list of
parents that take us from the end node all the way back to the start node. Because
we want a path from the start node to the end node, we must reverse it. There are
several ways to reverse the list, but one of the easiest is to use a stack.
Figure 9.7 shows the first two iterations of the greedy best-first algorithm applied
to the sample data set. In Figure 9.7(a) , the start node has been added to the closed
set, and its adjacent nodes (in blue) are added to the open set. Each adjacent node
has its h ( x ) cost to the end node calculated with the Manhattan distance heurist-
ic. The arrows point from the children back to their parent. The next part of the
algorithm is to select the node with the lowest h ( x ) cost, which in this case is the
node with h = 3. It gets marked as the current node and is moved to the closed set.
Figure 9.7(b) then shows the next iteration, with the nodes adjacent to the current
node (in yellow) added to the open set.
Search WWH ::




Custom Search