Maze generation algorithms

Two common maze generation techniques, see http://www.mazeworks.com/mazegen/ for more techniques and an excellent Java applet which demonstrates some of these.

Depth first search:

1. Start with an array (rectangular or hexagonal) of the proper width and height with all the cells marked as unvisited, and all walls up between the cells. If you want to exclude some cells from the maze (for example, to make a non-rectangular maze), mark these cells as visited.
2. Start at a particular cell and call it the "exit."
3. Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
   1. If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse to step 3 with that neighbor as the current cell.

If your computer architecture has a small stack and cannot effectively use recursion, you can store the backtracking information in the maze itself; this also provides a quick way to display a solution, by starting at any given point and backtracking to the exit.

Mazes generated with a depth-first search have a low branching factor and contain many long corridors, which makes depth-first a good algorithm for generating mazes in video games.

Kruskal's algorithm:

1. Start with an array (rectangular or hexagonal) of the proper width and height, with all the cells given a different number, and all walls up between the cells.
2. For each wall that is not a part of the border, in some random order:
   1. See if the cells on each side of the current wall have the same number, and if their numbers are different:
      1. Remove the current wall.
      2. Then find all the cells in the array with the higher of the two cell numbers and replace them with the lower of the two cell numbers.

At any point in this algorithm, the number in a cell uniquely identifies the region to which it belongs. However, note that this algorithm takes O(n^2) time because of the repeated flood filling of areas with the higher number.

Small-memory algorithm

Other algorithms exist that require only enough memory to store one line of a 2D maze or one plane of a 3D maze; they work by storing which cells in the current line are connected through cells in the previous lines. This algorithm never knocks down a wall between any two cells already connected.