Game Development Reference
FIG 5.5 Environment map for a maze with path found using BFS.
modified to take into consideration other costs such as terrain type and
traversal times in addition to or instead of distance by keeping track of
all possible paths to the destination and adding up the costs. The path
with the least cost can then be selected.
The DFS is simpler than the BFS and hence less effective. Instead of
radiating out from the starting node, this algorithm simply follows one
adjacent node to the next until it reaches the end of a path. Recursion
works well for this algorithm and can be written as Listing 5.4 .
Listing 5.4 A Depth-First Search Algorithm
DFS( a, vertex )
1. Let i = a;
2. Label node as i
3. For each adjacent node, n , to i, if n is labeled skip it; if n is the end node
then stop the search; else if n is not labeled run this algorithm with
DFS( a+1, n ).