|CSE Home||326 Home||About Us||Search||Contact Info|
Project 2 - The search for a-MAZE-ing donuts!
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:
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:
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:
Include the following files plus any others you find necessary:
Your README should contain the following information:
Answer the following questions:
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.
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.
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. The turn-in link is here. You should submit electronically:
Computer Science & Engineering|
University of Washington
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to gyngve]