Maze part I - Maze Generation

• Use a stack to implement an algorithm
• Use a collection to implement an algorithm
• Potentially use a queue to implement an algorithm
• Implement an algorithm to create random mazes of various sizes

The objective of this assignment is to create a Maze which contains no loops, no large open areas, and no unreachable areas. A lot of code is provided to start you out. Check the resources section of this page for that code. The requirements section specifies the details of what must be done to finish this project.

1. Create this program in a new directory which only contains code for this program.
2. Modify any source code you change to include your name and the current date.
3. You need a class to represent directions. This should be done as an enumeration. The source code needed for this is provided and can be used without modification. It is named Direction.java. The Direction enumeration specifies four directions, has information of the x and y displacement if moving in a particular direction, provides a name for each direction, and provides a method for getting the opposite direction.
4. You need a class to represent the individual cells of the maze.The Cell class keeps track of its own walls, its row and column position within the maze, stores a few pieces of information for algorithms to use, keeps track of any sides that are exterior boundaries of the maze, and can assemble a list of neighboring cells. Most of the Cell class has already been implemented for you. It is available as Cell.java. See the Methods section for a description of the one method you must implement.
5. You need a class to represent the maze as a whole. The Board class creates and initializes grids of Cell objects from 1 by 1 up through 100 by 100, keeps track of all of the individual cells, provides access to the individual cells, keeps track of a starting and an ending cell, and provides some convenience methods to facilitate maze creation and solving. A lot of the code has already been written for you. It is available as Board.java. See the Methods section for a description of the three methods you must implement.
6. You need a class to actually create and display the maze. This is what the Maze1 class does. Some of the code has already been written for you. It is available as Maze1.java. See the Methods section for a description of the one method you must finish implementing. This will be the code that actually creates the maze.
7. When you are done implementing the code you are supposed to implement, you can compile everything using: javac *.java. You can then run the code using: java Maze1
8. There is built-in test code to display whether or not your code is functioning properly.

1. In Cell.java: ArrayList<Direction> getNeighbors().
   Create and return a new ArrayList of Direction objects. The list should contain every Direction for which there is an adjacent Cell. It should not contain any Direction which leads beyond the boundaries of the maze itself.
2. In Board.java: ArrayList<Direction> getConnectedNeighbors(Cell c).
   Create and return a new ArrayList of Direction objects. The list should contain every Direction for which there is an adjacent Cell which exists and is connected (has no wall between it and the Cell specified by the method argument).
3. In Board.java: ArrayList<Direction> getUnvisitedConnectedNeighbors(Cell c).
   Create and return a new ArrayList of Direction objects. The list should contain every Direction for which there is an adjacent Cell which exists, is unvisited, and which has no wall between it and the Cell specified by the method argument.
4. In Board.java: ArrayList<Direction> getUnvisitedNeighbors(Cell c).
   Create and return a new ArrayList of Direction objects. The list should contain every Direction for which there is an adjacent Cell which exists and is unvisited (even if there is a wall between the adjacent Cell and the Cell specified by the method argument).
5. In Maze1.java: public Maze1().
   
   1. Create a new stack which can contain Cell objects.
   2. Choose a random cell from Board b and push it on to the stack.
   3. While the stack is not empty
      1. Let cl = the top Cell popped from the stack
      2. Set cl to visited
      3. Get a list of all of cl's unvisited neighbors
      4. If there are any items in cl's unvisited list, then push cl back onto the stack and choose one of its unvisited neighbors at random. Connect cl to that randomly chosen neighbor, and then push that neighbor onto the stack.

• Direction.java
• Cell.java
• Board.java
• Maze1.java