Thread: Maze Solving algorithm

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    14

    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.
    Last edited by mrJTparadise; 02-24-2012 at 08:53 PM.

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    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.

  4. #4
    Registered User
    Join Date
    Feb 2012
    Posts
    14
    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.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  6. #6
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by mrJTparadise View Post
    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 \..

  7. #7
    Registered User
    Join Date
    Feb 2012
    Posts
    14
    Thanks for the assist to both of you. After about an hour or so I got a solution. Still tweaking it and such, but will post solution if anyone is interested.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Solving a Maze in C, Help needed
    By Krote in forum C++ Programming
    Replies: 2
    Last Post: 06-22-2011, 10:32 PM
  2. Help solving a maze!
    By cosio55 in forum C Programming
    Replies: 2
    Last Post: 11-10-2010, 09:02 AM
  3. Solving maze using rec'
    By gavra in forum C Programming
    Replies: 14
    Last Post: 07-13-2008, 09:20 AM
  4. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 01:52 AM
  5. Maze Solving Cont....PLZ
    By jonnybgood in forum C Programming
    Replies: 30
    Last Post: 11-11-2005, 04:00 AM