2

I'm trying to write a program to find the shortest path in a 3D maze using recursion.

I am able to write the code that finds a random path through the maze but I'm wondering how I can modify my code in order to find the shortest path.

Please note that I want to keep the recursive approach.

Can someone suggest a solution?

Here is a sample 2D maze:

s    
XXXX 
XX X
XXX  
Xe  X

One starts from s going to e. X is an obstacle and is the route.

beaker
  • 16,331
  • 3
  • 32
  • 49
Gary Devil
  • 21
  • 3
  • What is your data structure to store nodes? – Prateek Gupta Sep 05 '16 at 13:43
  • The maze is a 3D grid actually. I'm using a 3D table and each node is defined by his cartesian coordinates (x,y,z) . – Gary Devil Sep 05 '16 at 13:50
  • Why do you want to go for recursive solution? It isn't faster always. Try reading about `A* Algorithm`. – Prateek Gupta Sep 05 '16 at 14:00
  • I have tried Dijkstra's algorithm before trying recursivity, however, it is too slow. For example, it takes the algorithm 7 seconds to solve just a 2D 30x30 maze. That's why I wanted to move to recursivity. Is A* much faster than Dijkstra ? – Gary Devil Sep 05 '16 at 14:05
  • Please read this page on [A* algorithm][1], it is much faster with a good heuristic. Mind that designing a good heuristic function is a challenge in itself. [1]: https://en.wikipedia.org/wiki/A*_search_algorithm – Prateek Gupta Sep 05 '16 at 14:16
  • I can't imagine Dijkstra's taking 7 seconds for a graph of that size. How are you getting the neighbors of each node? Do you build an adjacency list beforehand, or do you check the neighborhood when you reach each node? Since your graph appears to be unweighted, BFS would also be another (fast) approach. – beaker Sep 05 '16 at 14:44
  • I actually check the neighborhood when I reach each node. Is it a bad approach ? – Gary Devil Sep 05 '16 at 15:08
  • Actually, it sounds like quite a reasonable approach. It all depends on the implementation. – beaker Sep 05 '16 at 20:12
  • The problem was coming from the implementation of the function that generates the next node to go to : I was using a loop that took too much time. I fixed it by using a priority queue and it's much faster now. However I still can't solve a 30x30x30 maze in a reasonable time, it takes 2 minutes to solve it. I'm going to try A* search. Any advice ? – Gary Devil Sep 05 '16 at 20:44

1 Answers1

0

It depends on the algorithm you are implementing. If you want a recursive approach then finding a random path is a good start point (although if the problem is too complex then a bad choice could have huge effects on number of attempts needed for convergence). Afterwards you need to modify the path and for example check whether the new path is shorter than the pervious one; if yes then you continue modifying your parameters in the same direction. Otherwise you have to change your direction. Exit criterium for the algorithm/ program is normally the difference between the found solution and the ideal solution. So if you know the length of the ideal path (the optimal solution, you need not know the path itself but only its length) in advance then you can define an error margin of 10^-9 for example and once the difference between both solutions is less than this margin your algorithm exits.

In conclusion, this question is a mathematical optimization problem. Optimization is a field which has well-established literature eventhough it is a little bit complex. However if I were you I would search for shortest path algorithms and implement one which is best suited to my application (3D Maze)

mshabeeb
  • 577
  • 2
  • 9
  • 25
  • I have tried Dijkstra's algorithm before trying recursivity, however, it is too slow. For example, it takes the algorithm 7 seconds to solve just a 2D 30x30 maze. And that's why I wanted to move to recursivity – Gary Devil Sep 05 '16 at 13:56
  • Besides, I actually don't know the length of the ideal solution, I want to find it and I need the exact length not just an approximation, so error margins aren't to be considered here. – Gary Devil Sep 05 '16 at 13:59