Project 2 - The search for a-MAZE-ing donuts!

Phase B

Important Deadlines

Phase B Due	Wed, Feb 7	Electronic turnin (code + README.txt) by 11:59pm
	Thurs, Feb 8	Paper turnin due by beginning of Quiz Section

 

Outline

• VII. More Provided Code
• VIII. Maze Input and Output
• IX. Getting Started
• X. Detailed Requirements
• Xa. Files to Turnin
• Xb. README Questions (As usual, look here before starting)
• XI. Grading Breakdown
• XII. Going Above and Beyond
• XIII. Phase B Turnin

VII. More Provided Code

For the second phase of this project, we are providing code to read the input maze given as a text file, parse it, and build a Maze class object from it, which your algorithm will operate on. We are also providing the code for a simple maze runner, RandomMazeRunner, that picks the direction to explore in a random fashion. Your own MazeRunner classes should inherit from the abstract MazeRunner class. You may modify the provided code if you wish, but very little (if any) should be necessary, and you should justify any modifications in your README.

The provided code is located in the directory /cse/courses/cse326/07wi/projects/project2/code-phaseB/. You can copy these files when logged on to the instructional unix server attu. You will want to add to it all of the code from Phase A, including your changes.

Further documentation on the Maze code architecture and how to get started can be found here. If you find the large codebase a bit overwhelming, this is good place to start.

VIII. Maze Input and Output

INPUT: The SquareCellMazeFactory class reads a maze from a text file specified on the command prompt. The file format is a picture of the maze. There is also some header information at the front that gives the dimensions of the maze (width, then height). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the entrance, and 'O' for the donut. Once you find the donut, you get to chow down and then exit out of the maze. For example, the following is a legal maze : (Note: entrance and donut can be in any cells in the maze, not just the corners)

       7 5
      +-+-+-+-+-+-+-+
      |*|   | | |   |
      + +-+ + + +-+ +
      |   |   |     |
      + + + +-+ +-+ +
      | |   |     | |
      + +-+-+ +-+-+ +
      |       |     |
      +-+ + +-+-+ +-+
      |   |        O|
      +-+-+-+-+-+-+-+

There are some sample input files in the course project directory mentioned above that you can use to test your program. You are highly encouraged to write (and share with your classmates!) other test mazes to run your MazeRunner on. Send them to us or to the 326 discussion list or post them on the message board.

OUTPUT: After solving a maze, your MazeRunner should output a solution path calculated by the search. The path should be given on a single line and should consist of the printed locations (using the built-in print method) from the start to the exit, separated by single spaces. On the next line should be the length of the solution path, and on the following line should be the number of nodes visited and expanded in the search. The solution should be preceeded by a line giving the name of the search algorithm used. For example, the output for the above maze might be:

Random Search

(0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4) (4,4) (4,5) (4,6)

Length of Path: 10

Number Nodes Visited: 15

The solution displayed above corresponds to the solution path shown below with dots:

      +-+-+-+-+-+-+-+
      |*|   | | |   |
      +.+-+ + + +-+ +
      |.  |   |     |
      +.+ + +-+ +-+ +
      |.|   |     | |
      +.+-+-+ +-+-+ +
      |.....  |     |
      +-+ +.+-+-+ +-+
      |   |........O|
      +-+-+-+-+-+-+-+

Note that your MazeRunner does not need to output a text-graphical solution such as the one displayed above.

Note also that a search very likely involves visiting many nodes that are not on the final solution path. You will have to explore ways of extracting the path from the collection of nodes you visited. RandomMazeRunner gives an example of how this might be done. You will need to modify this technique to work for your algorithms.

IX. Getting Started

After combining your code from Phase A and the new provided code for Phase B, compile everything and try to run the provided random mazeRunner from the launcher class as follows:

      % java MazeRunnerLauncher -r maze0.txt

The "-r" option invokes the random maze runner. Take a look at RandomMazeRunner.java to get a general idea of how things work. After understanding this file, make a copy (say BFSMazeRunner.java) and try implementing a better algorithm.

X. Detailed Requirements

In Phase B you are required to:

• Write MazeRunner classes for BFS, DFS, and BestFS. For more information on the three search algorithms, go here . Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which search algorithm to use: 

	-BFS	use BFS
	-DFS	use DFS
	-BestFS	use BestFS

• Write a d-heap class that implements the PriorityQueue interface.

• Write an additional pointer-based implementation (either a LeftistHeap or a SkewHeap or a BinomialQueue) of a PriorityQueue. Do not use implementations of these that you may find on any web site - including the web site for our text book! Such use will be considered a violation of our collaboration policy. You are free to refer to skeleton code provided in our text book or on our course slides, however the code you turn in should be your own.

