1 Replies - 2983 Views - Last Post: 10 March 2012 - 12:02 PM Rate Topic: -----

#1 cupidvogel   User is offline

  • D.I.C Addict

Reputation: 31
  • View blog
  • Posts: 593
  • Joined: 25-November 10

Better method to find out shortest path in a maze?

Posted 10 March 2012 - 07:43 AM

Hi, suppose we are given a maze like this:

...#0.#....#0..
..........##...
....#.#..0.....
..0.......0..#.
...#...#......#
..#..#....0.0#.
0......*...#...
....#..........
.0....#...0#..#
.....0..#......
0....#....0..#.
...............
..........0#..0
0....#.....#...
.......0....#..



The asterisk marks the starting position, the zeroes are doors reaching upon any of which results in Jerry's escape, and the hashes are obstacles. I have to find out the shortest path to any door from Jerry's current position. I am doing a method like this: First I have a variable named length with arbitrarily large value, say 60000. Next I build a tree with the current position as parent node. From there I find all possible directions where Jerry can go. If any one of them is a door, I quit immediately and decide that the shortest path has a length of 1, otherwise I make one of those possible cells as the new father node and continue like that. When I find a door, I set length to the value from the starting point upto that point. While traversing, if the length of the path already becomes longer than length, I assume that this cannot lead to a path shorter than the one I have already found, so I back off, restoring its father node to the current node. Ultimately when I arrive at the original father node (found by the fact that it has no father) and find that there are no more cells to go from there (that is, all have been traversed through), I decide that the current value of length is the shortest path available and print its value. Problem is, for larger matrices, this method is taking huge amount of time. Can anyone suggest a better algo?

This post has been edited by cupidvogel: 10 March 2012 - 12:07 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Better method to find out shortest path in a maze?

#2 tlhIn`toq   User is offline

  • Xamarin Cert. Dev.
  • member icon

Reputation: 6535
  • View blog
  • Posts: 14,450
  • Joined: 02-June 10

Re: Better method to find out shortest path in a maze?

Posted 10 March 2012 - 12:02 PM

Putting stuff like this that should be mono-spaced inside of code tags helps because it keeps its formatting.
:code:

...#0.#....#0..
..........##...
....#.#..0.....
..0.......0..#.
...#...#......#
..#..#....0.0#.
0......*...#...
....#..........
.0....#...0#..#
.....0..#......
0....#....0..#.
...............
..........0#..0
0....#.....#...
.......0....#..


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1