Maze Generation

There are several ways to go about generating a maze from a grid. We would like to generate mazes with the following two properties:


Figure 1. A maze with a cycle
Mazes that satisfy these two properties are called "perfect" mazes. All three of the methods below generate perfect mazes.

Depth first search

This is very similar to the depth first search algorithm you used to search the maze. The version included in your code is an iterative version; below is the recursive version.

Generate( Maze m )
    Choose random cell to start at and initialize stack
    Call DFS( start , stack )
DFS( MazeCell current, Stack stack )
    Choose a random neighbor of current that has all its walls up
    If there is no neighbor of current with all its walls up
       Pop a cell off of the stack and call DFS( popped cell, stack )
    Else
      Knock down wall between current and neighbor
      Push current onto the stack
      call DFS( neighbor cell, stack )

Kruskal's algorithm

The algorithm described in your book, section 8.7, is Kruskal's algorithm. Think of the maze as a group of disjoint sets, one for each maze cell. Then union is equivalent to knocking down a wall between one set and another, so that there is now a passage between them. The algorithm works by performing a series of finds, and unioning sets with different labels. Note that once two sets have been unioned, knocking down any further walls within that set would produce an imperfect maze. The algorithm is complete when all the maze cells are within the same set and we are unable to perform any more unions.

Generate( Maze m )
    While (# Walls Down < Total # Cells - 1)
       Choose random cell current
       Choose random neighbor of current that has a wall up between it and current
       If such a neighbor exists
          Find the labels of current and neighbor
          If they are different, union them, knock down the wall, and add to # Walls Down

Note that the condition under which a neighbor is chosen is different than the condition in depth first search. In DFS we choose a neighbor with all of its walls up (thus guaranteed to be disconnected); in Kruskal we just look for a neighbor with a wall up between it and the current cell. Union/find takes care of the rest.

Prim's algorithm (Above and Beyond)

Prim's algorithm and Kruskal's algorithm solve the same underlying problem. In fact, if you were to weight which walls to knock down and use a priority queue to choose walls with the lowest weight first, the Prim and Kruskal algorithms will form the same maze (in a different way). The algorithm is as follows:
Generate( Maze m )
    Choose a random cell, mark it visited, and add it to the list
    While there are cells on the list
       Pick a cell off the list
       Add its neighbors to the list
       Knock down a wall between it and a neighbor
       Mark that cell visited