Purpose of the assignment:

• To give you some experience with Java Collections.

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:

• Write your program as an application, with the "main" class named Maze.
• Supply the height and width of the maze as parameters to your program.
  • For instance, the above maze could have been generated with java Maze 5 6
  • Print your maze out, in a form something like this:

    ___________ |_ | | | | | | _|_ | | |_| _|_| | _ |_ | |___|___|_|_|

• Do not bother to choose or print out start and finish locations. That just makes it harder to print out the maze, and isn't an important part of the assignment.
• Use Collections in your program. Specifically, keep the set of frontier cells in a Set.

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:

• Each cell of the array could contain an object (let's call it a Cell), with boolean fields top, right, bottom, left. A true value would indicate that the wall on that side exists, a false value would indicate the wall is absent.
• Similar to the above, but in order to avoid having to deal with redundant information, have only the fields right and 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.
• You could represent the above information as an integer, with 1=top, 2=right, 4=bottom, 8=left. So, for instance, a cell with top and left walls would be represented as the integer 1+8=9. In this case the array would be an int[].
  
  
• The Set could contain references to Cells. If the array contains Cells, then Cells could be stored directly in the Set. This will result in problems unless each Cell contains its own row and column address.
• The elements in the set could be row, column Pairs, where a Pair is 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.
• You could combine the row and column into a single number, 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 Set.

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).