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.
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.
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
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
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.
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.
The methods of the Square class are mainly getters and
setters. Square also has a toString method that you may find
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:
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:
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.
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.
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
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
Then apply the following step repeatedly
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 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:
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.
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
To summarize, your responsibilities in completing the maze
application are as follows:
Create a plain text file called "README" that contains the following information: