Assignment 2: Spam in a Maze!     [100 points]
Due Monday, January 31 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 MazeElements (individual cells in a maze). 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.

You may assume that a maze will always be 10 by 10 (except in the optional bonus problem below, if you choose to do that) and that the entire perimeter of a maze will be entirely made of walls (again, except in the bonus problem).

• 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. As you'll see, each MazeElement cell contains
  • its row and col, both ints
  • a char named contents, which is what's in the cell
  • a boolean flag named visited
  • a MazeElement reference named parent



• A MazeElementQueue class which defines a queue of MazeElements. This queue should be implemented as a linked list. You will find a skeleton 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!). You will, of course, need a Node class which can store MazeElements rather than integers -- for simplicity, that should appear in the same file, named MazeElementQueue.java. Again, don't write this file from scratch -- use the skeleton provided.
  
  While the data members of the Node class should be public, remember to keep the internal data members of your queue private so that an outside user cannot tamper with them! Also, you don't need to worry about building an interface, e.g., QueueADT for the MazeElementQueue -- it's a fairly specialized data structure, and our primary concern here is supporting breadth-first search.



• 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 10 characters in it.

Please submit ALL of the java files that your program uses except for the MazeElement class 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 in two ways: (1) allow arbitrary maze sizes (any height and any width, but continue to assume that it is retangular) and (2) allow mazes that do not necessarily have walls ('*') on all of the edges of the maze. The potential lack of walls on the edges mean that you need to more explicitly worry about out-of-bounds conditions!

Submit this class, as class MazeBFSExtra, in a file called MazeBFSExtra.java.

Hint #1: Notice the variable reader in the loadMaze method. This variable is of type BufferedReader. The key to the first part of the extra credit is to understand how objects of type BufferedReader behave at the end of a file... . 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.

Hint #2: For one possible approach to this problem, it helps to make the maze variable a private static data member of the MazeBFSExtra class.