Lab 4 - A-Maze-in'!

CSCI 151
Fall, 2018
Due:  11:59 pm, Sunday, October 14

In this lab you will use the power of a stack and a queue to find your way through a maze.  The purpose of the lab is to:

I'm providing some code to help you get started in this zip file:  lab4.zip.  The file also contains some sample mazes.

The maze program contains several pieces that need to fit together to make everything work properly.  So it's important to test each piece before going on to the next.

Part 1 - Representing the Maze

First, consider a basic maze.  It has walls and pathways, and it has one (or more) starting point(s) and one (or more) exit point(s).  (For this lab, we'll keep things simple and assume it has no more than one of each.)  Furthermore, one wall is just like another, and any open space (not including start and finish) is also identical.  So, we can think of a maze as being made up of individual squares, each square either empty, a wall, the start, or the exit.

Below is a graphical representation of the maze found in the file maze-2. The green box represents the start, the red box the exit, and the black squares the walls.

sample maze

The problem is to find a pathway through the maze from the starting point to the exit.  This is done largely by trial and error:  try one path, and if you run into a dead end or a place you've already been before, back up and try again.  Computer scientists call this backtracking.  This basic approach still leaves some room for different ways of doing things; in particular, how to keep track of where you've been before, how to back up, etc.  We'll take a look at an algorithm to solve the problem a little bit later.

First, we need to have a way to represent a Maze in a program.  Actually, we'll have two representations:  a representation in a text file (that we can read in as input), and a representation as a Java class (that we can apply our algorithm to).

The representation of a maze in a text file works like this:  The first line of the file contains two integers.  The first indicates the number of rows (R), the second, the number of columns (C).

The rest of the file will be R rows of C integers. The value of the integers will be as follows:

    0 - an empty space
    1 - a wall
    2 - the start 
    3 - the exit 

In terms of coordinates, consider the upper left corner to be position [0,0] and the lower right to be [R-1,C-1].

For example, this is the text version of the maze above (start is at [6,4] and exit at [6,11]).

7 13
0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 1 1 1 1 1 1 1 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0
0 1 0 1 1 0 0 1 1 1 0 1 0
0 0 0 1 0 0 0 0 0 1 0 1 0
0 1 1 1 1 1 0 1 0 1 0 1 0
0 0 0 0 2 0 0 1 0 0 1 3 0

To represent a maze in our Java program, we'll use two classes:  Square and Maze.

The Square Class

I'm providing a Square class that represents a single square in the maze.  A Square has an instance variable type that represents its type of square (space, wall, start, or exit).  It is also useful for a square to know where it is positioned in the maze, so it has instance variables row and column which represent its position.

The remaining instance variables (visited, onpath, and back) will be used by the maze solver.

public class Square {

   private int type;  // one of SPACE, WALL, START, or EXIT
   private int row;
   private int column;

   private boolean marked;
   private boolean onpath;
   private Square back;

I've also defined several constants with the keywords static final.  You can refer to these in your code if you like; for example, Square.SPACE, Square.START, etc.

public static final int SPACE=0, WALL=1, START=2, EXIT=3;

The methods of the Square class are mainly getters and setters.  Square also has a toString method that you may find useful.

The Maze Class

We'll also need to create a Maze class that stores the logical layout of a maze.  I'm providing a starter version that contains the following instance variables:

   private int height; // the number of rows in the maze
   private int width;  // the number of columns in the maze
   private Square[][] grid;  // 2-d array of Squares representing the maze
   private Square startSquare;
   private Square exitSquare;

I've also included some getters and setters and a toString method.  The reset method resets the maze so it can be solved again by the maze solver.  You may add additional methods if you like, but I wouldn't recommend changing any of the methods that I've written.

You're responsible for writing the following methods in the Maze class:

public static Maze loadMaze(String fname)
Creates a new maze.  The maze layout (in the format described above) is contained in the file named fname.
Start by instantiating a Maze with the no-argument constructor.  Then create a Scanner to read from the file.  Read all of the information from the file and use it to assign values to all of the fields in the Maze object.
If the specified file cannot be found, Java will throw a FileNotFoundException.  You need to declare that this method throws FileNotFoundException.  If the file exists but you encounter an error in the input file, you should throw a RuntimeException with an appropriate message.  The maze application will catch it and display the message.
public ArrayList<Square> getNeighbors(Square sq)
Returns an ArrayList containing the neighboring Squares of the parameter Square sq.  There will be at most four of these (to the North, East, South, and West) and you should list them in that order.

Before you continue, you should test that your Maze class works correctly. You can do this by creating a JUnit test.  Among other things, this test should load a maze from one of the supplied files, get the neighbors of some specific square (the start square, for example), and assert that (1) there are the correct number of neighbors, and (2) the neighbors are in the correct locations.  You probably should do this for the corners and border cases, at least.  There should also be a test to print out the maze, and to confirm your getStart and getFinish methods return the correct squares.

You may assume that any well-formed maze will have exactly one start and exactly one finish. You may not assume that all valid mazes will be entirely enclosed within walls.

Part 2 - Stacks and Queues

We've been talking about stacks and queues in class, and now it is your time to put that theory to good use.  Write two classes MyStack<T> and MyQueue<T> that implement the supplied interfaces StackADT and QueueADT, respectively.

MyStack
An implementation of the StackADT interface that is capable of storing an arbitrarily large amount of data.  Use an ArrayList for storage.
MyQueue
An implementation of the QueueADT interface that is capable of storing an arbitrarily large amount of data.  Use a linked-node implementation.


The methods you need to write for each of these classes are specified in the interfaces specified in the starter code.  Be sure to throw the correct exceptions.  If you get stuck, you can always peek at the text to help you out.  Don't copy anything directly, but you may use it as a guide.  This part of the lab is not meant to take you very long, so if you find you are spending a lot of time on it, check with the text to make sure you are on the right track.

For the linked queue implementation, use a nested QNode class to handle the nodes.  (I've included this in the starter version of MyQueue.)  When you enqueue a data item, you need to create a new QNode, insert the data item, and attach it to the linked list.  Note that a MyQueue has instance variables of type QNode called front and rear, which refer to the first and last nodes of the queue.

Implementing the Worklist interface

In addition to implementing StackADT or QueueADT, both MyStack and MyQueue need to implement an additional interface called Worklist.  This allows them to be plugged in to the maze solving algorithm.  The interface contains the methods add, remove, peek, isEmpty, and clear.  MyStack and MyQueue should both already have the methods peek,  isEmpty, and clear.  You just need to write add and remove methods for them..  The add method for MyStack should just call push; the add method for MyQueue should just call enqueue.  (Don't duplicate the push or enqueue code.)  Remove can be handled with calls to pop and dequeue. 

Before continuing, you should add JUnit tests for MyStack and MyQueue that perform testing on your data structures.  (Call these MyStackTest and MyQueueTest.)  Don't forget to test the exceptions too.  If you'd like to test your data structures by confirming that they match the behavior of Java's (highly recommended), the closest structures are Stack and ConcurrentLinkedQueue.  Note that the names of the functions are different, so you'll have to make that adjustment to your testing code.

Part 3 - Solving the Maze

Now that you have a maze class and working stack and queue data structures, you can use them to solve mazes.  You'll next be implementing the application portion of the lab, writing a MazeSolver class which will attempt to find a path from start to exit in a given maze.  Without jumping over any walls, of course.

The maze solving algorithm you will use works like this:  begin at the start location, and trace along all possible paths to (eventually) visit every reachable square in the maze. If at some point you visit the finish Square, you've found a path.  If you run out of squares to check, there's no path to the finish.

Writing this down in pseudocode, we have the following:

At the start

  1. Create an (empty) worklist (stack/queue) of squares.
  2. Add the start square to the worklist.

Then apply the following step repeatedly

  1. Is the worklist empty? If so, the exit is unreachable; terminate the algorithm (the maze is not solvable).
  2. Otherwise, grab a square from the worklist.
  3. Does the square correspond to the exit square? If so, the finish was reachable; terminate the algorithm (you've found a solution).
  4. Otherwise, it is a reachable non-finish square.  If it hasn't been marked yet, then:

    • mark the square,
    • make a list of this square's neighbors; that is, all the adjacent locations (up, right, down, left) that are inside the maze and aren't walls, and
    • add them to the worklist for future reference

Note that this pseudocode doesn't depend on what kind of worklist you use (that is, a stack or a queue). The application needs to pick one when it instantiates the maze solver, but the algorithm should work for either type of worklist.

The MazeSolver Class

The application uses a class called MazeSolver that will implement the above algorithm with a given worklist.  The MazeSolver class should have private class members of types Maze and Worklist, and should have the following methods:

MazeSolver(Maze maze, Worklist worklist)
The MazeSolver constructor takes a Maze and an empty Worklist as parameters and stores them in its instance variables.  It also performs the initialization steps of the algorithm:  clearing the worklist and adding the start square to it.
public boolean isFinished()
a method that the application program can use to see if the maze solver has finished the algorithm (whether or not it has actually solved the maze.)
public boolean pathFound()
a method that the application program can use to see if this algorithm has found a path from start to exit in the maze; that is, it has solved the maze.
public List<Square> getPath()
return a list of the squares on the solution path from the start to the exit.  If the maze has not been solved, it returns an empty list.
public void step()
perform one iteration of the algorithm above (i.e., steps 1 through 4).
In order to keep track of which squares have already been reached, you will "mark" each square when you remove it from the worklist.  Then, before you add a square to the worklist, you should first check that it is not marked (and if it is, refrain from adding it).  Square has an instance variable called marked to allow you to keep track of this.
In addition, the algorithm must keep some information that will allow it to retrace the path, once a path has been found.  This can be done as follows:  when a Square is added to the worklist, have it keep track of which Square added it to the worklist. The instance variable Square back is included in the Square class for this purpose.  It acts as a backward pointer to the previous Square on the path that is being followed.  When a Square is being added to the worklist, you will set its back variable to point to the current Square.


Part 4 - Animation

If everything is working in your Maze and MazeSolver classes, you should be able to run the MazeApp program and get a GUI interface that will allow you to visualize the process of finding the solution of the maze.  You do not need to modify anything in this file. 

maze app start maze app parital maze app filled

The load and quit buttons operate as you might expect. The reset button will call the Maze's reset() method and then create a new MazeSolver. If you click on the stack button it will toggle between using a Stack or Queue to solve the maze.  (Take a look at the makeNewSolver method in MazeApp.java.  You'll see that it creates a new MazeSolver and passes to it either a MyStack or a MyQueue, depending on what the user has chosen in the GUI.)  The step button performs a single step of the MazeSolver and start will animate things taking one step per timer delay interval.  As the animation proceeds, marked squares are painted gray.  If the maze is solved, the squares on the solution path are painted yellow.  The getPath method that you wrote in MazeSolver.java is used to display the path in the bottom panel.

Putting it all together

To summarize, your responsibilities in completing the maze application are as follows:


Part 5 - Written Questions

Create a plain text file called "README" that contains the following information:

  1. Your name
  2. What is the Big-O complexity of your solver algorithm (in terms of m and n, the number of rows and columns in the maze)?  Give some justification for your answer.
  3. Which search algorithm do you think is better?  Give some examples from the test cases to support your answer.  Is one solver faster at finding solutions than the other? Does one solver find better solutions than the other?
Put everything (all of your .java files including JUnit test files, and the README file) into a single directory called lab4, zip it, and submit it through handin.  Don't include the maze files.