Maze program using recursive function UPDATED!
-
UPDATED!!!! Now with Exact excercise instructions: In the preceding double-subscripted array, the #s 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. There may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm. Write a recursive function mazeTraverse to walk through the maze. The function should receive as arguments a 12-by-12 character array representing the maze, and the starting location of the maze. As mazeTraverse attempts to locate the exit from the maze, it should place the character x in each square in the path. The function should display the maze after each move so the user can watch as the maze is solved. Important data: 'S' represents the starting point of the maze 'E' represents the ending (exit) point of the maze '#' represents walls '.' dots represents the path where you can walk My file looks somthing like this: (please copy these characters and past them in to a word processor (e.g. notepad) to see it correctly. ############ #...#......# S.#.#.####.# ###.#....#.# #....###.#.E ####.#.#.#.# #..#.#.#.#.# ##.#.#.#.#.# #........#.# ######.###.# #......#...# ############ This is a 12 x 12 2-D array. So far, I can read/print the maze w/o problems, but the recursive function is a mess. Here's my code. Please help!! I don't know how to work w/ this recursive func. // My code: Find the way out of the maze using recursion //************************************************************************************************* **************** THIS IS THE PART THAT DOESN'T WORK ******************************** //Thanks to those that have offered me their comments. I understand now this code doesn't work at all. So please focus on the instructions and not this code. I'm leaving the code just so you can understand previous comments. Thank
-
UPDATED!!!! Now with Exact excercise instructions: In the preceding double-subscripted array, the #s 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. There may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm. Write a recursive function mazeTraverse to walk through the maze. The function should receive as arguments a 12-by-12 character array representing the maze, and the starting location of the maze. As mazeTraverse attempts to locate the exit from the maze, it should place the character x in each square in the path. The function should display the maze after each move so the user can watch as the maze is solved. Important data: 'S' represents the starting point of the maze 'E' represents the ending (exit) point of the maze '#' represents walls '.' dots represents the path where you can walk My file looks somthing like this: (please copy these characters and past them in to a word processor (e.g. notepad) to see it correctly. ############ #...#......# S.#.#.####.# ###.#....#.# #....###.#.E ####.#.#.#.# #..#.#.#.#.# ##.#.#.#.#.# #........#.# ######.###.# #......#...# ############ This is a 12 x 12 2-D array. So far, I can read/print the maze w/o problems, but the recursive function is a mess. Here's my code. Please help!! I don't know how to work w/ this recursive func. // My code: Find the way out of the maze using recursion //************************************************************************************************* **************** THIS IS THE PART THAT DOESN'T WORK ******************************** //Thanks to those that have offered me their comments. I understand now this code doesn't work at all. So please focus on the instructions and not this code. I'm leaving the code just so you can understand previous comments. Thank
Hello, One problem I see right away is that when you pass maze to your recursive funcion, you are passing it as a pointer to the array, not a copy of the array. When you set a point in the maze matrix to 'x', you are setting it globally, so that the maze matrix is permantly altered. This means, that the more times you are calling your recursion function, you are setting more and more of your maze to all 'x', and removing the path of '.'. When dealing with arrays in C/C++, you will always pass them as pointers to the underlying data, as opposed to passing a copy. If you want to stick with the method you are using above, you would have to make a new copy of the maze matrix before calling solve_maze each time. Check out the docs for memcpy()! maze[12][12]; newMaze[12][12]; memcpy(newMaze, maze, sizeof(newMaze)); // Do your switch to make the move, and apply the changes to the newMaze copy solve_maze(newMaze, ...); Note: Solving a huge maze with this method will eat a lot of memory, as you will make a new copy on each recusion level, leading to lots of copys when you get down deep in your tree. Good luck! Nick.
-
UPDATED!!!! Now with Exact excercise instructions: In the preceding double-subscripted array, the #s 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. There may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm. Write a recursive function mazeTraverse to walk through the maze. The function should receive as arguments a 12-by-12 character array representing the maze, and the starting location of the maze. As mazeTraverse attempts to locate the exit from the maze, it should place the character x in each square in the path. The function should display the maze after each move so the user can watch as the maze is solved. Important data: 'S' represents the starting point of the maze 'E' represents the ending (exit) point of the maze '#' represents walls '.' dots represents the path where you can walk My file looks somthing like this: (please copy these characters and past them in to a word processor (e.g. notepad) to see it correctly. ############ #...#......# S.#.#.####.# ###.#....#.# #....###.#.E ####.#.#.#.# #..#.#.#.#.# ##.#.#.#.#.# #........#.# ######.###.# #......#...# ############ This is a 12 x 12 2-D array. So far, I can read/print the maze w/o problems, but the recursive function is a mess. Here's my code. Please help!! I don't know how to work w/ this recursive func. // My code: Find the way out of the maze using recursion //************************************************************************************************* **************** THIS IS THE PART THAT DOESN'T WORK ******************************** //Thanks to those that have offered me their comments. I understand now this code doesn't work at all. So please focus on the instructions and not this code. I'm leaving the code just so you can understand previous comments. Thank
Sounds like homework for a Programming with Data Structures class. Base case: found a path through maze - return true. Your algorithm should go something like this:
0-Base Case?
Yes - return true.
No - continue.
1-Select a direction to move [iterate through all directions].
2-Can you move in that direction?
Yes - Move, then recurse.
If function returns true - return true.
If function returns false - undo move, loop to 1.
No - Loop to 1
3-Return false [You've tried all directions at this level of recursion].-Sean ---- Shag a Lizard
-
UPDATED!!!! Now with Exact excercise instructions: In the preceding double-subscripted array, the #s 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. There may be a shorter path than the one you have taken, but you are guaranteed to get out of the maze if you follow the algorithm. Write a recursive function mazeTraverse to walk through the maze. The function should receive as arguments a 12-by-12 character array representing the maze, and the starting location of the maze. As mazeTraverse attempts to locate the exit from the maze, it should place the character x in each square in the path. The function should display the maze after each move so the user can watch as the maze is solved. Important data: 'S' represents the starting point of the maze 'E' represents the ending (exit) point of the maze '#' represents walls '.' dots represents the path where you can walk My file looks somthing like this: (please copy these characters and past them in to a word processor (e.g. notepad) to see it correctly. ############ #...#......# S.#.#.####.# ###.#....#.# #....###.#.E ####.#.#.#.# #..#.#.#.#.# ##.#.#.#.#.# #........#.# ######.###.# #......#...# ############ This is a 12 x 12 2-D array. So far, I can read/print the maze w/o problems, but the recursive function is a mess. Here's my code. Please help!! I don't know how to work w/ this recursive func. // My code: Find the way out of the maze using recursion //************************************************************************************************* **************** THIS IS THE PART THAT DOESN'T WORK ******************************** //Thanks to those that have offered me their comments. I understand now this code doesn't work at all. So please focus on the instructions and not this code. I'm leaving the code just so you can understand previous comments. Thank
I haven't compiled and run your code, but a casual inspection seems to reveal several errors:
- You check for unescapable mazes by verifying whether you have returned to the start position. This is wrong: consider a maze where you initially face a dead-end corridor; eventually you'll have to come to the start position, but that doesn't mean there are no alternative routes.
- Seems you're not checking whether you stumble into walls; instead you check for free space. If you happen to run into a wall,
solve_mazewill just exit. - Seems like you change direction at every step, so if you start in a position with no walls around, you'll go N-E-S-W and return to the start without exploring anything.
A good way to debug your code is to insert at the beginning of
solve_mazea screen dump of the maze, so that you can follow the progression of the algorithm. Right-hand strategy can be implemented withouth resorting to recursion. Recursion is required, though, for another strategy called depth-first; maybe the following pseudo code will help you write your code:bool solve_maze(row,col,direction) // depth-first strategy
{
if(in exit) return true; // we did it
if(!(we can advance in direction)) return false; // hit a wall or a place we already were at
move in direction; // update row and col
mark position; // use 'x' for instance
if(solve_maze(row,col,north)||solve_maze(row,col,east)||
solve_maze(row,col,south)||solve_maze(row,col,west)){
return true; // 'x's mark the way out.
}
else{
// we tried every direction to no avail. Return false
// indicating failure. Recursion will take care of trying
// previous positions.
unmark position; // clear out this failed step
return false;
}
}Joaquín M López Muñoz Telefónica, Investigación y Desarrollo