Saturday, 18 January 2014

SHORTEST PATH FINDER FROM A MAZE IMAGE

1/18/2014 08:22:00 am

                             This matlab code finds the shortest path that can be traversed to go through a maze from starting pointing to required ending point. The algorithm used is simple and straight forward. This code first looks for one of the possible path from starting point to destination. This path is actually obtained by looking for a way to make the next move in a specific direction (here down first) and moves in the direction if there is a possible way. If not then it checks for left and moves in that direction if there is a possible way and finally right if there isn't any path in the down and left direction.

Here are some images showing possible ways that the object can move in different situations.

1
Object moves left
2
Moves down
3
Moves back twice and then right

Now that we found one of the possible path we go now in the reverse direction and find all possible paths. Since we have all possible paths all we need to do is find the shortest among them by simple calculations.
The following video shows how all the possible paths are obtained.....




Here's the source. Just unzip it and use it in whatever way you want...

Written by

4 comments:

  1. can't we decrease the time complexity of algorithm?? it'll tak lots of time as the maze increases.......

    ReplyDelete
  2. Hey Anudeep thanx for your interest... If you are talking about the video, the delay between each path being shown was intentionally introduced so that we would be able to see how the program finds the shortest path. It actually takes lot much lesser time to solve the maze. You can check it yourself. Download the source above and run the Main.m file. It took me a total time oof less than one second.....

    ReplyDelete
  3. How can I do like the video above ? I want to show the maze solve step by step before it reach the finish. Help me, please..!!

    ReplyDelete
    Replies
    1. I made a script to plot all the possible paths (appearing in red) frame by frame with a delay and then screen recorded it.

      Delete

 

© 2013 The Repository. All rights resevered. Designed by Templateism

Back To Top