Thread: Recursive Solution to Any Maze And Stack Overflow Problems

  1. #1
    Registered User
    Join Date
    Dec 2002
    Posts
    28

    Unhappy 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!!!!!!

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    One way of solving a maze type problem is to use
    a grid[M][N] label it so that grid[M][N] = 1 if it is a wall
    grid[M][N] = 0 if empty and grid[M][N] = -1 if it is empty
    and visted. Then you basically do a depth first search
    by calling the algorithm on adjacent unvisted empty nodes recursivily.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: Recursive Solution to Any Maze And Stack Overflow Problems

    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.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Dec 2002
    Posts
    28
    Would either of these solutions solve a maze that was 9 by 9 and had the end point in the center of the maze and no walls except the outer ones in the maze?


    This is not the maze that I have to solve but... I was instructed to make my algorithm such that it could solve any maze.
    Last edited by PunkyBunny300; 12-13-2002 at 02:31 PM.

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Either follow a wall, as was suggested, though this will only work if the start and goal are at the perimiter.

    Or follow every path, and make a recusive split if the path splits into 2 or more ways. Mark the visited paths so you don't end up in an endless recursion. See picture:
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Magos
    Either follow a wall, as was suggested, though this will only work if the start and goal are at the perimiter.
    Not true. My example will always solve any maze.
    Code:
    ###################
    #                 #
    # ####### # #######
    #   #     # #    ##
    # ##### ### # #####
    #     #S#   #     #
    # ### # # ### # ###
    #   # # #E#  ##   #
    ###################
    n,n,w,w,e,e,e,e,n,n,
    w,w,w,w,w,w,s,s,e,e,w,
    w,s,s,e,e,e,e,s,s,n,n,
    w,w,w,s,s,e,e,n,n,n,n,
    n,n,n,e,e,e,e,e,e,e,e,
    e,e,s,s,s,s,w,w,s,s,

    Vola. Solved. The code example I gave will *always* solve any maze. If you use more directions of travel, just add them in. Basicly you always follow the same order as you go around any given intersection. You will always eventually reach the end.

    That's what I mean by "follow the wall". You actually follow around a set order at every intersection. (IE: "Always turn left".)

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    You can't solve my example maze by following the wall. If you follow the left wall, you will end up at the start again (and obviously the same if you follow the right wall). That's because the goal lies in a separate section (notice that the walls in the middle aren't connected to the outer walls, which they are in your maze).

    Your solution path isn't 100% correct (you miss some moves) but I noticed that you most of the time walks with the wall at your left side, but at the end suddenly do a right turn...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Magos
    Your solution path isn't 100% correct (you miss some moves) but I noticed that you most of the time walks with the wall at your left side, but at the end suddenly do a right turn...
    That's what I meant by "following the wall", I should have said, "Always turn left." instead. And yeah, It may be slightly off at the end. I didn't write a program to solve that maze and dump the text. I just typed it in by hand. Basicly you get the idea of how it works. That algorythm, which is the code I provide above, will always solve any maze.

    And the only reason that a "follow the wall" will fail is if there is more than one way to solve a maze. Any "perfect", I believe that's the term", maze will be solved by "follow the wall". A non-perfect (ie: more than one patch connects a given cell to another) maze may foil a "follow the wall" algo, like you said:
    Code:
    ###########
    #    E    #
    # ### ### #
    # #     # #
    # # #S# # #
    # # ### # #
    # #     # #
    # ####### #
    #         #
    ###########
    The "follow the wall" just follows around and around and around the center block. My example would solve it.

    [edit]
    Actually, I should have rephrased that, my code actually is "always turn right", so the solution for my example would have been basicly on the first shot. Right turn, right turn, solved.
    [/edit]

    Quzah.
    Last edited by quzah; 12-13-2002 at 03:45 PM.
    Hope is the first step on the road to disappointment.

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    ONe major downfall to using recursion to solving a maze (especially if you do as Magos suggested and test every path) is that if you use are solving a decent sized map you will have a stack overflow pretty quick. Unless the maps are always very linear--which defeats the purpose of a maze--the recursion should be used conservitively for this application.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by master5001
    ONe major downfall to using recursion to solving a maze (especially if you do as Magos suggested and test every path) is that if you use are solving a decent sized map you will have a stack overflow pretty quick. Unless the maps are always very linear--which defeats the purpose of a maze--the recursion should be used conservitively for this application.
    Yes and no. With huge mazes, at best you should end up with a number of recursions the same size as the maze. The same basicly holds true with non recursive maze solving. You end up having to have an array or (insert data structure here) the same size as the maze itself.

    With most recursive functions, unless you're introducing new variables, you shouldn't have too much stack overhead per recursion:
    Code:
    int recurse( Node *room )
    {
        room->state = USED;
        if( room->north != USED )
        {
            recurse( room->north );
        }
        if( room->east != USED )
        {
            recurse( room->east );
        }
        if( room->south != USED )
        {
            recurse( room->south );
        }
        if( room->west != USED )
        {
            recurse( room->west );
        }
    }
    Incomplete, but close enough to illustrate. The only thing here is the need to backtrack at dead ends. So you'd probably want a parameter to pass as the direction you came from.

    But yes, you're right also in that you can run out of stack space on very large mazes.

    The benifit of non-recursive solutions, is while it does require basicly a duplicate of the maze (space wise), it isn't allocated on the stack so it avoids overflow.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Dec 2002
    Posts
    28
    Code:
    +---+----+---+
    |            |
    |            |
    |            |
    +     X      |
    |            |
    +            +
    |            +
    +--+--+--+--++
    Will your code solve this? with x as the end point? Because I would consider this a maze (and I believe game theory does also)....
    And I'm not trying to be nitpicky... well I am... but I really need to be sure that this way will solve any maze... and I don't see how the following the wall or making left hand turns will solve this... I haven't tried coding it for myself yet...
    Last edited by PunkyBunny300; 12-13-2002 at 04:58 PM.

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Of course it will. Apply the logic. The "maze" doesn't need any walls. It doesn't even have to be an array. It could be a list of lists. Whatever, it doesn't matter, so long as you provide the code to "move" in a given direction, and a way to mark that "cell" as having been looked at.

    "If ThisDirection is not used, move this way and then mark where we move as used."

    That's the basic algo.

    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by quzah
    That algorythm, which is the code I provide above, will always solve any maze.
    And the only reason that a "follow the wall" will fail is if there is more than one way to solve a maze. Any "perfect", I believe that's the term", maze will be solved by "follow the wall". A non-perfect (ie: more than one patch connects a given cell to another) maze may foil a "follow the wall" algo, like you said:
    Perhaps you should rephrase the "solve any maze" into "solve any maze that has exactly one solution" then . In that case I agree with you.

    Sorry, but i can be a little pedantic over details sometimes...

    Oh, and can you explain how PunkyBunny's maze works, I didn't get it. Is it just a lot of space so 'following a wall' won't do much?
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  14. #14
    Registered User
    Join Date
    Dec 2002
    Posts
    28
    It works! Yay!!! Thanks so much guys!!

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Magos
    Perhaps you should rephrase the "solve any maze" into "solve any maze that has exactly one solution" then . In that case I agree with you.
    No. My example will solve any maze. The code I provided will solve any maze. Apply the logic.

    What I was referring to "Put your left hand on the wall and walk" will only solve mazes where there is no chance of a small circle (example box #2).

    The code example I provided is not "walk with your hand on the wall", it is "if there is an open neighboring cell, move there", and it will solve any maze. Period.

    There were two concepts discussed:
    1) Walk with your hand on the wall.
    2) Walk in any given non-used direction, in methodical order. (IE: Always turn left.

    The code example is the latter. There is a big difference between walking with your hand on the wall, and always turning a direction, provided it (that cell) hasn't been traveled before.

    Quzah.
    Last edited by quzah; 12-14-2002 at 08:31 PM.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive Stack Algorithm Maze Solver
    By unrestricted in forum C Programming
    Replies: 0
    Last Post: 09-04-2007, 03:11 AM