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

Phase B

Important Deadlines

Base code ready for copying	Mon, Oct 20	Should be ready by 6:00 pm
Phase B "donut-ready" checkin	Mon, Oct 27	Electronic turnin by 11:00pm
Phase B Writeup	Wed, Oct 29	Beginning of Lecture; see printing guidelines

Updates

(Dated updates will appear here for this assignment as they come up.)

Thursday, Oct 23, 9:25am -- Added missing MazeRunnerLauncher.java to the starter code and fixed the webpage instructions to reflect the change (main used to be bundled with RandomMazeRunner, but it's now in the Launcher). @awong
Thursday, Oct 23, 1:15pm -- Fixed code to make the "-p" option work as intended. File changed: SquareCellMazeVisualizer.java. Lines 85 and 91. @ashish

XIa. Above and Beyond Requirement
XIb. Files to Turnin
XIc. README Questions (As usual, look here before starting)

XII. Grading Breakdown
XIII. Going Above and Beyond (for credit)
XIV. Phase B Turnin

See the writeup for Phase A for background information.

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/03au/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. Note: for the basic requirements of the project, you should not have to read every line of the code, particularly the parts that parse the input or perform visual displaying or implement the details of a MazeCell.

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 (height, then width). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the entrance, and 'X' for the exit. For example, the following is a legal maze:

      7 5
      +-+-+-+-+-+-+-+
      |*|   | | |   |
      + +-+ + + +-+ +
      |   |   |     |
      + + + +-+ +-+ +
      | |   |     | |
      + +-+-+ +-+-+ +
      |       |     |
      +-+ + +-+-+ +-+
      |   |        X|
      +-+-+-+-+-+-+-+

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 class discussion list.

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) 
10 
15

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

      +-+-+-+-+-+-+-+
      |*|   | | |   |
      +.+-+ + + +-+ +
      |.  |   |     |
      +.+ + +-+ +-+ +
      |.|   |     | |
      +.+-+-+ +-+-+ +
      |.....  |     |
      +-+ +.+-+-+ +-+
      |   |........X|
      +-+-+-+-+-+-+-+

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. Maze Visualization

You should also use the mazerunner program to visualize the progress of your algorithm. Pass a maze file to mazerunner with the -v option to watch mazerunner simulate your algorithm graphically. The following command will start mazerunner's simulation of your algorithm:

      % java MazeRunnerLauncher -r -v -t -p 800 mazefile

The "-v" option turns on the visualizer, "-t" prints out some tracing information, and "-p" tells the algorithm to wait for a specified time after processing each step. You can choose any (or no) options to use, but you must provide them in this order. For your maze runners and any Above and Beyond stuff you implement, add more options to MazeRunnerLauncher.java to invoke the appropriate code.

Try using the visualizer with the random solver so you can see how it works. In your own MazeRunner, you will need to call setCellState() in MazeCell to make the colors change. There may be some flexibility in when exactly to change the colors relative to the algorithm's progress; you can make the exact determination of how to do this provided you follow the basic algorithm.

You can run the visualizer either under Windows or from UNIX. If running under UNIX, make sure ReflectionX is running and that your display is set up properly. If you can start emacs in a separate window (i.e., run emacs & successfully), that is good enough.

XI. Detailed Requirements

You are expected to turn in all your code by 11:00 pm on the deadline mentioned at the top of this page. Use the turnin utility to submit your project. This project is called "project2B" in the turnin system.

Required Above and Beyond Extension

For ths assignment, beyond the basic requirements, you must implement one Above and Beyond extension. You may choose any of the listed extensions or try to come up with one yourself (please contact the course staff first to make sure your extension is within the workload we are expecting you to have in this assignment).

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: all improved to grow as necessary
(code from Phase A) ThreeHeap.java, a growable 3-heap priority queue
MazeRunnerLauncher.java -- Main launcher file, with added options to invoke your mazerunners, etc.
BFSMazeRunner.java -- MazeRunner based on breadth-first-search
DFSMazeRunner.java -- MazeRunner based on iterative depth-first-search
BestFirstMazeRunner.java -- MazeRunner based on best-first-search
The code and related documentation for the required Above and Beyond extension.

The three maze solvers should all be capable of displaying their progress in some way through the visualizer. See the writeup for Phase A for more details on these three search algorithm.

README Questions

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:

Give a high-level summary of how you implemented the recursive DFS algorithm iteratively. What differences did you note between these two algorithm design techniques? Which would you use for DFS? Other algorithms?
Why is it more important for DFS than BFS to check whether a cell has been visited yet?
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)?
In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
What kind of search algorithms in general (if any) are guaranteed to find the shortest path to the exit? Do the three you implemented fall in this category?
What did you enjoy about this assignment? What did you hate? Could we have done anything better?

XII. 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. Be sure to review the grading guidelines and devote appropriate portion of your effort on correctness (40%), architecture and documentation (30%), and README (30%).

XIII. Going Above and Beyond

The following suggestions are meant for you to try if you finish the requirements early. They will be worth a nominal amount of extra credit. Be sure to clearly describe what you did and how to run it in your README.

Write an additional pointer-based heap implementation (either a LeftistHeap or a SkewHeap). In your README, write a paragraph on the tradeoffs between a pointer vs. array-based heap. Some possible topics to cover include runtime, coding complexity, and memory usage.
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 at the entry on A* in the Wikipedia 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.)
Do something cool with the visualizer. Please let the staff know what you're going to do before you start.
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 about the basic design specifications, check with the staff, and document what you did. Of course, your code should still meet the basic requirements.

XIV. 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. Follow the normal turnin procedures, using the name "project2B" for this turn-in. You should submit:

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

For the hardcopy, please place the README 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). Also, please be sure to follow the printing instructions as this ensures a consistent style for the TAs to grade.