CMSC 341 Fall 2008
Project 2

Assigned	Wednesday, Sep 24, 2008
Due	Sunday, Oct 12, 2008 at 11:59 PM
Updates
	The algorithm for searching for the goal previously had you mark maze cells as visited when they are taken off of the agenda. It is better to mark them as visited when they are put on the agenda. The description of the algorithm below has been modified to reflect this change.
	The character used to mark the starting point is a lower case letter O, not an upper case letter O or a zero.
	The project due date is Sunday, October 12th by 11:59pm. This is what the syllabus says, but previously the project description said Wednesday, October 12th.
	Please read carefully the information below about what to submit. In particular, do not submit your javadoc. Rather, your build.xml must have a doc task that will build it for you.

Background

Given a map, (most) people have little difficulty planning a route from where they are to where they want to go. In this assignment you will implement an algorithm for finding your way through a maze. Somewhat more sophisticated versions of this algorithm are used everywhere from computer games to Google Maps to GPS car navigation systems.

Input and Output

Your program will be run with two command line arguments. The first will be the name of a file containing a maze. The second will be either the string stack or queue. Of course, you should check to ensure that the correct number of arguments is given and that the named file can be opened for reading. An example file is shown below:

10 12
############ 
#.#........# 
#.#.######.# 
#.#....#...# 
#.###.*#.#.# 
#...####.#.# 
#.#.#..#.#.# 
#.#.#.##.#.# 
#o#......#.# 
############

The first line of the file contains two integers, which are the height and width of the maze, respectively. The maze is made up of grid cells that can be any of the following:

. - open space
# - wall
o - starting location
* - goal location

Your task is to write a program that determines whether there is a path from the starting location to the goal location that traverses only open spaces. You can move north, south, east, or west. That is, from your current location you can move up or down one row (staying in the same column) or left or right one column (staying in the same row).

Maze files will always start with a line containing two positive integers separated by white space. Immediately following that line will be a number of lines equal to the height of the maze. Each such line will contain a number of characters equal to the width of the maze indicating the contents of each maze cell in that row and may contain trailing white space. Maze edges are guaranteed to be walls.

Given a maze file as input, your program should echo the maze (as in the diagram above), and determine whether a path exists from the start to the goal and print that information. If a path exists, print another copy of the maze with the maze cells on the path your program found marked with the + character, like this:

10 12
############ 
#.#++++++++# 
#.#+######+# 
#.#++++#+++# 
#.###.*#+#.# 
#+++####+#.# 
#+#+#..#+#.# 
#+#+#.##+#.# 
#o#++++++#.# 
############

Note that only cells on the path from the start to the goal should be marked with +. Cells that your algorithm visits looking for a path but that are not on the path should not be marked in this way.

The Algorithm

The algorithm for finding a path through the maze is outlined below. It requires that you add maze cells to an agenda which, for this project, will be either a stack or queue (depending on the value of the second command line argument) of maze cells that are to be explored.

add the maze cell which is the starting location (which might have been identified when the maze was loaded) to the agenda and mark it as visited
while the agenda is not empty
- current = get next maze cell from the agenda
- if current is the goal location (which might have been identified when the maze was loaded), terminate
- add the maze cells to the immediate north, south, east, and west of current to the agenda if they are not walls and have not already been visited and mark them as visited
tell the user there is no path to the goal location

Because the path you discover will depend on the order in which you add the neighbors of the current cell to the agenda, you must always add neighbors in this order: north, south, east, west. Of course, if one of those neighbors is a wall or was previously visited, do not add it to the agenda and move on to the next neighbor in the ordering.

To implement this algorithm, you'll need a Maze class, instances of which contain a 2D array of MazeCell objects. This class should also support reading mazes from files and printing them (via a toString method). Each MazeCell should clearly record what that cell contains (wall, start, goal, nothing) and whether it has been visited. You may, and probably will, need to keep track of additional information in maze cells.

Depending on whether you use a stack or a queue as the agenda, the paths you find may differ. To facilitate experimentation with this, you'll need to define an Agenda interface that supports the following operations:

Add an item to the agenda
Return the next item from the agenda without removing it (i.e., peek)
Return the next item from the agenda and remove it
Determine whether the agenda is empty or not

Note that the Agenda interface must be defined as generic so that it can hold objects of any type, though for this project the agenda will hold MazeCell objects. Then you should create two classes that implement the Agenda interface, one that uses a stack to store items and another that uses a queue. Again, each of these classes must be generic. You can use any Java class to get the desired stack or queue behavior. Both can be layered easily on top of java.util.LinkedList.

Very roughly, your main() could look something like this:

Maze maze = new Maze();
maze.load(args[0]);
System.out.println(maze);

Agenda<MazeCell> agenda;
if (args[1].equalsIgnoreCase("queue"))
  agenda = new QueueAgenda<MazeCell>();
else 
  agenda = new StackAgenda<MazeCell>();

if (maze.solve(agenda)) {
  System.out.println("Maze is solvable");
  System.out.println(maze);
} else
  System.out.println("Maze is NOT solvable");

Questions

Write brief (one or two paragraphs should suffice) answers to the following questions and submit them through CVS in a file named questions.txt. Your answers will be worth 10 points (out of 100) on your project grade.

Is either of the methods for storing maze cells (stack or queue) guaranteed to find the shortest path to the goal? If so, which one and why? If not, why not? Note that this is not asking if one is more efficient than the other, but whether one finds the shortest path regardless of the cost of finding the path.
Construct a maze that's at least 6-by-6 (including boundary walls) in which the goal is adjacent to the start but it (the goal) is the last cell explored by the stack-based agenda. Remember the NSEW order for exploring neighbor cells.

Submission

You must use CVS to check out your module in the Proj2 repository and to check in your code. That must include an ant build.xml file with targets for creating javadoc (named "doc"), for running your program (named "run" and that allows the command line arguments to be specified with -Dargs, like this ant -Dargs="arg1 arg2 ..." run), and for compiling your code (this must be the default target). The build.xml file that comes with your module in the Proj2 repository has all of this. Do not submit or put under CVS control your javadoc output. We will build it with the "ant doc" command. See the projects page for more information on all of these topics.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.