Assignment 2: Spam in a Maze!     [100 points]
Due Wednesday, Sept 13 by 11:59 PM (Part 0 Due Sunday, Sept 10 by 11:59pm)
Recommended Reading: Keller, Chapter 7, pages 239-242.

Objevtives:

• Implement breadth first search to find the shortest path throuh a maze to a can of spam.
• Extend a moderately sized Java program with new functionality.

If you finish early, there is an optional bonus problem that's a lot of fun also.

Part 0: 5 points, due SUNDAY, SEPTEMBER 10, 11:59pm

Read the rest of this assignment and all of the provided code and answer the following questions. Feel free to discuss any or all of these questions with the grutors or with others in the class (although you should each turn in your own writeup). Write your answers in a file called Part0.txt, and when you are finished, submit this file using cs60submit.

1. In class we saw that BFS keeps track of each node's parent in performing the search.
   1. Give one reason why the algorithm keeps track of a node's parent as it is discovered.
   2. Explain briefly how your java implemetation will keep track of each node's parents. (e.g., something like "Function X will set object Y's member variable Z to point to object B" where you fill in X, Y, Z, and B).
2. Why do MazeBFS elements store their row and column position (give at least one reason)?
3. Does BFS() in the MazeBFS class need to modify its MazeBFSElements? If so, what modifications does it need to make?
4. Below we warn you to build and test your code incrementally. Describe one small logical piece of your BFS() function that you could build and test incrementally and describe how you would do this testing.

Part 1: 95 Points, due Wednesday, Sept 13 at 11:59pm

First, 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 then write your own testing program that creates a queue and then enqueues some data, dequeues some data, and prints the contents of the queue. Now that you have the MazeElementQueue written and tested, move on to writing the main program MazeBFS. In MazeBFS, write just a bit of code and then test it before moving on to the next logical part.

You may assume that a maze will always be 10 by 10 and that the entire perimeter of a maze will be entirely made of walls (except in the bonus problem, should you wish to do it).

You should assume that a single step is a move that is due north, south, east, or west. One cannot move from a node to one of its four diagonal neighbors in one step -- that's two steps away!

Here are the classes and files that you'll need to get this program working:

• 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
Notice that all of these items are public. One could argue that they should have been made private. However, this is a very specialized class that will only be used by your program and not "the outside world". Therefore, for simplicity, we've made these public so that the rest of your code can easily use the MazeElement.


• 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, 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.

A note on elegance and design: In your breadth-first search algorithm you will need to examine all 4 neighbors of the "current" maze element. It may be tempting to have essentially the same (or very similar) code replicated for each of the 4 prospective neighbors. Replicating code like this is inelegant and you should avoid it. Why? For one thing, imagine that you had 8 prospective neighbors (you were allowing diagonally adjacent nodes to be considered neighbors) or, worse yet, you were operating in 3-dimensions and had perhaps 26 prospective neighbors! Then, replicating the code 8 or 26 times would be nasty! Moreover, even with just 4 prospective neighbors, the code is more readable and easily debugged and modified if the "common code" appears just once. Think about clean and elegant ways that you might do this and try to implement that in your code.

A note on debugging: 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 print statements to aid in debugging. If your code is behaving funky, print out the contents of the important variables and data structures so that you can trace the behavior of your program by hand and compare it to what the program is doing. This is another SECRET TO ALL HAPPINESS! 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. You can use cs60submit multiple times, once for each file you wish to submit. Alternatively, you can submit multiple files at the same time. For example, typing cs60submit spam.java foo.java bar.java will submit the three files spam.java, foo.java and bar.java. Yet another alternative is to simply type the command cs60submitall with nothing else. This will submit every java file in the directory in which you're currently residing! Be sure to call the MazeBFS class MazeBFS.java. Our grading scripts look for exactly this file name.

Optional extra credit: 3D Mazes! [7 Points]

Here's a fun bonus problem that extends what you just did. Please be sure to submit the regular part of the assignment before submitting the bonus problem.

Let's now assume that the maze is 3-dimensional. Each "floor" of the maze is still 10 by 10, but there can be an arbitrary number of floors.

Write a program called MazeBFS3D.java that takes in one or more files on the command line, each of which is a 10 by 10 maze. The first file is the first floor of the maze, the next file is the second floor of the maze, and so forth. For example, if there are just two floors, we might have files named floor0.maze and floor1.maze and we would run our program by typing

% java MazeBFS3D floor0.maze floor1.maze

• The boundaries of the maze are still marked by '*' symbols. Exactly one location in the entire maze (over all of the given floors) contains a 'S' indicating the start position and one location contains a 'D' indicating the destination position.
• One can move up one floor if and only if the current cell contains the symbol 'O' (upper case Oh) and the floor above contains the symbol 'O' at the same row and column. Similarly, one can move down one floor if and only if if the current cell contains the symbol 'O' and the floor below contains the symbols 'O' in the same row and column. That is, 'O' corresponds to a stairway between floors.
• You should no longer assume that the maze is delimited by walls ('*' characters) at the boundaries! The maze can be open at the boundaries.
• The program should infer the number of floors from the number of files provided at the command line.
• The program should show the floors before and after computing the shortest path from 'S' to 'D'.
• Your code should comprise files named MazeBFS3D.java (containing the main executable program), MazeElement3D.java (defining a 3D maze element), and MazeElement3DQueue.java (defining a queue of MazeElement3D objects).
• The directory /cs/cs60/assignments/assignment2/bonus contains the files floor0.maze and floor1.maze used in the example below.
• Please submit all of your files: MazeElement3D.java, MazeElement3DQueue.java and MazeBFS3D.java.

7 % java MazeBFS3D floor0.maze floor1.maze
Here's the maze:
Floor 0
******  **
 S *  *  *
*  *  *O *
*     *  *
         *
*  *     *
*  *  *  *
*  *  *   
*        *
***  *****

Floor 1
*  *******
*   *     
       O *
*   *  * *
* * ******
*        *
* ********
     *   *
*      *D*
***    ***

-----------------------------------
And here's the solution:
Floor 0
******  **
 So*  *  *
* o*  *O *
* oooo*o *
     ooo *
*  *     *
*  *  *  *
*  *  *   
*        *
***  *****

Floor 1
*  *******
*   *     
 ooooooO *
*o  *  * *
*o* ******
*o       *
*o********
 oooo*ooo*
*   ooo*D*
***    ***