Recursive Solution to Any Maze And Stack Overflow Problems
So I'm trying write a program that will solve any maze using a recursive function. I keep coming close to solving it using a random number generator that tells the program where to move next if there is more than one possible move surrounding the space it is currently at.
My problem is that the program only runs a certain number of times and then gives me an error. So it never reaches the end of the maze. I have a base case for when it reaches the mark that denotes the end of the maze and I also have a function which will back track over spaces already visited if it gets into a space where it no longer has any possible moves. I have been working on this FOREVER and am incredibly frustrated. I've heard that this is because I have too many variables which will overload the stack but I don't know how to reduce the number of variables I feel like I need them all!!!!!!!!!!! Ahh!!!!!!
Re: Recursive Solution to Any Maze And Stack Overflow Problems
Quote:
Originally posted by PunkyBunny300
So I'm trying write a program that will solve any maze using a recursive function. I keep coming close to solving it using a random number generator that tells the program where to move next if there is more than one possible move surrounding the space it is currently at.
For creating use random. Don't use random for solving. To solve, use the "follow the left hand wall" approach.
Code:
if( north != been_there_done_that )
recursive( here->north );
if( east != been_there_done_that )
recursive( here->east );
if( south != been_there_done_that )
recursive( here->south );
if( west != been_there_done_that )
recursive( here->west );
return at_a_dead_end;
Basicly, as suggested, make a grid, pick your starting X and Y coords, and apply the above logic. When you get someplace, mark it as "visited". Or as in my example, "been_there_done_that".
Eventually you will map the entire maze, or you will hit the exit before that.
Quzah.