LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (http://www.linuxquestions.org/questions/programming-9/)
-   -   Algorithm to find paths (http://www.linuxquestions.org/questions/programming-9/algorithm-to-find-paths-547898/)

xeon123 04-21-2007 02:07 PM

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

xeon123 04-21-2007 02:08 PM

Sorry, this isn't the right questions.

One of the answer for this is Dijkstra's algorithm.

xeon123 04-21-2007 02:19 PM

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,

dmail 04-21-2007 04:32 PM

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.

[edit]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

matthewg42 04-21-2007 04:46 PM

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.

graemef 04-24-2007 02:18 AM

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 :)


All times are GMT -5. The time now is 02:11 PM.