In this program you are given 2 classes to work with:

1)Maze which is a Maze

2)MazeDisplay which graphically displays the maze it is given.

You will also use:

1) the 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 should have a method called .solve(), which contains a loop which will run until the Maze is solved or until the user says to quit. Inside the loop, the user 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. It should prompt the user to enter the number of rows and the number of columns, then create an instance of a MazeSolver, passing in the number of 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 ResumeSolvingMaze.java, which will contain a main method that will read in a serialized MazeSolver (instead of creating a new one). So it should ask the user to enter the name of the file that contains the serialized class, then read it in and convert 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 an enum called Direction, which is either UP, DOWN, LEFT, or RIGHT. Since Direction is defined inside Maze, 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; //whichWay is a Maze.Direction o whichWay = Maze.Direction.UP; //so it can this value, for example o Stack myStack; //Generics

The 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 tell the maze to move there:

.getCurrentRow() //returns the current row

.getCurrentCol() //returns the current column

.goalReached() //returns true or false, depending on whether the goal is reached

.move(Maze.Direction.UP) //for examplethis would tell the current location to move UP

.isOpen(Maze.Direction.RIGHT) //for examplethis would return a boolean telling whether 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 stores a Maze and also stores 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. NOTE: you will also create an instance of a MazeDisplay, but do not declare it in the class data. It uses the Thread class, which is not Serializable. 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. The 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.

Tell 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 choose 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, you cannot change or add code to the Mazes methods, but only use Mazes existing public methods that are also described above.

The basic algorithm is 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 they 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 users 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 user does not type Q or q, then make a move, 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 mark the cell you arrived at as visited. Tell the maze instance to move in the direction of Maze.Direction.UP.

Else if 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 mark 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 come 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 quits, print Program ended without solving.

If the loop ends with the Maze being solved, print Maze is solved.

public class MazeDisplay extends javax.swing.JFrame implements Runnable, java.io.Serializable

