PDA

View Full Version : Path Finding Algorithm


nier
07-06-2007, 01:38 PM
Hello!

I was wondering if anyone here has ever tried to implement any kind of path finding algorithms in MEL or Python.

I have a map with connected segments, represent a street network of a city. I have then a target and a starting point, and I want to find out the shortest path between them. I have something figured out, but it does not work when it reaches dead ends, for example...

I was looking for info in the net, and found out about this A* algorithm which seems pretty interesting, but I am completely lost about how to implement it...

Any ideas??

Thank you!
Daniel

uncle_frankie
07-06-2007, 02:01 PM
Hey

I've implemented A* in Python for a Blender Game Engine project

You can find the most recent source at the end of this thread

http://blenderartists.org/forum/showthread.php?t=67442

hope this saves you some work

cheers

GennadiyKorol
07-06-2007, 04:52 PM
Hey,

A* is a generalized version of graph path search algorithms. Me thinks it's far beyond your simple needs.
In your place I'd take a look at Dijkstra (shortest paths in graph with weighted edges, ie, length of an edge) or BFS (for finding shortest paths in number of edges).

BFS is very simple to implement even in MEL, and should give you pretty decent results. Dijkstra would require implementing the heap data structure, which could be implemented as an array in MEL, which would require just a bit more work.

Then again, it depends on what shortest paths you are interested in :)

Hope that helps,
Henry

goleafsgo
07-06-2007, 06:32 PM
The polySelect command can do something like what you want.


// The numbers are vertex id's...
polySelect -shortestEdgePath 121 251 pTorus1;

// These numbers are uv id's...
polySelect -shortestEdgePathUV 263 127 pTorus1;

nier
07-07-2007, 04:48 PM
well, I really wnat to find out some more simple solution to my case, and it seems BFS might be the answer... I am looking for stuff about it right now... Polyselect won't be the case, as I am mostly dealing with curves as paths...

Here is an image of what I am dealing with... it is the street network of a small village in Switzerland, and the surfaces will work as target/starting points (they represent the plots on the streets). There will be plenty of them, these in the image are only for testing purposes.

I have stored all the curves vertices, as well as the location of each surface on its curve, so I know on which curve I have to start and on which I have to end. I just need now to figure out how to do that lol

http://www.nier.com.br/arquivos/temp/cgTalkpathFinding.gif

nier
07-07-2007, 05:18 PM
Found a great website explaining in a very simple way how to apply the BFS algorithm...
Pretty much what I wanted...

http://ai-depot.com/Tutorial/PathFinding-Blind.html

Now it's *just* a matter of trying to implement it lol

GennadiyKorol
07-07-2007, 05:55 PM
You could implement a stack with an array in MEL, which would be very similar to C or C++ implementations, event easier because MEL will handle array memory allocation for you :)

Then just implement the pseudo code of the BFS algorithm :)

CGTalk Moderation
07-07-2007, 05:55 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.