USING JAVA:

- Follow each part using Java

Part 1: Maze Object

Reference the following UML diagram to build an object that will represent the maze on the computer.

Discussion on Maze

A maze is defined by a 2 dimensional int array. Walls in the maze are denoted by the number 1. Places that can be traversed are denoted by the number 0. The entrance and exit are denoted by number -1. The entrance is on the left(column 0), the exit is on the right(rowlength -1).

Example of a maze:

Notice the Maze itself is surrounded by walls except for the entrance and exit.

Constructors

The maze will have one constructor that accepts an int[][] that assigns to the map. We also need to find the starting row for the entrance. To do this we will call upon the findEntranceRow() and assign it to the entranceRow field.

Getters/Setters

getCell/setCell will get or set the information within the int[][] array. The set will be used a lot as we set the cell to a different value as we search.

getEntranceRow() reports back its value.

getExitColumn() reports back the last column on the right. Use row [0] and report its length. We are going to assume our 2D array is rectangular and we can't hardcode the length/size of the array, but rather use the lengths for any size maze.

Other Methods:

isOpenSpace(int r, int c) will be our helper method to make sure we are not out of range of the array AND that we aren't at a wall. This is a boolean method. If false is returned we know we can't go to the space. This will be used in our recursive method to help solve the maze.

- So that means you need to check if the values r & c sent are within the range of the 2D array and if it contains the value '0'. Return true

- otherwise return false.

findEntranceRow() will search through the first column of the maze and report back the row that the entrance is at. Note: this is a private method and only used inside the class, the getter will be used to report it back

printMaze()

When printing the maze you should use '*' (asterisks) as the walls, the cells visited/final result should be marked with '@' the exit should be a [ ]. Note that you should use if or switch to match the -1, 0 and 1 values saved in the array. Think about adding extra spaces around characters as you print. This will also be in a nested loop structure.

Part 2: Solving the Maze

Reference the following UML diagram to build the MazeSolver.java file.

Discussion of MazeSolver

The MazeSolver will hold a single Maze object. This will have our recursive method to solve the maze

Constructor

Takes on a simple Maze object and assigns it to the field

Maze Solver

solveMaze(int r, int c) is the most important method here that uses Recursion to find the end of the maze. The method accepts two ints representing the current location in the maze. For the first call upon the method the entrance of the maze will be passed as the current location. This method attempts to locate the exit marking an '@' in each square that has been reached. So as you traverse through blank spaces you need to mark/change the cell. Note: the '@' comes from the print maze, since our maze is in int[][] format pick another number to fill in the cell that you can later represent as an '@'

Here is the basic algorithm you can follow:

Part 3: MazeDriver

Create a class MazeDriver.java that contains the main() method. This will have a MazeSolver object to which you send it an int array to create a maze. Give the user 3 options of mazes to solve.

Use the following as the mazes OR create your own:

Then you will call the MazeSolver's solveMaze() method that is boolean and use to print out if the maze is solved or unsolvable. Use a condition that if it is solvable, you print out the maze showing the path.

111111111111100010000001101010111101111010000101100001110101111101010101100101010101110101010101100000000101111111011101100000010001111111111111 \begin{tabular}{|l|} \hline \multicolumn{1}{|c|}{ MazeSolver.java } \\ \hline -Maze maze \\ \hline MazeSolver(Maze m ) \\ + solveMaze(int r, int c) : boolean \\ \hline \end{tabular} solveMaze(int r, int c) First use the is0penSpace method on the maze, then nested inside if the current cell is the exit, then return true 1 BUT so is the entrance.. which means you need to make sure you are on the exit column otherwise: mark the space with another number that will represent the path taken (for example number 2) if not the end of the path then recursive call all below: Check the location above us if is a valid spot and not visited yet solveMaze(cur X, curY - 1 ) return true Check the location left of us if is a valid spot and not visited yet solveMaze(curX-1, curY return true Check the location right of us if is a valid spot and not visited yet solveMaze(curX+1, curY) return true Check the location down from us if is a valid spot and not visited yet solveMaze(curX, curY+1) return true ***Welcome to the Maze Project*** Select a maze to solve: 1. Maze 1 2. Maze 2 3. Maze 3 Choice: Example Output *** Welcome to the Maze Project *** Select a maze to solve: 1. Maze 1 2. Maze 2 3. Maze 3 Choice: 1 *** Starting Maze *** Maze Solved: *** Welcome to the Maze Project *** Select a maze to solve: 1. Maze 1 2. Maze 2 3. Maze 3 Choice: 3 *** Starting Maze *** Maze Solved: ************************ @@@@**@@**@@********@@** ******@@**@@@@@@@@**@@** ** @@@@******@@**@@[] ********@@** **@@** ** ** **@@** **@@** ** **** **@@** **@@** ** ** @@@@@@@@@@** ** ** *** Welcome to the Maze Project *** Select a maze to solve: 1. Maze 1 2. Maze 2 3. Maze 3 Choice: 3 *** Starting Maze *** ****************** ** [][]