{

//------------ constants

private final int START_WIDTH = 700;

private final int START_HEIGHT = 500;

private final int ANIMATIONDELAY = 0; //Animation display rate (in milliseconds), so 20fps

//------------ data

private int cellDim;

private int[ ][ ] mazeArray;

private int numArrayRows;

private int numArrayCols;

private java.awt.Graphics g;

private Thread animationThread;

private java.awt.Insets insets;

//----------- constructor(s)

// Parameterized constructor which receives an int that is the landscapeID

public MazeDisplay(Maze aMaze)

{

//if aMaze is null, throw an exception

if (aMaze == null)

throw new IllegalArgumentException("trying to create a MazeDisplay with a null Maze");

//store the reference to aMaze's mazeArray to be used in the display

mazeArray = aMaze.getMazeArray();

//isolate the number of rows and the number of columns in the mazeArray

numArrayRows = mazeArray.length;

numArrayCols = mazeArray[0].length;

//get the number of "real" rows and cols tht the Maze has

int numRealRows = numArrayRows/2;

int numRealCols= numArrayCols/2;

//calculate the optimum size of one cell

int calcWidth = START_WIDTH/numRealCols;

int calcHeight = START_HEIGHT/numRealRows;

cellDim = Math.min(calcWidth, calcHeight);

//but if the cellDim is < 2 pixels, then it is too small to draw

if (cellDim < 2)

throw new IllegalArgumentException("maze has too many rows/cols to draw");

//set the JFrame attributes

setTitle("CSC205AB Maze");

setDefaultCloseOperation( javax.swing.JFrame.EXIT_ON_CLOSE);

setSize(numRealCols*cellDim+7,numRealRows*cellDim+1+28); //add one for last border, subtract 38 for title bar, borders

center();

setResizable(false);

setAlwaysOnTop(true);

setVisible(true);

// use those values to determine the greeny and the orangey

insets = getInsets();

// add a WindowListener

addWindowListener(new java.awt.event.WindowAdapter()

{public void windowClosing(java.awt.event.WindowEvent e)

{ System.exit(0);}});

// get the Graphics object that will be used to write to this JFrame;

g = getGraphics();

// Anonymous inner class window listener to terminate the program.

this.addWindowListener(new java.awt.event.WindowAdapter()

{

public void windowClosing(java.awt.event.WindowEvent e)

{

System.exit(0);

}

}

);

// Create and start animation thread

animationThread = new Thread(this);

animationThread.start();

}

//----------- methods(s)

// run will actually run this Frame

public void run()

{

//Loop, sleep, and update sprite positions once each ANIMATIONDELAY milliseconds

long time = System.currentTimeMillis();

while (true) //infinite loop

{

paint(g);

try

{

time += ANIMATIONDELAY;

Thread.sleep(Math.max(0,time - System.currentTimeMillis()));

}

catch (InterruptedException e)

{

System.out.println(e);

}//end catch

}//end while loop

}//end run method

// center - will set the x and y of this Frame to the center of the screen

private void center()

{

java.awt.Dimension ScreenSize = java.awt.Toolkit.getDefaultToolkit().getScreenSize();

java.awt.Dimension FrameSize = this.getSize();

int x = (ScreenSize.width - FrameSize.width)/2;

int y = (ScreenSize.height - FrameSize.height)/2;

this.setLocation(x, y);

}

//------------------------------------------------

public void windowGainedFocus(java.awt.event.WindowEvent e)

{

repaint();

}

//------------------------------------------------

public void windowLostFocus(java.awt.event.WindowEvent e)

{

repaint();

}

//------------------------------------------------

public void componentResized(java.awt.event.ComponentEvent e)

{

repaint();

}

//------------------------------------------------

public void componentMoved(java.awt.event.ComponentEvent e)

{

repaint();

}

//------------------------------------------------

public void componentShown(java.awt.event.ComponentEvent e)

{

repaint();

}

//------------------------------------------------

public void componentHidden(java.awt.event.ComponentEvent e)

{

//repaint();

}

//------------------------------------------------

public void update(java.awt.Graphics g)

{

repaint();

}

//------------------------------------------------

public void actionPerformed(java.awt.event.ActionEvent e)

{

}

// paint - repaints the whole Maze. Uses "double-buffering" to eliminate flickering.

public void paint(java.awt.Graphics g)

{

// create an image - we will "double buffer" (draw to that image first and then

// draw the image) to eliminate flickering

java.awt.Image image = createImage(getWidth(), getHeight());

java.awt.Graphics graphicsBuffer = image.getGraphics();

// fill the image with the background color

//graphicsBuffer.setColor(Color.WHITE);

//graphicsBuffer.fillRect(12, 12, getWidth()-24, getHeight()-24);

graphicsBuffer.setColor(java.awt.Color.BLACK);

for (int row=0; row

for (int col=0; col

{

if (row%2==1 && col%2==1 && mazeArray[row][col] == 3) //odd rows, odd cols are the actual cells

{

graphicsBuffer.setColor(java.awt.Color.MAGENTA); //goal

int startx = insets.left + col/2 * cellDim;

int starty = insets.top + row/2 * cellDim;

graphicsBuffer.fillRect(startx, starty, cellDim, cellDim);

}

if (row%2==1 && col%2==1 && mazeArray[row][col] == 2) //odd rows, odd cols are the actual cells

{

graphicsBuffer.setColor(java.awt.Color.YELLOW); //current

int startx = insets.left + col/2 * cellDim;

int starty = insets.top + row/2 * cellDim;

graphicsBuffer.fillRect(startx, starty, cellDim, cellDim);

}

else if (row%2==1 && col%2==1 && mazeArray[row][col] == 0) //odd rows, odd cols are the actual cells

{

graphicsBuffer.setColor(java.awt.Color.WHITE); //current

int startx = insets.left + col/2 * cellDim;

int starty = insets.top + row/2 * cellDim;

graphicsBuffer.fillRect(startx, starty, cellDim, cellDim);

}

}

graphicsBuffer.setColor(java.awt.Color.BLACK);

for (int row=0; row

for (int col=0; col

{

if (row%2==0 && col%2==1 && mazeArray[row][col] == 1) //even rows, odd cols are the horizontal walls

{

int startx = insets.left + col/2 * cellDim;

int endx = insets.left + col/2 * cellDim + cellDim;

int starty = insets.top + row/2 * cellDim;

int endy = insets.top + row/2 * cellDim;

graphicsBuffer.drawLine(startx, starty, endx, endy);

}

else if (row%2==1 && col%2==0 && mazeArray[row][col] == 1) //odd rows, even cols are the vertical walls

{

int startx = insets.left + col/2 * cellDim;

int endx = insets.left + col/2 * cellDim;

int starty = insets.top + row/2 * cellDim;

int endy = insets.top + row/2 * cellDim + cellDim;

graphicsBuffer.drawLine(startx, starty, endx, endy);

}

}

// copy the image to the actual Frame

g.drawImage(image, 0, 0, java.awt.Color.WHITE, null);

repaint();

}

}