In this program y

ou are

given

2

classes to work with

:

1)

Maze

which is a

Maze

2)

MazeDisplay

which graphically displays the maze it is given.

Yo

u will also

use

:

1)

t

he Stack class that you wrote and submitted on HyperGrade this semester. If you do not have it, you

can use Javas built

-

in Stack class for a deduction on your grade.

Finally,

you will

write

:

1)

A

class called MazeSolver, which will be able to create a Maze

, set up a MazeDisplay,

and then solve

the Maze

.

It s

hould ha

ve a

method called

.

solve

()

,

which contains a

loop

which will run until the Maze

is solved or until the user says to quit.

Inside t

he loop, the us

er can enter Q

(or q) to quit, S (or s) to

save the current state of the MazeSolver, or just ENTER to do another move.

See below for details.

2)

A

class called

StartSolvingMaze.java, which will contain a main method that will start the whole

program. I

t should promp

t the user to enter the number of row

s and the number of col

umns, then

create an ins

tance of a Maze

Solver, passing in the number o

f rows and

number of

columns.

Once the

new MazeSolver

is created,

then

the

StartSolvingMaze

class should tell your MazeSolver

instance

to

.solve()

3)

A class called

R

esumeSolvingMaze.java,

which

will contain a ma

in method that will read in a

serialized MazeSolver (instead of creating a new one)

.

So it should ask the user to enter the n

ame of

the

file

that contains the serialized

class, then read it in and conv

ert it to the existing MazeSolver. Then

tell it to

.solve().

The

enumerated data type called

Maze.

Direction:

Look at the Maze.java file; it contains the code for the Maze.

You do not have to know or understand all the code for the Maze class, but

it uses a feature called

enumerated data

types

that you will use extensively.

At the very end of the

Maze

class is defined an

enumerated data type (

enum

in Java)

called Direction.

When working with a Maze,

you can use a

n enum

calle

d Direction, which

is either

UP, DOWN, LEFT,

or

RIGHT. Since Direction is defined inside Ma

ze, you have to refer to it as Maze.Direction

and refer to the

various directions as Maze.Direction.UP etc. You can use enumerated data types

as a type

in the same

way that you would use other types or classes. For example, you could have:

o

Maze.Direction

whichWay

;

//whic

hWay is a Maze.Direction

...

o

w

hichWay = Maze.Direction.UP;

//

...

so it can thi

s value, for example

o

Stack

myStack;

//Generics

Th

e Direction type

will be extremely important, as the Maze methods that you have available are expecting

Maze.Directions...

The

public Maze methods

:

Once a Maze is created, these are

its

public methods that

you will use

in your

MazeSolver

class

to decide where to move and

then tel

l the maze to move

there

:

.

get

CurrentRow()

//returns the current row

.

getCurrentCol()

//returns t

he current column

.

goalReached()

//returns true or false, depending on whether the goal is r

eached

.

move(Maze.Direction.UP)

//for example

...

this would

tell

the

current location to move UP

.

isOpen(Maze.Direction.RIGHT)

//for example

...

this would

return

a

boolean telling whe

ther or not

//

the Maze

is open from the current location going to the RIGHT

//

(whether

//

or not there is a wall there)

You are to write a program called

MazeSolver

.java

.

It should have:

Class data that store

s

a Maze and also store

s

the data structures you will use to solve it.

To solve it, you

will use

a

Stack and also a data structure to keep track of which cells in the Maze have been visited (see

the algorithm below). This class data will be eligible to be serialized

when the user chooses that option.

N

OTE:

you will also create an instance of a Maz

eDisplay, but do not declare it in the class data. It uses

the Thread class, which is not S

erializable.

So declare it locally in the solve() method.

A

parameterized

constructor that will receive a number of rows and a number of columns, both as ints. T

he

constructor will:

Create

the

new instance of a Maze

that you declared in the

data

, passing in the number of rows and the

number of columns.

Tell

the

