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:

There are no cycles (See Figure 1)
There is a unique path from the start cell in the maze to the end cell (indeed, this is true of any two cells in the maze)

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