I recently finished a small series of posts on the AI topic of emergent behavior. Now I will be posting a few entries on the AI topic of search algorithms, aka pathfinding.

Almost everything I program is from a game programmer’s perspective. As such, search algorithms are pathfinding algorithms as far as I’m concerned. In the most generic sense though a search algorithm finds…something. Path, state, item, what ever. During my posts I plan to cover at least Depth-first (that is this post), A*, and Dijkstra’s algorithm.

Depth-first search is an algorithm used to search tree structures. Let’s call the node you’re looking for the goal. Generally with a depth-first search you’re looking for either the location the goal or the path to it.

Here is the pseudocode for this algorithm:

` `

find(n, goal) if n == goal end and return path else for all children of n find(child, goal))

I am no pseudocode expert so I hope I formatted that in an understandable way. The concept though is this:

- Write a function that takes a node and a goal node
- If the node is the goal node, stop and return the path
- If the node is not the goal node, then run this function for all children of the node

In my experience depth-first searches are suited well in games for two purposes:

- Generating perfect mazes. A perfect maze is a maze in which there exists exactly one unique path between any two cells.
- Finding a path in a very constricted environment, such as a maze.

I have used depth-first a few times and it has always been for mazes!

I have created an ActionScript 3 demo. This demo creates a perfect maze using depth-first search. It also finds a path between a start node and where ever you place your mouse real-time. This search also uses depth-first search.

Here is the logic for creating a maze:

- Create a grid pattern of some size (mine is 20 X 20)
- All nodes are initialized with all 4 walls turned on.
- Pick any node to start with and run the following pseudocode

` `

expand(n) set n as visited randomize order of n's neighbors for all neighbors of n if neighbor not visited knock down wall between n and neighbor expand(neighbor)

The logic above will touch every tile and create a unique looking maze. To find a path within the maze you can run a similar search from a starting node until you reach the destination node. In that search though you only consider neighbors of a node that have open pathways (eg doorways).

DOWNLOAD

click to view example

Read Full Post »