Thread: Q: Recursion to find all paths of a maze

  1. #1
    Registered User
    Join Date
    Nov 2002
    Posts
    3

    Q: Recursion to find all paths of a maze

    Hi all.

    I've been working on a program that will find all possible paths through a maze. I can find the way through the maze no problem, but what I want to try to do is to get it to find all the paths so after I can determine which one is the shortest/quickest path. My problem was that with my recursion algorithm I would take the same path over and over (of course).

    So, I came up with this type of algorithm:

    1.) Go through the maze, storing each 'turn' that is made
    2.) Block the 'turn' closest to the end of the maze so you do not repeat that path.
    3.) If a dead end is reached, fill the dead end with a wall-type character so you do not continue down that path.

    Eventually with this you end up 'closing' each path to be made through the maze. The first time through the maze it works, then the second, but then it just gets all buggy and doesn't work.

    I'm not trying to get anyone to write this code for me, because I am doing it mostly out of curiousity. But my question is, am I making it more complicated than it has to be? Or is there a simpler algorithm to solve the problem?


    Code:
    Example Maze:
    
    O = start
    X = end
    
     ##########
     #        #
     # ## # #O#
     # ## # ###
     # ## # #X#
     # ## ### #
     #      # #
     # # ## # #
     #        #
     ##########
    Thanks in advance.
    Last edited by reti; 11-25-2002 at 11:55 PM.

  2. #2
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356
    here is a link http://cboard.cprogramming.com/showt...threadid=29167
    The maze stuff above is not recursve if that what u want then this same question has been intrduced to this board many times ...try the board search for maze solving ..??You will end up with more than 50 links ..

    Cheers
    "I wish i could wish my wishs away"

    "By indirections find directions out" -- William Shakespears

    "Do what thou wilt shall be the whole of the law" -- Crowley "THE BEAST 666"

    Mizra -> love = Death...
    RDB(Rocks yooo)..

    http://www.cbeginnersunited.com

    Are you ready for the Trix ???

  3. #3
    Registered User
    Join Date
    Nov 2002
    Posts
    3
    That's different than what I was asking. And yes, I did do many searches but I could not find anything for what I was trying to do. If I missed one, then I am sorry. Also, mine is recursive.

    My program reads the maze from a file that has already been created then just runs through it and will choose the best path. Yours is quite different (that or I am missing something, sorry).

    Thanks.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    For building a maze and traversing one, you can use the same algorythm. In your case, I'd suggest something like:

    1) Use an array the size of the array to store the path.
    2) As you go down the "path", increment your counter and fill in that cell in the array.
    3) When you reach the end, compare the counter with your "solved" counter. If it's less, then you have a new path.
    4) Copy that "path" (the contents of the array) to a holding array.
    5) Backtrack the maze until you reach a fork in the road, and take it instead. If you reach the end on this fork, goto step (3) Otherwise, repeat step five because you're at a dead end.

    When you've been everywhere, whatever path is in your holding array is the shortest.

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

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    202
    The maze problems I've done in my classes have all been FIFO based linked lists, I trust you're doing something similar?

    In any case, it seems to me that the chief problem for you to solve is to explore every possible path in the maxe, and only keep a record of those that actually traverse the entire maze. For each traversal, just maintain some kind of count of the number of steps you needed to take until you "give up" on the current exploration. If you "give up" because you reached the end, bravo, keep a record of that, otherwise chuck the result. After You have explored every path in the maze, just compare how many steps each successful traversal took; the one with the shortest steps is the most efficient.

    In any case, it would help if you could show more than just the maze diagram. *cough *cough *code.

    starX
    www.axisoftime.com

  6. #6
    Registered User datainjector's Avatar
    Join Date
    Mar 2002
    Posts
    356
    Originally posted by reti
    Yours is quite different (that or I am missing something, sorry).

    Thanks.
    No u arnt
    "I wish i could wish my wishs away"

    "By indirections find directions out" -- William Shakespears

    "Do what thou wilt shall be the whole of the law" -- Crowley "THE BEAST 666"

    Mizra -> love = Death...
    RDB(Rocks yooo)..

    http://www.cbeginnersunited.com

    Are you ready for the Trix ???

  7. #7
    Registered User
    Join Date
    Nov 2002
    Posts
    3
    Originally posted by quzah
    For building a maze and traversing one, you can use the same algorythm. In your case, I'd suggest something like:

    1) Use an array the size of the array to store the path.
    2) As you go down the "path", increment your counter and fill in that cell in the array.
    3) When you reach the end, compare the counter with your "solved" counter. If it's less, then you have a new path.
    4) Copy that "path" (the contents of the array) to a holding array.
    5) Backtrack the maze until you reach a fork in the road, and take it instead. If you reach the end on this fork, goto step (3) Otherwise, repeat step five because you're at a dead end.

    When you've been everywhere, whatever path is in your holding array is the shortest.

    Quzah.
    That is *exactly* what I am trying to do Quzah and I know that's what I have to do. But the only problem I have with it is getting it to take a different path. I can get it to 'back track' each time but then I keep getting the same results after the first 2 paths. Thanks though

    It'll probably help if I post the piece of code that I am having problems with when I get home later on.

    Thanks everyone.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >But the only problem I have with it is getting it to take a different path.
    You missed the part where quzah said to fill in the location. This is marking the path as visited so that you don't go down it again.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. noobie maze program
    By stormfront in forum C Programming
    Replies: 9
    Last Post: 11-30-2005, 10:23 AM
  2. A Problem with recursion
    By Adamkromm in forum C++ Programming
    Replies: 4
    Last Post: 09-28-2005, 08:35 PM
  3. Find Dialog
    By Lithorien in forum Windows Programming
    Replies: 6
    Last Post: 04-25-2005, 05:28 PM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM