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.