Game Development Reference

In-Depth Information

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
).