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

The solution displayed above corresponds to the following solution path:

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

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

IX. Maze Visualization

      % 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:

• (from part A)QueueAr.java, StackAr.java, BinaryHeap.java, all improved to grow as necessary.
• (from part A)ThreeHeap.java, a growable 3-heap priority queue.
• 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

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.

• 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, memory usage, etc.
  Implementation: create a new MazeRunner class BestFirstMazeRunner_Pointer.java that utilizes this heap to demonstrate how this works.
• 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)? Then, 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.
  Implementation: create a new MazeRunner class BestFirstMazeRunner_Heuristic.java that utilizes this heuristic to demonstrate how this works.
• We saw that, in general, a truly random algorithm for maze search (ie, the RandomMazeRunner) performed poorly. However, algorithm research in recent years has focused on the well-applied use of randomization, with some dramatic results. Design and implement a new randomized maze runner (or modify one of your existing maze runners), and answer the following questions: (1) in what ways do you think your randomized algorithm is "better" than the analogous deterministic algorithm? Worse? (2) present a maze in which the randomized algorithm performs (in general) better than a deterministic algorithm. (3) If the deterministic algorithm does as good as, or better than, the randomized algorithm in some mazes, present an example. If such a maze does not exist, explain why.
  Implementation: create a new MazeRunner class RandomMazeRunner_Improved.java that utilizes this randomization to demonstrate how this works.
• Do something cool with the visualizer. Please let Luke know what you're going to do before you start.
• Go all out: We're letting you express your creative side here. 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 Luke, and document what you did. Of course, your code should still meet the basic requirements.

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:
       ((SquareCellMaze)maze).printAccessedCount();
   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!