Computer Science 60
Principles of Computer Science
Fall 2003
Assignment 2: Spam in a Maze!
Due Monday, September 15 by 11:59 PM
The objective of this assignment is to write a program for finding the
shortest path through a maze using the breadth-first search algorithm
described in class. It's a lot of fun but do start early.
Here's a major sanity-preserving tip: Build this program
incrementally. After each increment, test what you've done (perhaps by
writing a simple testing program) to give you confidence that this
part works. This is the SECRET TO ALL HAPPINESS! For example, you
will need to implement a class defining a queue of points. Write that
class and test it before moving on. Then, in MazeBFS, write just a
bit of code and then test it before moving on.
Here are the parts that you'll need to get this program working:
- A Point class which stores points with integer coordinates.
This will be used to keep track of the point at which you are currently
searching in the maze.
You'll find this class (we've written it for you) in the directory
/cs/cs60/assignments/assignment2. Please do not modify
this class.
(Remember that our convention is to store coordinates in row major form.
Thus, the point (3, 4) corresponds to row 3 and column 4 of the maze!)
- A PointQueue class which defines a queue of Points.
The queue should be implemented as a linked list. You will find
the outline of this class in the directory
/cs/cs60/assignments/assignment2. You should fill in
the code for each of the methods (toString is optional but
very handy!). It will be a straightforward modification of the integer
queue that we discussed in class. You will, of course,
need a Node class which can store Points rather
than integers and this is provided for you.
- A MazeElement class which represents the individual
cells in the maze. This class is already written and is available
in the directory
/cs/cs60/assignments/assignment2. Please do not modify
this class.
- The MazeBFS class which contains the main
program. Please look at the file MazeBFS.java
in /cs/cs60/assignments/assignment2. You will notice
that we have supplied you with the main method, the
location method, and the loadMaze method. Your
job is to write the BFS method (which is the heart of the program)
and the draw_solution method. Note that all methods in this
class must be static as will be discussed in class.
Your program should display the shortest path through the maze using
the symbol 'o' (lower case letter oh) for the path.
For debugging purposes, it may be very helpful to you to print out the contents of the point queue during each iteration of the breadth-first search.
It may be useful to add other output statements to aid in debugging.
Do remove these debugging aids once your program works and you are ready
to submit it.
In the directory /cs/cs60/assignments/assignment2 you will also
find three sample 10 by 10 mazes called test1.maze,
test2.maze, and test3.maze. You can run your program on these mazes by typing
java MazeBFS test1.maze, for example.
You can also create your own mazes by creating a text file with 10 lines
of characters, each of which has exactly 10 characters (no extra spaces at the end of any line!).
Please submit ALL of the java files that your program uses
except for the Point and MazeElement classes which
we have supplied for you.
Be sure to call the MazeBFS class MazeBFS.java. Our
grading scripts look for exactly this file name.
For optional extra credit after submitting MazeBFS.java,
take a look at the provided
loadMaze method in MazeBFS.java and generalize it
and the rest of the program to handle mazes of arbitrary height and width
(not just 10 by 10). You should assume that the file will contain a
rectangular maze of some height and some width, but the height and width will
not be specified explicitly in the file (that is, the file will not contain
numbers with the height and width; your program will need to infer the height
and width by itself!)
Submit this class in a file called MazeBFSExtra.java.
Last modified September 2003 by Ran Libeskind-Hadas