This assignment expands on problem 8.15 of Weiss. You are to write a program that generates mazes of arbitrary size inside a JPanel. In addition, the program should be able to find an optimal path through the maze. Some other features and functionalities are required.

As usual, you should include a README file that explains the program.

Part 1) Generating random mazes (22 pts.)

Write a program that allows the user to generate random mazes using a GUI. The method for doing this is described in section 8.7 of Weiss. Here are some features that you should implement (THERE ARE SOME ADDITIONAL REQUIREMENTS ABOUT THE WAY THE Disjoint-Sets DATA STRUCTURE SHOULD BE IMPLEMENTED. THESE ARE SHOWN IN RED):

• You should use a Disjoint-Sets implementation to keep track of mutually reachable cells as you remove walls.
• You should create your own Disjoint-Sets implementation which uses the "reverse-tree" model, and employs union by rank or size, as well as path compression.
• Allow the user to specify the number of rows and columns in the maze.
• The program should stop knocking walls down when there is only one component left. Furthermore, no wall should be knocked down whenever doing this does not result reducing the number of components.
• Allow the user to specify the start-cell and end-cell of the maze by clicking on the two cells at the beginning of the program. For full credit, you should allow the start and end cells to occur even in the interior of the maze. If the user clicks on an exterior cell the outer wall of that cell should be knocked down. The colors of the start-cell and end-cell should be different from the colors of regular cells. If you don't have time to implement this feature, set the start-cell to be the top-left corner and the end-cell to be the bottom-right corner.
• Allow the user to re-start.

Part 2) Solving the maze (8 pts.)

Solve the maze by finding the optimal path (no dead-ends) from the start-cell to the end-cell. When this path has been found, it should be drawn on the panel. The user should be able to click on a "Solve" button to start the solution phase of the program.

One way of doing this is by viewing the maze as a graph; moreover, cells are vertices which are connected to neighboring cells by an edge, whenever the wall between the cells has been knocked down. You can either create an explicit graph representation for the maze, or you can keep only the structures that you had for part 1, so that the edges are just "missing" interior walls. You can use the method described in class, or any other method that you come up with.

Part 3) Extra Credit Additions

List any extra credit that you do in the README file and explain how your extra credit works.

• User defined wall-knocking-down policy (5 pts.) Let the user specify how walls should be knocked down. In particular the user should be able to choose from the following options:
  • Stop knocking walls down when only one component left (usual policy).
  • Stop knocking walls down when the start-cell is connected to the end-cell. So there may well be areas that are unreachable.
  • Allow knocking walls down even when the number of components doesn't increase. This will result in cycles appearing in the maze. You'll still need to be able to solve the maze but the algorithm that you used for Part 2 may no-longer work!
• Animation of the algorithm and applet version (5 pts.) Here you just add the capability to let the user see exactly what is happening as it occurs. So as each wall gets knocked down, the panel should be redrawn; furthermore, as each cell is explored in trying to solve the maze, the corresponding edge should be drawn, including dead-ends and back-tracks (which after being given-up on, aren't drawn anymore, or are left on the maze, but with a lighter color). You should also let the user decide how fast to make the animation (one way to do this is with the Thread.sleep() method). Finally, turn the whole application into an applet so that with your permission, your program can be published on the Web.

  If you do this part, please demo to Zeph.