Add code to Maze.java

Help Needed asap

Consider a maze made up of rectangular array of squares, such as the following one:

X X X X X X X X X X X X X

X X X X X X

X X X X X

X X X X X X X X

X X X X X

X X X X X X X

X X X X X X X X X X X X X

Figure 1--- A sample maze

The X blocks represent a blocked square and form the walls of the maze. Lets consider mazes that have only one entrance and one exit, as in our example. Beginning at the entrance at the top left side of the maze, find a path to the exit at the bottom right side. You can move only up, down, left, or right. Square is either clear or blocked.

Let a two dimensional array represent the maze. Use a stack data structure to find a path through the maze. Some mazes might have more than one successful path, while others might have no path.

Hints:

The primary consideration is that if you reach a dead end, you need to be able to backtrack along the path to the point where you can try a different path. The stack data structure makes it possible to store the current path and backtrack if necessary. Every clear position visited in the current path is pushed to the stack and if a dead end is reached, the previous position is popped from the stack to backtrack. You need to have a loop that begins with the start position and pushes it into the stack then moves to a neighboring cell until either the goal position is reached or the stack becomes empty. Make sure to mark each clear array cell you move to as visited to avoid checking it again and getting stuck in an infinite loop. For example, each array cell can have three different values: X for blocked, V for visited, and for clear. A dead end is an array cell whose all neighbors are either blocked or already visited.

What you need to do:

I have attached three files with this assignment spec:

Position.java: a class to store the position of an array cell. It has two attributes: row and column along with their accessor and mutator methods. It also has an equals method that checks for equality of two Position objects. Maze.java: a class to store and traverse a maze. It has one attribute: a two dimensional character array which represents the maze. It also has a method traverse which finds a solution to the maze. MazeTester: a sample driver class which calls the traverse method on the maze shown in figure 1.

You only need to implement the traverse method in the Maze.java class. This method receives the start and goal positions as parameters and returns an array of Position which stores a solution to the maze if such solution exists; otherwise, it returns null.

Note: There might be more than one possible solution to a maze, depending on the ordering in which the neighboring cells are visited at each location. Please follow the following order in visiting the neighbor positions:

First move left, if the left neighbor is not clear, then move right, if the right neighbor is not clear, then move up, if it is not clear, then move down.

To get a full credit, it is very important that you comply with this ordering rules, so that your method produces a solution that matches the correct solution in my test harness

You also need to validate the parameters passed to the traverse method. For example, the start and end positions should be valid array positions and contain blank.

You may create any additional helper methods to aid you. For instance, you may make a method to convert the stack to a necessary array. Just remember, when you grab the information off of a stack you are getting in the reverse order you push them in.

Also, modify the maze in the MazeTester class to test your algorithm.

MAZE.JAVA /**** * A class to store and traverse a maze * @author esahe2 * */ import java.util.*; public class Maze { /** * Two dimensional array to represent a maze */ private char[][] maze; /** * Constructor initializing the maze array * @param maze */ public Maze(char[][] maze) { this.maze= maze; } /** * You need to implement this method * @param start: The start Position in the maze * @param goal: The goal Position in the maze * @return An array of Position which stores a solution to the maze. If a solution is not found a null value should be returned. */ public Position[] traverse(Position start, Position goal) { //Your implementation goes here. } }

MAZETESTER.JAVA

/** * A simple driver class to test the maze traversal * @author Ellie * Below is what should be printed by your traverse method: row:1 column:0 row:1 column:1 row:1 column:2 row:2 column:2 row:2 column:3 row:2 column:4 row:1 column:4 row:1 column:5 row:1 column:6 row:2 column:6 row:2 column:7 row:2 column:8 row:2 column:9 row:3 column:9 row:4 column:9 row:4 column:10 row:4 column:11 row:5 column:11 row:5 column:12 The goal is reached * */ public class MazeTester { public static void main(String[] args) { char[][] sample_maze ={ {'x','x','x','x','x','x','x','x','x','x','x','x','x'}, {' ',' ',' ','x',' ',' ',' ','x','x','x','x',' ','x'}, {'x','x',' ',' ',' ','x',' ',' ',' ',' ','x',' ','x'}, {'x','x',' ','x','x',' ','x',' ','x',' ','x',' ','x'}, {'x','x',' ',' ','x',' ',' ',' ','x',' ',' ',' ','x'}, {'x','x','x','x','x','x','x',' ','x',' ',' ',' ',' '}, {'x','x','x','x','x','x','x','x','x','x','x','x','x'} }; Maze m = new Maze(sample_maze); Position[] sol= m.traverse(new Position(1,0), new Position(5,12)); if (sol!= null) { for (int i=0; i 
POSITION.JAVA
 
/** * A class to store a position in a maze * @author esahe2 * */ public class Position{ /*************************** * Attributes ****************************/ private int row; private int column; /*************************** * Constructor * @param row * @param column ***************************/ public Position(int row, int column) { this.row = row; this.column= column; } /************************** * Checks two positions for equality. Two positions are equal if the have the same row and column numbers. *************************/ public boolean equals(Object obj) { Position otherPosition= (Position)obj; return (otherPosition.row==row && otherPosition.column==column); } public String toString() { return "row:"+ row + " column:"+ column; } /************************** * Getter and Setter methods * @return */ public int getRow() { return row; } public void setRow(int row) { this.row = row; } public int getColumn() { return column; } public void setColumn(int column) { this.column = column; } }