Support LQ: Use code LQ3 and save \$3 on Domain Registration
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Algorithm to find paths
 User Name Remember Me? Password
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 04-21-2007, 02:07 PM #1 xeon123 Member   Registered: Sep 2006 Posts: 368 Rep: Algorithm to find paths I'm trying to find the name of algorithms to find ways. For example, suppose that i'm in a labyrinth, and i want to find the exit. - How can i build an algorithm to find the exit path, from several possibilities? - Exists a right algorithm? - What's the name of the algorithm? Thanks, Pedro
 04-21-2007, 02:08 PM #2 xeon123 Member   Registered: Sep 2006 Posts: 368 Original Poster Rep: Sorry, this isn't the right questions. One of the answer for this is Dijkstra's algorithm.
 04-21-2007, 02:19 PM #3 xeon123 Member   Registered: Sep 2006 Posts: 368 Original Poster Rep: What i'm asking is: For example, i've the following labyrinth in an array of Strings: Code: ```####.# #..#.# ##.#.# #x...# ###### #..### ######``` The x marks the initial position. The '.' marks a path. The '#' is a wall. 1 - Know, i want to transform the labyrinth, to a form that i can apply an algorithm like the Dijkstra's algorithm. Can anybody help me? 2 - Count the number of faces of the wall from the labyrinth. The problem is that, in only counts the wall that can be reachable from the exit. Ie, the path that is unreachable, doesn't count. Can anybody help me? If you answer to this question, you don't need to write code or pseudocode. Just tell me what should i do. Thanks,
 04-21-2007, 04:32 PM #4 dmail Member   Registered: Oct 2005 Posts: 970 Rep: Dijkstra is not the correct algorithm for this as it's a greedy algorithm and normally used when X's position is not know, instead you want to use A*. When areas are unreachable they should be marked as such, so that algorithm does not try every node possible. X does not mean x as you have it just some position like your exit. Here is a good tutorial on the algorithm http://www.policyalmanac.org/games/aStarTutorial.htm Last edited by dmail; 04-21-2007 at 04:41 PM.
 04-21-2007, 04:46 PM #5 matthewg42 Senior Member   Registered: Oct 2003 Location: UK Distribution: Kubuntu 12.10 (using awesome wm though) Posts: 3,530 Rep: Dijkstra's walk might not be suitable because it is expensive (although it will find the best path). An alternative is A*, which is popular in games because it is generally much cheaper. A good paper on path finding can be found here.
 04-24-2007, 02:18 AM #6 graemef Senior Member   Registered: Nov 2005 Location: Hanoi Distribution: Fedora 13, Ubuntu 10.04 Posts: 2,379 Rep: To answer your question about how to transform the maze. You want to express the problem as a graph. Each point on the maze is a node and the path is set up from node A to node B if there is a path in your maze. The number of faces of the wall will be 4 - the number of paths from that node. I hope that makes sense. If you require a better explanation just shout