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, '
|' are used for walls, '
+' 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 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.txtTake 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 VisualizationYou 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:
You will also need to include a README which contains the following information:
Also, please answer the following questions (justify your answers, of course; 3-4 sentences each should be fine):
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: