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.

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

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.

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.

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

Quote:

---

Originally posted by reti
Yours is quite different (that or I am missing something, sorry).

Thanks.

---

No u arnt ;)

Quote:

---

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.

>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