Sixth Assignment: Creating a Maze
Dave Matuszek, Spring 2003

Purpose of the assignment:

The general idea:

Write a program that builds and prints a random maze.

The algorithm:

Start with an n by m rectangle, with all "walls" present.

This can be implemented as an array, where each cell of the array contains some kind of information about which walls are present. To avoid duplicate information, it might be best to just include "right" and "bottom" walls--in this case, cells in row 0 can be assumed to have a "top" wall, and those in column 0 to have a "left" wall.

Select any square to begin, and count it as being "in the maze." This would be the green square in the example.

Create a set of "frontier" cells. These are cells that are not yet in the maze, but are adjacent, horizontally or vertically, to the cell that is in the maze. (I've made frontier cells yellow.)

Randomly choose a cell from the set of frontier cells. This cell will be adjacent to one or more cells that are already in the maze.

If there is only one such cell, erase the wall between it and the chosen frontier cell.

Cells that are adjacent to the newly added cell, but not in the maze, must be added to the set of frontier cells.

Again, randomly choose a cell from the set of frontier cells. This cell will be adjacent to one or more cells that are already in the maze.

If there is only one such cell, erase the wall between it and the chosen frontier cell. Add any necessary frontier cells.

Again, randomly choose a cell from the set of frontier cells. This cell will be adjacent to one or more cells that are already in the maze.

In this case there is more than one adjacent "in the maze" cell, so randomly choose one of the maze cells adjacent to the chosen frontier cell, and erase the wall between the two cells. Add any necessary frontier cells.

Continue in this fashion until all cells are "in the maze." You always choose one cell from the frontier and connect it to one cell already in the maze.

You are done when the set of frontier cells is empty.

When all cells are in the maze, you can choose a start cell and a finish cell. These would typically be on opposite sides of the maze. (You can actually choose any two cells, but for a good maze you don't want them too close to each other.)

If you have written the program correctly, there should be one and only one path between any two cells.

Details:

Suggestions:

The obvious way to store the maze is in an array, and the obvious way to keep the set of frontier cells is as a Set. But what is actually in the array? And what are the elements of the frontier set? Here are some possibilities:

Now, how do you tell whether a cell of the array is "in the maze" or "not in the maze"? One way is to put the information into the cell itself (how you do this depends on what is in the array). Another way is to keep a Set of cells that are in the maze. Or maybe a Set of cells that are not in the maze. But probably not two sets ("in" and "not in")--it's always a good idea to avoid redundant information.

This is not a difficult assignment. There are a lot of minor choices to be made in implementing this program, but almost anything can be made to work. The trick is to make the choices in such a way as to make the program as simple as possible. The simpler you can make it, the easier it will be to debug, and the less work it will be.

Due date:

Tuesday, April 1st (no fooling).