Project 2 - The search for
a-MAZE-ing donuts!
Phase C
Important Deadlines
Outline
Congratulations! You can solve your maze! But creating those test mazes was so tedious and boring...isn't there a better way to create mazes than by hand?
For the third phase of this project, you will harness the power of computers and data structures to generate your own mazes. You will implement Kruskal's algorithm to create new, random mazes. In addition to that webpage, the Weiss book has a description of this algorithm: see Section 8.7. To help you get started, a depth first search version of maze generation is provided for you in the new Maze.java class.
Kruskal's algorithm relies on the Disjoint Set data structure. You will need to write a DisjointSet class that implements the Disjoint Set data structure. Your implementation will be pointer-based.
You will need to add methods to Maze.java and MazeCell.java in order to complete the assignment. You will
add the following methods to the Maze class:
- formKruskalMaze - forms the maze using Kruskal's algorithm
You will also need to add methods to the MazeCell class. For example, you may want to add a helper method for finding a neighboring cell with its wall up. Additionally, you will need to add setParent and getParent methods (see below).
The provided code is here. In addition to newer versions of MazeViewer.java, MazeCell.java, and Maze.java, we are also giving you a simple tester class. The tester takes 8 UpTree's and performs a series of unions on them. The result should be the same as in your book in Figure 8.4. Your first version of DisjointSet should thus implement the following methods:
- public void union(UpTree tree1, UpTree tree2)
- public UpTree find(UpTree tree)
Once you write DisjointSet so that DisjointSetTester works appropriately, you will modify the methods so that they take MazeCell as parameters instead of UpTree. You should not have to change anything else within DisjointSet besides the method headers. Instead you will modify MazeCell so that it has a parent variable, and you will write setParent and getParent methods.
XVI. Detailed Requirements
In Phase C you are required to:
- Write a Disjoint Set data structure.
- Write a method for maze generation by Kruskal's algorithm. You will also have to write a helper method (or two) in MazeCell.
Include the following files plus any others you find necessary:
- README (see the next sub-section for details)
- DisjointSet.java
- Maze.java -- Main algorithm file
- MazeCell.java -- Will contain helper methods
You should NOT have to modify MazeViewer.java or MazeFactory.java.
Your
README should contain the following information:
- The names of your team
members and your team's name
- A breakdown of the work - a
brief who-did-what description.
- (Answer
this question before you begin) How long do you think this
project will take you to finish?
- How much time did you
actually spend on this project?
- Acknowledgement of any
assistance you received from anyone but your partner, the course staff, or
the Weiss book.
- A brief description of how
your project goes "above and beyond" the basic requirements, if
it does.
Answer
the following questions:
- What are some advantages to the pointer-based Disjoint Set method versus the array-based method? What are some disadvantages?
- Which algorithm works better for maze generation, depth first search or Kruskal's? Why?
- Suppose you thought of each maze cell as a vertex, and each wall as indicator of an edge, so that if there was a wall up between neighboring cells A and B, that means there is not an edge between them. Thus the initial grid (before generation) corresponds to a grid of vertices that are completely unconnected (i.e. there are no edges between any vertices). What does the final maze, after generation, correspond to?
- Prove that the mazes generated by DFS and Kruskal's algorithm have the property that the path from the starting to the ending points is unique.
- What did you enjoy about this
assignment? What did you hate? Could we have done anything better?
The
amount of code required for this project is actually very small. A significant
part of your grade will be based on your program design and your README.
- Correctness - 40%
- Architecture/design- 30%
- README- 30%
Look
at the course
grading policy for a more detailed explanation on grading guidelines.
The
following suggestions are meant for you to try if you finish the requirements
early. Be sure to clearly describe what you did and how to run it in your
README. Recall that any extra-credit points you earn for these are kept
separate from your assignment score and will be used to adjust your grade at
the end of the quarter, as detailed in the course
grading policy.
- Kruskal's algorithm can be modified so that a priority queue is used to choose which wall to knock down next. Modify your code to do this. There should be some heuristic you use to prioritize which wall to knock down. For example, you could prefer "vertical" mazes and thus always knock down horizontal walls before vertical walls.
- Implement union-by-size, union-by-height, and/or path compession. Describe how this changes the performance of the algorithm in your experience.
- Another algorithm that can be used for maze generation is Prim's algorithm. Implement this algorithm. You can also extend Prim's algorithm in the same way as Kruskal's, above, by including a priority queue.
- Super-duper above and beyond (courtesy of Gary, the graphics student): Make your heuristic for your priority queue correspond to a picture, so that your maze looks kind of like the input. For instance, you could input an ASCII file with a big smiley face, and your heuristic would then choose to knock down walls so that the maze looked like a smiley face. Or you could read in a JPEG file, find the edges via an edge detection algorithm, and then use those to dictate your heuristic.
- Choose your own extension!:
Exercise your creativity and think how you can extend this project. If you do
anything that alters the basic design specifications, check with the
staff, and document what you did. Of course, your code should still meet
the basic requirements.
For
Phase C, turn in all your code that you changed/added for this assignment.
Only
one person from each team should submit. The same person who submitted Phases A and B should submit Phase C. You should submit electronically:
- All of the Java code (use
*.java) that you need to compile your program
- The README.txt file