CSE 326 - Summer 2003 Homework #3 (part B)
The Search for a-MAZE-ing Donuts!
Assigned Monday July 7
Partner selection (if any) due by 9 p.m. Tuesday July 8
Part A "in-progress" checkin due by 11 p.m. Thursday July 10
Part B "donut-ready" checkin due by 11 p.m. Tuesday July 15
Writeup for part B due at beginning of class, Wednesday July 16
See the writeup for Part 1 for background information. Note that we have added some clarifications to the psuedo-code for BFS and best-fit-search, these appear in bold in the pseudo-code section.

VI. More Provided Code

For the second part of this project, we are providing code to read, parse, and build a Maze class which your algorithm will operate on, as well as a sample RandomMazeRunner. 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 /projects/cse/courses/cse326/03su/hw3. You can copy these files when logged in from any instructional machine. Further documentation on the Maze files architecture may be found here.

You will want to add all of the code from part A, including your changes, to this code.

VII. Maze Input and Output

The SquareCellMazeFactory class reads a maze file from a 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 directory that you can use to test your program. You should also consider writing (and sharing with your classmates!) other test mazes to run your MazeRunner on.

After solving a maze, a 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 spaces. On the next line should be the length of the solution path, and on the following line should be the number of nodes 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) 

The solution displayed above corresponds to the following solution path:

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

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

VIII. Getting Started

After combining your code from part A and the new provided code for part B, compile everything and try to run the provided mazeRunner:

      % java -classpath . RandomMazeRunner maze0.txt
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.

IX. Maze Visualization

You can 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 -classpath . RandomMazeRunner -v -t -w mazefile

The "-v" option turns on the visualizer, "-t" prints out some tracing information, and "-w" tells the algorithm to wait after processing each step. You can choose any (or no) options to use, but you must provide them in this order.

Try using the visualizer with the random solver so you can see how it works. If using the "-w" option, repeatedly press "Enter" in the console window (e.g. where you entered the command line to start the program) to progress through the maze. 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. Note also that to enable the "wait after each step" feature you must call waitForEnter() inside your main loop; see RandomMazeRunner.java for an example.

(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 (e.g., emacs &), then this is good enough).

X. Detailed Requirements

You are expected to turn in all your code (use the turnin utility to submit your project. This project is called "hw3b" in the turnin system).

Include the following files plus any others you find necessary:

The three maze solvers should all display their progress in some way through the visualizer. See the writeup for part A for more details on these alogrithms.

You will also need to include a README which contains the following information:

  1. The names of your team members and your team's name
  2. If you worked in a team, a breakdown of the work.
  3. (Answer this question before you begin) How long do you think this project would 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 team members, the 326 staff, or the Weiss book.
  6. An explanation of how to compile your program.
  7. A brief description of how your project goes "above and beyond" the basic requirements.

Also, please answer the following questions (justify your answers, of course; 3-4 sentences each should be fine):

  1. 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?
  2. Why is it more important for DFS than BFS to check whether a cell has been visited yet?
  3. 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)?
  4. In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
  5. Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
  6. Which search algorithms (if any) are guaranteed to find the shortest path to the exit? Which ones aren't?
  7. 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.

Each part of the assignment will be worth (approximately) the following. Please budget your time appropriately.

 40%   Program correctness (including boundary cases) and error-free compilation
 30%   Architecture/design of program. Style, commenting, layout. Other forms of program documentation.
 30%   README and answers to writeup questions

XII. Going Above and Beyond (for credit)

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.

XII. MazeRunner Competition!

As announced in class today, the mysterious benefactor of HW #3 appears to be sponsoring a competition to see who can create the best[*] MazeRunner. We can never be too sure of his motives, but it seems very likely that this will include some kind of prize for the winner, not to mention the certain esteem of the rest of the class.

[*] The "best" MazeRunner will be defined as the MazeRunner that touches (in any way) the smallest number of distinct maze cells. Note that is rather generous to algorithms such as RandomMazeRunner that might touch the same cell multiple times, but of course the best algorithms probably only need to look at each cell once. Test your program on different types of mazes, because we will be evaluating your program on some new mazes that you haven't seen yet.

To enter the competition, do the following:

  1. Copy these new versions of SquareCell.java and SquareCellMaze.java into your code. (If you've made any changes to these you want to keep, trying run Unix diff to see what has changed). This code will keep track of how many different cells your search touches.
  2. At the very end of your solveMaze() routine, add the line:
    This will cause your program to print out the number of distinct cells accessed, allowing you (and us) to see how well your MazeRunner works. This should be your very last line of output.
  3. Don't forget this! Pick your best MazeRunner, and name it BestMazeRunner.java. This code must run in the same way as the standard MazeRunners to enable us to test it. Submit this file together with everything else for part B's turnin, then wait for the award ceremony!