• You should assure that all of your PriorityQueue implementations work with MazeRunner.  Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which priority queue implementation to use when needed:  

	-bin	use Binary Heap
	-three	use Three Heap
	-dheap #	use a d-heap, where d = #
	-ptr	use your pointer-based heap (Leftist, Skew or Binomial)

Electronic Turnin

Include the following files plus any others you find necessary:               

• README (see the next sub-section for details)
• (code from Phase A) Queue, Stack, BinaryHeap, ThreeHeap: all improved to grow as necessary
• Your new d-heap implementation (DHeap.java)
• Your new pointer-based implementation (LeftistHeap.java, SkewHeap.java, or BinomialQueue.java)
• MazeRunnerLauncher.java -- Main launcher file, with added options to invoke your mazerunners, and priorityqueue implementaions, etc.
• DFSMazeRunner.java -- MazeRunner based on iterative depth-first-search
• BFSMazeRunner.java -- MazeRunner based on breadth-first-search
• BestFirstMazeRunner.java -- MazeRunner based on best-first-search

README Questions

Your README should contain the following information:

1. The names of your team members and your team's name
2. A breakdown of the work - a brief who-did-what description.
3. (Answer this question before you begin) How long do you think this project will take you to finish?
4. How much time did you actually spend on this project?
5. Acknowledgement of any assistance you received from anyone but your partner, the course staff, or the Weiss book.
6. A brief description of how your project goes "above and beyond" the basic requirements, if it does.

Answer the following questions:

7. Why is it more important for DFS than BFS to check whether a cell has been visited yet?
8. If you gave your MazeRunners a maze that was too large to fit in main memory, which would likely run faster, BFS or DFS? (Any reasonable answer -- as long as it is justified -- will be accepted.)
9. In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
10. Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
11. Why is BFS guaranteed to find the shortest path? Are the other two algorithms guaranteed to find the shortest path? If yes say why, if not, give a counter example.
12. What are the tradeoffs between a pointer vs. array-based heap? In particular, what are the tradeoffs between a binary heap, a threeheap, and a pointer-based heap? Some possible topics to cover include runtime, coding complexity, and memory usage. Did you observe any differences (for example in runtimes or memory use) between using these three for the larger maze inputs?  (Just note if you noticed anything, it is fine if you did not.  You are welcome to explore this question in more detail (timings, measurements, calculations) for extra credit.)
13. In general (not necessarily in the context of this project), why could it be better to use a sorted array implementation of a priority queue versus a binary heap? Why could it be worse?
14. What did you enjoy about this assignment? What did you hate? Could we have done anything better?

XI. Grading Breakdown

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.

XII. Going Above and Beyond

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.

• Create a visualization routine that runs as the maze is being solved. Pop up a window that shows the graph, with different colors used to indicate the state of each room. Drawing routines will need to be invoked when the maze is create and from setState. Include instructions in your README file on how to run the visualization as a Java program and/or as an applet. Please have it so we can run the visualizer in your program using java MazeRunnerLauncher -v - - . Hint: have your visualizer class extend JFrame and implement MazeChangeListener
• Add a maze generator to your program or applet.
• Using the Manhattan distance has several problems, including the fact that the MazeRunner is sometimes fooled into going down "dead ends" in the maze. What other heuristics might be used in your MazeRunner? When might your heuristics perform better than the Manhattan distance, and when might they perform worse (you may want to consider factors such as space usage and time to calculate the heuristic)? Implement and run your Best-First MazeRunner with its new heuristic on several mazes and report which heuristic performed better, and in what type of maze it did better in.
• There is a variation of the Best-First Search heuristic called "A*" (pronounced "A-Star"). A* has some theoretically and practically interesting qualities. Take a look here for a description of the algorithm. Implement A* and give a description of why the algorithm works and how it compares to your other search algorithms (e.g. When does it work better? When does it work worse? Which one would you generally choose to use? etc.)
• Choose your own extension!: Exercise your creativity and think how you can extend this project. Can your MazeRunner handle mazes with multiple exits? What about rendering your maze in 3-D? 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.

XIII. Phase B Turnin

For Phase B, turn in all your code for this assignment (from both Phase A and Phase B).

Only one person from each team should submit. The same person who submitted Phase A should submit Phase B. The turn-in link is here. You should submit electronically:

1. All of the Java code (use *.java) that you need to compile your program
2. The README.txt file

For the hardcopy, please place the README.txt file in front, and include any code that you have written or modified. You do not have to hand in printouts of files that we provided that you did not modify (eg. MazeRunner.java). In addition to both partners’ names and UW email ids, please write the section of each partner (ie. AA, AB, BA, BB) on the front of the README file.