Program 5: Recursive Maze Solver

Due Date and Submission Requirements

Due Date: Sunday, December 8th at 11:59 p.m.
Partner Information: You are allowed to work with one partner. Be sure to indicate in your submission who your partner is. Each Java class should have the name of each student in a comment at the top of the program
Submission Instructions: Upload your .java files to the Program 5 Dropbox.

The goal of this lab is:

Write a complex Java Program
Gain experience using recursive algorithms

Background

In this assignment, you will be writing a program that will solve a text-based maze using recursion. This can be a tricky assignment, so make sure you give yourself enough time.

The following grid of hashes (#) and dots (.) is a 2D array representation of a Maze. F is the finish, or exit of the maze. Your goal is to solve this maze, by going from the starting point to the finish point, while keeping track of the path taken.

# # # # # # # # # # # # # . . . # . . . . . . # . . # . # . # # # # . # # # # . # . . . . # . # # . . . . # # # . # . # # # # # . # F # . # . # # . . # . # . # . # . # # # . # . # . # . # . # # . . . . . . . . # . # # # # # # # . # # # . # # . . . . . . # . . . # # # # # # # # # # # # #

You will be using 2D array to represent the maze. The hashes represent the walls of the maze, and the dots represent the possible paths through the mze. Moves can only be made to a location in the array the contains a dot.

The algorithm

There is a simple algorithm for walking through a maze that GUARANTEES finding the exit (assuming there is an exit). If there is not an exit, you will arrive at the starting location again. This algorithm does not provide the optimal path (ie the shortest path). There is also some edge cases where this algorithm will not work, but you don't have to worry about those cases.

Place your right hand on the wall to your right and begin walking forward. Never remove your hand from the wall. If the maze turns to the right (ie your right hand is on a . character), you follow the wall to the right. If you cannot go right, you should attempt to go forward one spot. If you cannot move forward, then turn left. As long as you do not remove your hand from the wall, eventually you will arrive at the exit of the maze.

Assumptions

Your maze you will be solving will always be 12x12, and will have a valid exit somewhere.
The maze will always have a border of hashes (#) (other than the starting spot), so you dont have to worry about going out of bounds.
The input maze will always follow the similar format (hashes, dots, F, etc).

Directions

You are welcome to develop your solution from scratch, otherwise you will use Program5Demo.java and MazeSolver.java as a starting point, and you will write the body for the following methods.

Part 1: Reading in the maze via an input file into a 2D character array (`loadMaze(String filename)`)

You must read in the maze via a text file (maze.txt) into a 2D character array. The loadMaze() method takes in a String (the name of the file), and loads the file into a 2D character array (for example char[][] maze). After the array has been filled, the array needs to be returned.

Part 2: Printing out the maze (`printMaze(char[][] maze)`)

Now that the maze is filled, you will need to write a method that will print out the maze, because after you make a move in the maze, you will print out the current status of the maze. The printMaze() method takes in the maze array, and prints it out.

Part 3: Understanding the `solveMaze()` method

The solveMaze() method is called from the demo class, and starts the first recursive call. In this method, the starting location is hard coded into the start_x, start_y, start_hand_x, start_hand_y variables. If you use a different maze as input, you will need to change these values to reflect the starting location of your maze.

Then, this method calls the first iteration of the make_move() method with the starting location, which will kick off a long chain of recursive calls.

This method is finished for you. You shouldn't need to change anything in this method with the default input (maze.txt), but you can change stuff here if you'd like.

Part 3.5: Understanding the Maze

The maze is represented by a 2D character array called maze. Specific spots in the array can be accessed using maze[y_value][x_value].

[0,0] is going to be the top left corner of the maze.This means that the Y values grow going down, and the X values grow going to the right. Consider this portion of the maze that shows the coordinates of the maze.

To access the green square, for example, it could be accessed by maze[4][3]. To move north one spot, that would be maze[current_y-1][current_x].

Part 4: Making a move in the maze (`makeMove(x, y, hand_x, hand_y)`

This is the trickiest part, and will be the bulk of your code. You need to write the body of the makeMove() method. This method takes in only four parameters: the characters current x and y coordinates, and the x and y coordinates of their right hand. You are not allowed to change the arguments to this method. This MUST be a recursive method, and makes a single move in the maze. There are two important parts

Part 4.1: Determining your direction

The first part is to determine which direction the character is facing. This can be determined by the characters current x,y location, and the x,y location of their right hand. Consider the following scenario:

We need to determine which direction the character is facing, because that will dictate how we move forward, turn right, or turn left.
We can determine the character must be facing north, because the Y value of the character (y) and the Y value of their right hand (hand_y) are the same, and the x value of the right hand (hand_x) is greater than the character's x value (x)).
You will need an if statement(s) to determine if the character is facing north, east, south, or west, which you can determine by comparing the values of the four input parameters.

Part 4.2 Making a move

You only have three options for movement:

Turn right 90 degrees and move forward one spot (this helps prevent an infinite loop)
Move forward one spot
Turn left 90 degrees

You can only see one step to the left, right, and one step in front of you for each turn (no looking ahead multiple spot, no looking behind, no teleporting), Every time you make a move, you will need to place an 'X' on the current spot to represent the path being taken.

Using the image above, if the player is moving forward one spot (facing north), that can be done by recursivly calling the method, and providing the new x,y coordinates of the character and their right hand:
make_move(x, y-1, hand_x, hand_y -1)

Consider the following logic:

1. If the finish/exit ('F') is in front of me, move the exit and return
2. IF my hand is on a dot, I will turn 90 degrees and move to that dot. I will then recursively call my method with new x, y, hand_x, hand_y
3. ELSE IF my hand is not on a dot, I will look forward in front of me, IF it is a . in front of me, I will move forward and then recursively call this method with new x, y, hand_x, hand_y
4. ELSE IF it's a # in front of me, I can't move forward, so I'll turn 90 degrees to the left and recursively call my method with the same x and y values, but new hand_x and hand_y values

Your code is going to have a lot of if statments. Your code might look a bit ugly, and that is fine!

The character might need to backtrack, so they will need to pick up on '.'' as well as the 'X' characters. Your if statements will need to handle that (example:if(maze[y+1][x] == '.' || maze[y+1][x] == 'X' )

Starting Code, and input maze

Your code should work on any maze of a similar format. First, just get your algorithm working on the given maze (maze.txt), and then try other mazes.

Sample Output

When your run your program, it should look very similar to the following output:
Program 5 output
It should print out the maze after each step, and place an X at each spot the character travels too. When the exit is reached there should be a print statement to indicate the maze has been solved.

Hints

Take baby steps, and test your program every time you add a new move option. First, if facing east, try to get the character to move forward one spot, test your program, then try to get turning left facing east working, test your program, then try to get moving north forward one spot, test your program, and so on.
Do not wait until the last few hours to do this assignment otherwise you will be miserable.

Additional Mazes for testing

maze2.txt
maze3.txt
maze4.txt (your algorithm should not work on this example (why is that?)... which is totally fine-- you wont lose points)

You are welcome to create your own mazes and try them!

Maze solving is a classic problem in computer science. You may see similar problems like this in your upper-division computer science classes, so it is helpful to hang onto this code. In CSCI 232, we will discuss more ways to solve mazes similar to this.

Grading (100 points)

Criteria	Points
Maze is read in from a file and loaded into a 2D array	15
There exists a method that prints out the array	10
Your recursive method works and is able to move north properly	15
Your recursive method works and is able to move east properly	15
Your recursive method works and is able to move south properly	15
Your recursive method works and is able to move west properly	15
Your algorithm does not result in stack overflows, array index out of bounds error, method arguments are not changed, etc	15

program 5 solution