|Sixth Assignment: Creating a Maze
Dave Matuszek, Spring 2003
Write a program that builds and prints a random maze.
Start with an
mrectangle, 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.
java Maze 5 6
___________ |_ | | | | | | _|_ | | |_| _|_| | _ |_ | |___|___|_|_|
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:
truevalue would indicate that the wall on that side exists, a
falsevalue would indicate the wall is absent.
bottom. Walls above and to the left would be represented in adjacent Cells; Cells in the top row would be assumed to have a top wall, and Cells in the leftmost column would be assumed to have a left wall.
Setcould contain references to
Cells. If the array contains
Cells could be stored directly in the
Set. This will result in problems unless each
Cellcontains its own
Pairs, where a
Pairis a small class you create. Small classes like this really should be created as inner classes, unless you have some reason to think they are more generally useful.
1000*row+column. (I promise we won't use more than 1000 columns!) I picked 1000 because it's readable: 12017 is clearly row 12, column 17. Of course, you would have to wrap this integer before you could put it into a
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
Set of cells that are in the maze. Or maybe a
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.
Tuesday, April 1st (no fooling).