Maze instance to do a

.buildMaze(

0

);

where

0

is the delay in milliseconds. The larger

the

delay, the slower

the build will be animated.

T

ell the

Maze instance to do a

.setSolveAnimationDelay(n);

where n is the delay in milliseconds

,

which is how long it will wait between moves. This is so the animation does not happen so fast

that

you cannot watch it. You can choo

se any delay you want.

Create

the

other data structures

that are declared in the class data

(the Stack and the data structure to

keep track of whether or not a cell has been visited)

A method called solve(),

which will contain the logic to actually solve the Maze. It should do the

following:

Create a new

instance of a

MazeDisplay, passing in the Maze

that

has already been

created

.

Once the Maze is built and displayed, you are to write code to solve it.

The algorithm is described

below. When you implement it,

y

ou cannot ch

ange or add code to the Mazes methods

, but only

use

Mazes

existing

public

methods

that are also described above

.

The basic algorithm

i

s

to try going UP, DOWN, LEFT, or RIGHT

(in any order)

to legally move through

the

Maze

,

taking care to go to a cell (location) that you have

NOT

already been to.

If there is no

new

location

to go

to

,

you have to use the Stack to backtrack.

This can be done

as follows:

Mark the current

(starting)

cell you are at as visited.

Tell the

user the

y are to enter Q to

quit, S to save to a file, or just ENTER to move.

Repeat the following actions

while

the goal location

has not been

reached

and the user does not say to Quit

{

Get the user

s next input

If the input is S or s, then ask for the file to serialize to and

serialize

this MazeSolver to that file.

But if the u

ser does n

ot type Q or q, then make a

m

ove, which

the logic below shows:

If

it is open

in the

Maze.Direction.UP

direction

and you have not visited the cell

above

you

,

then push

Maze,Direction.UP onto your Stack and ma

rk the cell you arrived at as visited. Tell the maze instance

to move

in the direction of Maze.Direction.

UP.

Else

...

i

f

it is open

in the

Maze.Direction.

DOWN

direction

and you have not visited the cell

below

you

,

then push Maze,Direction.

DOWN

onto your Stack and ma

rk the cell you arrived at as visited. Tell the

maze instance to move

in the direction of Maze.Direction.

DOWN

.

Else ....(try the same thing for the

Maze

.Direction.

LEFT direction

. Same logic

)

Else ...(try the same thing for the

Maze.Direction.

RIGHT direction

. Same logic

)

Else

you have co

me to a dead end. Pop the Stack to see the direction you came from. Tell the maze

instance to move in the opposite direction, which will accomplish the backtracking.

}

If the user quit

s, print

P

rogram ended without solving

.

If the loop ends with the Maze being solved

, print Maze is solved.

Hints

and

Suggestions

:

Be sure that the b

lack DOS window is the active window

(by clicking in it f

irst)

when you enter the S, Q,

or ENTER.

To keep track of which cells have been visited,

you c

ou

ld either

o

use a 2

-

dimensional array of

b

ooleans

that is the same dimensions as the Maze. Then

when you

arrive at a new Maze location, set the corresponding entry

in the

array to true.

o

O

r

...

create an ArrayList that holds Poi

nts. Then when you arrive at a new Maze location

, create a

new Point with the (row, col) and tell the ArrayList to add it.

To

check if a cell has been visited

be

fore, see if the ArrayList

.con

tains that

Point

If your logic causes the

Maze animation to just go back and forth between 2 cells, it means that you

are not

chec

king to see if a cell is

visited

correctly

Let the user type in the

complete file name

when serializing. D

o not put the .dat or any other extension on

for them.

Testing your program:

Since this

assignmen

t will not be using HyperGrade, you will have to test you

r program

by yourself. This will be easy

, since

there is no data

just

be

sure it can successfully solve

Maze

s

, quit,

serialize,

and read a serialized file.

There are also no late days to use so plan on submitting it on time!

Comments and formatting

:

