# Maze Solving algorithm

• 02-24-2012
Maze Solving algorithm
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.
• 02-24-2012
VirtualAce
It has been a long time since I wrote any code for this so let me see if I can remember it. Wait I don't have to because I can Google it.
Think Labyrinth: Maze Algorithms

In all seriousness I forgot the algorithm I used long ago. It might still be on the forums if you search for it.
• 02-24-2012
manasij7479
For a 2d maze, you're making it more complicated than it has to be.
Backtracking is alright, but for 2d, there is already a great intuitive way to backtrack. Just follow a wall and stick to it. You're guaranteed to reach the end.
i.e. Maintain a state called direction, depending on which you'll call your Go*() functions. Whenever it reaches a block, turn (but turn the same way everytime).

Graph algorithms could probably solve it a lot quicker, but is a lot more work to implement.
• 02-24-2012
VirtualAce, I've already read those algorithms, and I understand them, just turning them into code is the part I'm puzzled on.

manasij7479, you are talking about the right-hand rule? The right hand rule makes sense, as in if you follow a wall you will eventually make it to the end. But there are so many cases in which when to go EAST, WEST, etc. Checking if there is a wall in whatever direction and checking if so and so is marked, I just get lost. I just picture it with a boatload of if-statements. I need something to get me going.
• 02-24-2012
VirtualAce
For starters mazes are recursive in nature. I would try some recursive approaches to solving the mazes. If I remember correctly the simple algo goes like this:

• Push cell x,y on a stack
• Pick a random direction to move - N, S, E or W and record the direction you moved in the cell
• If the new cell is empty start the process over
• If the new cell is occupied pop off the stack and pick a direction you have not tried for the cell - start process over from cell on stack
• Repeat until all cells have been visited.

I do not remember all of it but that should get you started.
• 02-24-2012
manasij7479
Quote:

manasij7479, you are talking about the right-hand rule? The right hand rule makes sense, as in if you follow a wall you will eventually make it to the end. But there are so many cases in which when to go EAST, WEST, etc. Checking if there is a wall in whatever direction and checking if so and so is marked, I just get lost. I just picture it with a boatload of if-statements. I need something to get me going.

Not really a boatload of if statements..
In pseudocode:
Code:

```while(not_in_the_end_cell)     while(nothing_in_front)         move(current_direction);     turn_left() //This changes the current_direction     record_current_position()     if(at_starting_position)         NO_SOLUTION```
Notice the indentation carefully though \..
• 02-25-2012