Hi guys,
I'm a newly registered member and liked to say hello.
I've been stumped on how to recursively solve this simple maze problem. I've been doing alot of reading on different types of algorithms to write, and I am doing this with a backtracking strategy. Now, let me explain. I have written the following functions (not going to display this code because it would be brain hating) :
I have functions to test if there is a wall, North/South/East/West. These return true if there is a wall in the specified direction. (e.g. I call NorthWall() and it returns true if there is a wall north of my current position)
The exact same principle goes if there is a marked cell. I also have a function to mark the current cell also. And I do understand, if I come to a dead end, I have to move back to a marked cell, pop the stack, etc.
I have boolean functions to tell me if I am at the end or if I am at the start.
I also have a function which lets me retrieve the current location. This is used to push it into a stack. ( At the end, I print the direct path in a coordinate style such as [x,y] (imagine a 2d grid).
And at last, I have functions which let me move in whichever direction (NSEW).
I've been writing code, and I keep trashing the code because I think my solution's if statements are too exclusive and the whole function starts to climb to 50+ lines of code. After deleting I've been stumped. Here is what I have laying around.
Code:
enum DIRECTIONS { NORTH, EAST, SOUTH, WEST };
static stack<int> sR, sC;
//if we make to the end
if( AtEnd() )
{
ofstream output("result.txt");
int r, c;
currentLocation(r,c);
output << r << " " << c << endl;
output.close();
}
if( !(WestMarked() && EastMarked() && SouthMarked() && NorthMarked()) ) //if the current tile isnt marked, mark it.
{
Mark();
}
if( !SouthMarked() ) //if south isn't marked, move there, mark it
{
GoSouth();
Mark();
}
if( !NorthMarked() )
{
GoNorth();
Mark();
}
if( !EastMarked() )
{
GoEast();
Mark();
}
if( !WestMarked() )
{
GoWest();
Mark();
}
I call the Traverse() function inside itself to make it loop, but I've been unsure if I should just include it at the end of function, or inside the if statements.
This shouldn't be taking me hours of thinking and writing to solve this.
Edit: I also wanted to say, I am using a graphical program to visualize everything. The program generates a random maze and I traverse through it.