Game Development Reference
In-Depth Information
FIG 5.6 Environment map for a maze with path found using DFS.
An implementation of this algorithm is shown in Figure 5.6 . Note that the
algorithm does not find the shortest path to the destination, just a path. The
success of finding the destination in a reasonable time is left to the luck of
which adjacent node is selected first. In Figure 5.6 , nodes are selected in an
anticlockwise order beginning with the one immediately above the current
node. If a clockwise order had been chosen the path would be different. Of
course, this algorithm could also be modified to perform an exhaustive search
to find all paths to the destination; by finding the path with a minimum cost
the best could be selected. However, it is an ineffective way of finding the
shortest path.
The most popular algorithm used in games, for searching graphs, is called A*
(pronounced A-Star). What makes A* more efficient than BFS or DFS is that
instead of picking the next adjacent node blindly, the algorithm looks for one
that appears to be the most promising. From the starting node, the projected
cost of all adjacent nodes is calculated, and the best node is chosen to be the
next on the path. From this next node the same calculations occur again and
the next best node is chosen. This algorithm ensures that all the best nodes
are examined first. If one path of nodes does not work out, the algorithm can
return to the next best in line and continue the search down a different path.
Search Nedrilad ::




Custom Search