Recursion Maze Solver

This lab will use 2D arrays, recursive algorithms, and logical thinking. The following grid of hashes(#) and dots(.) is a 2D array representation of a maze

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

The hashes represent the walls of the maze and the dots represent squares in the possible paths through the maze. Moves can only be made to a location in the array that contains a dot.

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. 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, you follow the wall to the right. As long as you do not remove your hand from the wall, eventually you will arrive at the exit of the maze. If you follow the algorithm.

Write a program to walk through the maze. You must write a recursive function. The function should recieve as arguments 12-by-12 character array representing the maze and the starting point (x, y location in the maze). You should read the maze in from a text file. Use args[0] to read the file name, command line argument. This way I can give you new mazes to test your algorithm. As the function attempts to escape from the maze it should place an X for the current path taken. The program should display the maze at each step so you can watch as the maze is solved. Put an X where you have traveled and maybe an O where you currently are located. The end of the maze will be a capital 'F' (stands for finished).

This algorithm doesn't work for all mazes. Can you come up with a maze where this doesn't work?

Rules you must follow:

• Recursive Algorithm, must use recursive method.
• Method gets four parameters (maze, xLoc, YLoc, handLocationX, handLocationY) no instance fields needed.
• Your method can only see one step, you can only see what's in front of you and what your hand is on......no teleporting, no looking beyond one step at a time.
• Read in the text file as a 2D array.....use command line arguments to get the text file read in. You can start with just hardcoding the maze above in as a 2D array, then add a method to read in the data from a text file. Hardcode in the start coordinates and the hand locations.
• Hints
• Make a move, print out the maze and see where you are, make another move, print the maze. Don't try to solve the whole maze at once, get the different moves working first.
• Think of it like this......"I am at x, y, my hand is at Hx, Hy which tells me the direction I'm facing based on Hx being less than or great than x, and Hy being less than or greater than y. Based on on that logic I can check what is in front of me. IF it is a . in front of me I'll move forward and then recursively call this method with my new x, y, if it's a # I can't go forward so I'll check to see what's under my hand......IF my hand is on a dot I'll turn to the right and call my method again with a new updated values for Hx, Hy but same x, y because I just turned, didn't move, if my hand is on a # then..........so on and so on.
• Lots of if statements to figure out which way you are facing, where you need to check to see if you can move forward, of if you need to turn.
• The maze above has spaces between the letters, that's so it lines up nicely. When you read it in you'll need to trim white space (ignore blanks) to create your 2D array. Also the starting point is always on the outside of the maze, you can search the outside of the input to find a . then you know your starting point. Do that last, wait until you have everything else working first......hard code in the starting point until you get the traversal working.
• If you hit a dead end you must turn, then turn (2 recursive calls according to the rules) and then head back along the path you already travelled......but now instead of .'s you will see x's if you are showing the route you travelled with x's. Your if statements should handle that......example: if(maze[y+1][x] == '.' || maze[y+1][x] == 'x')