LinuxQuestions.org
Did you know LQ has a Linux Hardware Compatibility List?
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
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

Reply
 
LinkBack Search this Thread
Old 04-21-2007, 02:07 PM   #1
xeon123
Member
 
Registered: Sep 2006
Posts: 363

Rep: Reputation: 16
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
 
Old 04-21-2007, 02:08 PM   #2
xeon123
Member
 
Registered: Sep 2006
Posts: 363

Original Poster
Rep: Reputation: 16
Sorry, this isn't the right questions.

One of the answer for this is Dijkstra's algorithm.
 
Old 04-21-2007, 02:19 PM   #3
xeon123
Member
 
Registered: Sep 2006
Posts: 363

Original Poster
Rep: Reputation: 16
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,
 
Old 04-21-2007, 04:32 PM   #4
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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

Last edited by dmail; 04-21-2007 at 04:41 PM.
 
Old 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: Reputation: 62
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.
 
Old 04-24-2007, 02:18 AM   #6
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,376

Rep: Reputation: 147Reputation: 147
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
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
token bucket algorithm vs Leaky bucket algorithm xeon123 Linux - Networking 2 03-26-2007 04:57 AM
Wine can't find paths in Mandriva 2005 LE kalahari875 Mandriva 3 06-28-2005 07:22 AM
Where can I find source code for CPRM algorithm? George2 Programming 2 03-13-2004 04:06 AM
Automatically resolving WINDOWS paths to pre-configured Linux paths gazzy Linux - General 1 09-05-2003 10:15 PM
assistance with an algorithm mandrake_linux Programming 3 07-27-2001 04:03 AM


All times are GMT -5. The time now is 04:32 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration