## Depth-first Search and Mazes

June 13, 2007 by jobemakar

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

### Like this:

Like Loading...

*Related*

on July 5, 2007 at 11:23 pm |Mike BoxleiterJobe, I don’t know how much experience you have with search algorithms, but if you want the best pathfinding algorithm it’s defiantly A* (a-star). It’s similar to depth first in that it searches a node graph but it expands the nodes which are closest to the goal and have the shortest path from the root node. This way you don’t have to expand every possible node like in breadth-first, and in general its faster than depth-first. Depth-first can get lucky and get faster results than A*, but in general A* is pretty optimal.

on July 5, 2007 at 11:40 pm |Jobe MakarHi,Yes I am very familiar with A*. In fact, I dedicated much of a chapter in one of my books to it.A* is versatile. But for searching a maze such as this one, depth-first is better. A* is best-used when you can tap into its heuristic to start wandering in the “best” direction.By the way, I have an post coming up where I’ll discuss A* in detail. I just haven’t had the time to write it yet.

on July 14, 2007 at 4:13 am |Mike BoxleiterYeah, I get the idea now. In a maze situation you wouldn’t know where the exit is and thus wouldn’t be able to use the A* heuristic.Well, I suppose you could, but you’d have to use a random number or a constant for the distance to exit which would defeat the purpose of the algorithm…

on November 12, 2007 at 7:27 pm |Sina TJobe, very clever idea of maze generation with AS3 =). Just one question though, I looked at your AS3 code and you have ENTER_FRAME events that seem to be unused i.e. the constructor is empty with “//” inside of it. Can you explain why that is there because I have no idea why put something there if you are not going to use it. Thanks