Homework #1 (h1)
Overview
We have written a "maze generation and traversal" framework for you to modify. The framework already generates mazes and can traverse them using a depth-first search strategy. Your assignment is to implement breadth-first search and A* ("A star" search).
Due Date
This assignment is due at 12:01am on Thursday, January 24th, 2008. See the grading policy for information about late submissions.
Getting the Code
You should already have checked out the comp314 repository as part of the previous homework. From inside your own homework/turnin directory, run the following command:
svn update
A directory called h1 will appear alongside your existing h0 directory. Inside h1 you will find code that will serve as a starting point for your homework.
Framework Details
The code provides a main class called MainWindow which provides a GUI for the maze visualizations. Even without your additions, the code is runnable. To execute the program, run the following command from h1/src:
javac maze/MainWindow.java java maze.MainWindow
This will launch the maze GUI.
The Maze GUI allows you to generate various random mazes using the "New" button. You can traverse a maze by pressing the "Depth-First" button. It will show you how it traverses the maze and leave a path in red of the DFS path from source to goal. You can clear the color-codings of the traversal with the "Clear" button.
Obviously, "Breadth-first" and "A*" are not yet implemented and will do nothing.
In addition to the GUI, we have provided a small, hardly-exhaustive, test file for JUnit that will do a basic test of DFS. YOU ARE NOT REQUIRED TO WRITE TEST CLASSES FOR YOUR CODE. I repeat, YOU ARE NOT REQUIRED TO WRITE TEST CLASSES FOR YOUR CODE. Oh, and by the way, did I tell you that you do not have to write test classes for your code?
The test class provided is to demonstrate how we will be testing your code. You may write tests if you wish to help build your confidence in your code, but it is not required.
To run the provided test class, from the h1/test directory:
java -cp $CLASSPATH:../src org.junit.runner.JUnitCore maze.algorithm.DFSTest
Integrating With the Framework
The two files you need to change are found in h1/src/maze/algorithm. and are named BFS.java and AStar.java. Both implement the maze.Search interface but are just stubs. You need to fill in the stubs to make the program work.
You need to implement the two maze.Search methods for both of the stubs. These are:
public void addSearchListener(SearchListener listener);
public boolean search(int startX, int startY,
int goalX, int goalY,
LegalMoveGenerator g);
The first method, addSearchListener is basic. You just need to add the provided listener to a data structure of your choice. A Java collections class, such as HashSet, is an excellent choice.
The search method is where your algorithm code will go. Obviously, the arguments include a starting coordinate in the maze and a goal coordinate in the maze. For every coordinate, the LegalMoveGenerator g can provide you with a Set of legal moves, each move stored as an x,y coordinate in a two-element array (e.g. (x,y) = {x,y}). These moves are legal from the point-of-view of the maze, not the algorithm.
When constructing your algorithm, you need to use some "hooks" to keep the GUI apprised of your progress. Look at SearchListener for the defined signals and at DFS for an example. You will not need all signals for your algorithms. For example, there is a signal that indicates backtracking. This signal has no meaning for BFS and A*.
ONE VERY IMPORTANT POINT: For both BFS and A* there is no way to know the correct path from the start to the finish until the goal node is actually encountered. The path will have to be reconstructed and you will have to signal the listeners of the change in room status.
You will likely have questions about the framework. Contact your TAs or labbies or stop by IRC for help.
Submission
You will submit this assignment through subversion, similar to the submit process for h0. We provided the starting code to you by copying it to your turnin directory, so all you have to do is make your changes and svn commit them. The contents of that directory (in the repository) after 12:01 on the due date will be your submission.
Eclipse
Want to use Eclipse for this homework? See here.