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.
Remember, the due date is firm. Submittals made after midnight of the due
date will not be accepted. Do not submit any files after that time.