Please have an opening comment which briefly describes the class. Each method

should also have an opening comment. There should be comments in the code to describe lengthy sections or to

help the reader understand tri

cky parts. For additional maintainability, code should be indented correctly and the

variable names should be meaningful.

T

his is impor

tant for maintainability

. D

eductions for lack of comments and

incorrect

formatting could be as high as 10% of the program.

Please submit

via

Canvas

: Y

our

Stack.java,

MazeSolver.java

,

StartSolvingMaze.java, and

ResumeSolvingMaze.java files

. Please be sure they are all named correctly and compile.

* This program implements a Maze. Internally, walls and data are stored

in a single 2D array; the entries whose row/col are even-odd or odd-

even

are the walls and the entries whose row/col are odd-odd are the cells

themselves. Therefore, a 4x5 maze will be stored in a 9x11 array so

the

walls can be stored as well as the cells. In the code, the variable

names

try to make it clear which it is working with (realRow vs arrayRow).

*/

public class Maze implements java.io.Serializable

{

//-------data

private int[ ][ ] mazeArray;

private int currentArrayRow;

private int currentArrayCol;

private int goalArrayRow;

private int goalArrayCol;

private int buildAnimationDelay;

private int solveAnimationDelay;

private boolean alreadyBuilt;

//-------constructors

public Maze(int numRealRows, int numRealCols)

{

//since the maze is being created, initialize

alreadyBuilt to false

alreadyBuilt = false;

//set the buildAnimationDelay and solveAnimationDelay to

0; they can be reset with methods

buildAnimationDelay = 0;

solveAnimationDelay = 0;

//make sure that the numRealRows and numRealCols are

both > 1 (start cannot == goal)

if (numRealRows < 2)

throw new IllegalArgumentException("number of

rows must be > 1");

if (numRealCols < 2)

throw new IllegalArgumentException("number of

columns must be > 1");

//create the 2D array to hold the maze (its even

rows/cols hold the walls, odd rows/cols hold the paint

mazeArray = new int[2*numRealRows+1][2*numRealCols+1];

//since the even values are the walls, set anything with

an even component to 1 (wall exists to start)

for (int row=0; row

for (int col=0; col

col++)

if (row%2==0 || col%2==0) //if either

dimension is even...

mazeArray[row][col] = 1;

//its a wall, so set value to 1

//initialize the currentArrayRow and currentArrayCol to

the upper left corner

currentArrayRow = 1;

currentArrayCol= 1;

}

// **************** methods

*******************************************

//equals - returns true if it equals what is received

public boolean equals(Object obj)

{

if (obj == null)

return false;

if (this.getClass() != obj.getClass())

return false;

Maze objMaze = (Maze)obj;

//now do the real check - do the arrays have the exact

same elements?

//build a single String out of all the elements in this

Maze, row major

String myElementsStr = "";

for (int row=0; row

for (int col=0;

col

myElementsStr = myElementsStr +

this.mazeArray + " ";

//build a single String out of all the elements in

argument Maze, row major

String objElementsStr = "";

java.util.ArrayList objElementsAL = new

java.util.ArrayList();

for (int row=0; row

for (int col=0;

col

objElementsStr = objElementsStr +

objMaze.mazeArray[row][col] + " ";

//if the 2 Strings are equal, then the original arrays

contained the same elements

return myElementsStr.equals(objElementsStr);

}

//------- setSolveAnimationDelay - sets the delay (milliseconds) for

the maze being solved (in case its animated)

public void setSolveAnimationDelay(int theDelay)

{

solveAnimationDelay = theDelay;

}

//------- buildMaze - builds the Maze; calls other buildMaze method

to set buildAnimationDelay to 0

public void buildMaze()

{

buildMaze(0);

}

//------- buildMaze - builds the Maze; receives a delay to slow it

down (in case its displayed)

public void buildMaze(int buildAnimationDelay)

{

//if this maze has already been built and it trying to be

built again, throw an exception

if (alreadyBuilt)

throw new IllegalStateException("cannot build

maze - it has already been built");

else

alreadyBuilt = true; //because we are NOW

building it

System.out.println(" beginning to build the maze with "

+ mazeArray.length/2 + " rows, " + mazeArray[0].length/2 + " cols");

//create a Stack to hold the cells we are visiting as it

is built (they will be stored as Points)

//and an ArrayList to hold the "neighbors" in the code

below

java.util.Stack cellStack = new

java.util.Stack();

java.util.ArrayList neighborAL;

//in the mazeArray, the even rows/cols are the walls, the

odd rows/cols are the cells

int numRealRows = mazeArray.length/2;

int numRealCols = mazeArray[0].length/2;

//calculate the total number of (real) cells to visit

int totalCells = numRealRows * numRealCols; //rows x

cols

//the odd rows/cols store the actual cells. Choose a

random cell to start.

java.util.Random gen = new java.util.Random();

int currentArrayRow = gen.nextInt(numRealRows)*2 + 1;

//ex: if 3 real rows, this is a random from 1,3,5

currentArrayCol = gen.nextInt(numRealCols)*2 + 1;

//same for cols...

int lastArrayRow = currentArrayRow;

int lastArrayCol = currentArrayCol;

mazeArray[currentArrayRow][currentArrayCol] = 2;

int numVisitedCells = 1;

//while all cells have not been visited...

while(numVisitedCells < totalCells)

{

//go to sleep to slow down animation (based

on its speed)

try{ Thread.sleep(buildAnimationDelay); }

catch(Exception ex) {}

//find all neighbors of currentCell with all

walls intact

neighborAL = new

java.util.ArrayList();

//try cell above it

if (inMaze(currentArrayRow-2,

currentArrayCol) && allWallsIntact(currentArrayRow-2, currentArrayCol))

neighborAL.add(new

java.awt.Point(currentArrayRow-2, currentArrayCol));

//try cell below it

if (inMaze(currentArrayRow+2,

currentArrayCol) && allWallsIntact(currentArrayRow+2, currentArrayCol))

neighborAL.add(new

java.awt.Point(currentArrayRow+2, currentArrayCol));

//try cell to the left of it

if (inMaze(currentArrayRow, currentArrayCol-

2) && allWallsIntact(currentArrayRow, currentArrayCol-2))

neighborAL.add(new

java.awt.Point(currentArrayRow, currentArrayCol-2));

//try cell to the right of it

if (inMaze(currentArrayRow,

currentArrayCol+2) && allWallsIntact(currentArrayRow, currentArrayCol+2))

neighborAL.add(new

java.awt.Point(currentArrayRow, currentArrayCol+2));

//if neighbors with intact walls exist...

if (neighborAL.size() > 0)

{

//choose a neighbor at random

int randomInt =

gen.nextInt(neighborAL.size());

java.awt.Point theNeighbor =

neighborAL.get(randomInt);

int neighborRow =

(int)theNeighbor.getX();

int neighborCol =

(int)theNeighbor.getY();

//knock down the wall in between

if (currentArrayRow != neighborRow)

//neighbor chosen was above or below

mazeArray[(currentArrayRow+neighborRow)/2][currentArrayCol] = 0;

//knock down wall in between

else if (currentArrayCol !=

neighborCol) //neighbor chosen was to the left or right

mazeArray[currentArrayRow][(currentArrayCol+neighborCol)/2] = 0;

//knock down wall in between

//push the current cell onto the

cellStack

cellStack.push(new

java.awt.Point(currentArrayRow, currentArrayCol));

//clear the current cell

mazeArray[currentArrayRow][currentArrayCol] = 0;

//make the new cell the current cell

currentArrayRow = neighborRow;

currentArrayCol = neighborCol;

mazeArray[currentArrayRow][currentArrayCol] = 2;

//add 1 to visitedCells

numVisitedCells++;

}

else

{

//clear the current cell

mazeArray[currentArrayRow][currentArrayCol] = 0;

//pop the most recent entry off of

cellStack and make it the current cell

java.awt.Point popped =

cellStack.pop();

currentArrayRow = (int)popped.getX();

currentArrayCol = (int)popped.getY();

mazeArray[currentArrayRow][currentArrayCol] = 2;

}

} //end while

//clear the cell that ended up as the current Cell

mazeArray[currentArrayRow][currentArrayCol] = 0;

//set the current cell to the upper left corner

currentArrayRow = 1;

currentArrayCol = 1;

mazeArray[currentArrayRow][currentArrayCol] = 2;

//current

//set the goal to the lower right corner

goalArrayRow = numRealRows*2-1;

goalArrayCol = numRealCols*2-1;

mazeArray[goalArrayRow][goalArrayCol] = 3; //goal

System.out.println("finished building the maze ");

}

//-------- getNumRows - returns the number of rows in the maze (from

user's perspective)

private int getNumRows()

{

return mazeArray.length/2; // divide by 2 for real

answer

}

//-------- getNumCols - returns the number of columns in the maze

(from user's perspective)

private int getNumCols()

{

return mazeArray[0].length/2; // number of columns in

row0 (divide by 2 for real answer)

}

//-------- allWallsIntact - returns true if the cell at [aRow][aCol]

has all walls around it intact

private boolean allWallsIntact(int aRow, int aCol)

{

return (mazeArray[aRow-1][aCol] == 1 && //wall

above it exists

mazeArray[aRow+1][aCol] == 1 && //wall below it exists

mazeArray[aRow][aCol-1] == 1 && //wall to the left exists

mazeArray[aRow][aCol+1] == 1); //wall to the right

exists

}

//-------- inMaze - returns true if the cell at [aRow][aCol] is in

the maze

private boolean inMaze(int aRow, int aCol)

{

return (aRow > 0 && aRow < mazeArray.length-1 &&

aCol > 0 &&

aCol < mazeArray[0].length-1);

}

//-------- getCurrentRow - returns the current (real) row

public int getCurrentRow()

{

return currentArrayRow/2;

}

//-------- getCurrentCol - returns the current (real) col

public int getCurrentCol()

{

return currentArrayCol/2;

}

//-------- isOpen - returns true if there is no wall in the

direction that is passed in

public boolean isOpen(Direction direction)

{

boolean result = false;

if (direction == Direction.UP &&

mazeArray[currentArrayRow-1][currentArrayCol]==0)

result = true;

else if (direction == Direction.DOWN &&

mazeArray[currentArrayRow+1][currentArrayCol]==0)

result = true;

else if (direction == Direction.LEFT &&

mazeArray[currentArrayRow][currentArrayCol-1]==0)

result = true;

else if (direction == Direction.RIGHT &&

mazeArray[currentArrayRow][currentArrayCol+1]==0)

result = true;

return result;

}

//-------- isOpenTo - returns true if the current cell is openTo (no

wall) the one passed in

private boolean isOpenTo(int aRow, int aCol)

{

boolean result;

if (!isAdjacentTo(aRow, aCol))

result = false;

else if (currentArrayRow-aRow == 2) //IS adjacent,

figure which direction and call other method

result = mazeArray[currentArrayRow-

1][currentArrayCol]==0; //UP

else if (currentArrayRow-aRow == -2)

result =

mazeArray[currentArrayRow+1][currentArrayCol]==0; //DOWN

else if (currentArrayCol-aCol == 2)

result =

mazeArray[currentArrayRow][currentArrayCol-1]==0; //LEFT

else if (currentArrayCol-aCol == -2)

result =

mazeArray[currentArrayRow][currentArrayCol+1]==0; //RIGHT

else

result = false;

return result;

}

//-------- adjacentTo - returns true if the current cell is

adjacentTo (above/below/left/right) current cell

public boolean isAdjacentTo(int aRow, int aCol)

{

//calculate how far the move is (hopefully row OR col is

just +-2)

int arrayRowChange = currentArrayRow - aRow;

int arrayColChange = currentArrayCol - aCol;

//it is adjacent if EITHER the rows or the cols differ by

2

return Math.abs(arrayRowChange)==2 ^

Math.abs(arrayColChange)==2; //checking row xor col

}

// -------- move - receives a Direction and moves there if OK.

Calls the other

// arrayMove to do this

public boolean move(Direction direction)

{

boolean success = false;

if (direction == Direction.UP)

success = arrayMove(currentArrayRow-2,

currentArrayCol);

else if (direction == Direction.DOWN)

success = arrayMove(currentArrayRow+2,

currentArrayCol);

else if (direction == Direction.LEFT)

success = arrayMove(currentArrayRow,

currentArrayCol-2);

else if (direction == Direction.RIGHT)

success = arrayMove(currentArrayRow,

currentArrayCol+2);

return success;

}

//-------- move - receives the literal (not array) row/col to move

to. Calls the

// other ArrayMove to do this.

private boolean move(int realRow, int realCol)

{

return arrayMove(2*realRow+1, 2*realCol+1);

}

//-------- arrayMove - moves using the maze array (moves a distance

of 2 to get to next cell)

// first checks to see if move is legal.

Returns true if successful.

private boolean arrayMove(int newArrayRow, int newArrayCol)

{

boolean success;

//go to sleep to slow down animation (based on its speed)

try{ Thread.sleep(solveAnimationDelay); }

catch(Exception ex) {}

//make sure the new row/col is still in the maze

if (!inMaze(newArrayRow, newArrayCol))

throw new IllegalMazeMoveException("trying to

move to cell <" + newArrayRow/2 + ", " +

newArrayCol/2 + "> which is

outside the maze");

//make sure the new row/col is adjacent

else if (!isAdjacentTo(newArrayRow, newArrayCol))

throw new IllegalMazeMoveException("trying to

move from cell <" + currentArrayRow/2 + ", " + currentArrayCol/2 +

"> to non-adjacent cell <" +

newArrayRow/2 + ", " + newArrayCol/2 + ">");

//make sure there is not a wall in between

else if (!isOpenTo(newArrayRow, newArrayCol))

throw new IllegalMazeMoveException("trying to

move from cell <" + currentArrayRow/2 + ", " + currentArrayCol/2 +

"> to cell <" +

newArrayRow/2 + ", " + newArrayCol/2 + "> and there is a wall in

between");

//if OK, move the current cell

else

{

//if new ArrayRow is already in the path,

then we are retreating from current location so

//clear current location

if (mazeArray[newArrayRow][newArrayCol] == 2)

mazeArray[currentArrayRow][currentArrayCol] = 0;

currentArrayRow = newArrayRow;

currentArrayCol = newArrayCol;

//move current cell

mazeArray[currentArrayRow][currentArrayCol] =

2; //and show it as part of path

success = true;

}

//return

return success;

}

//-------- goalReached - returns true if the maze is solved (current

location == goal)

public boolean goalReached()

{

return (currentArrayRow == goalArrayRow &&

currentArrayCol == goalArrayCol);

}

//-------- getMazeArray - returns the mazeArray

public int[][] getMazeArray()

{

return mazeArray;

}

//******************************************************************

*****

//This is Maze's enumerated data type: moves can be UP, DOWN, LEFT,

RIGHT

public enum Direction implements java.io.Serializable

{

UP, DOWN, LEFT, RIGHT

}

//******************************************************************

*****

//MazeMoveException will be thrown when an illegal move is requested

in the maze

public class IllegalMazeMoveException extends

IllegalArgumentException implements java.io.Serializable

{

//no data is needed - all inherited...

//constructor - just do what the parent class would do if

it received the String

public IllegalMazeMoveException(String str)

{

super(str);

}

//no methods are needed - all inherited...

}

}