Assignment 2: Spam in a Maze!
Due Monday, February 2 by 11:59 PM
Recommended Reading: Keller, Chapter 7, pages 239-242.

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.

1. A Gridpoint 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. Notice that this class is virtually identical to the Point class that we have grown to know and love. The main difference is that while a Point had x- and y-coordinates, our new Gridpoint class calls these internal variables row and column instead. This will make things a bit more convenient as we proceed.
   
   
2. A GridpointQueue class which defines a queue of Gridpoints. 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 Gridpoints rather than integers.
   
   
3. 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.
   
   
4. 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 Gridpoint 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 (5 bonus points) 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 rectangular 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.

Hint: Notice the variable inStream in the loadMaze method. This variable is of type FileInputStream and FileInputStream has a method called available() which returns an integer representing the number of symbols in the file. Play with this to see if white space and carriage returns are counted as symbols! In any case, this method is the secret to all happiness.

In general, how do you find out about the built-in "features" in Java? A great place to look is the official Java Specification web site. You can also find the link from the "Reference Guides and Software Information" link on the CS 60 homepage.