17 replies to this topic

[asnowcappedromance]

hey guys,

I thought it's time to test my python skills and decided to give the Dijkstra Pathfinding Algorythm a shot.
Some credits actually go to Sam Hancock who inspired me to do this project, I gladly took a peek at his approach before I tackled the problem,
also I have to thank my friend Michael Davis who always throws in some kickass workflow tips.

After a couple hours of work I was able to solve the (too me a big) mystery - as I never dealt with such stuff before it got quite interesting.
The biggest problem I ran into was calculating the distances between connected points (the "neighbours") in Python,
it gets really messy as there is no such thing as an edge in Houdini compared to other packages (I'm not complaining, only a little) -
so I decided to go back to VOPs and use the neighbourCount and neighbour nodes which provided a really fast and flexible workaround.

During my little ride I actually solved the travelling salesman problem (TSP) accidentally, see the attached image  

Anyway, I'm attaching the scenefile for everyone who's interested,

cheers,

Manu

Attached Thumbnails

• 
• 

Attached Files

•  Dijkstra_Pathfinding_Manu_v3.hip   223.41K   211 downloads

Edited by asnowcappedromance, 01 December 2011 - 11:32 PM.

[Ole]

asnowcappedromance, on 01 December 2011 - 11:31 PM, said:

hey guys,

I thought it's time to test my python skills and decided to give the Dijkstra Pathfinding Algorythm a shot.
Some credits actually go to Sam Hancock who inspired me to do this project, I gladly took a peek at his approach before I tackled the problem,
also I have to thank my friend Michael Davis who always throws in some kickass workflow tips.

After a couple hours of work I was able to solve the (too me a big) mystery - as I never dealt with such stuff before it got quite interesting.
The biggest problem I ran into was calculating the distances between connected points (the "neighbours") in Python,
it gets really messy as there is no such thing as an edge in Houdini compared to other packages (I'm not complaining, only a little) -
so I decided to go back to VOPs and use the neighbourCount and neighbour nodes which provided a really fast and flexible workaround.

During my little ride I actually solved the travelling salesman problem (TSP) accidentally, see the attached image

Anyway, I'm attaching the scenefile for everyone who's interested,

cheers,

Manu

Thank you for sharing!

[asnowcappedromance]

terribly sorry, forgot to attach the otl file, without it the scene is useless. My bad!
Here you go!

One thing that I'd like to add is the following link:
http://eoinbailey.co...ted-explanation
It's a detailed explanation of the algorithm, it helped me a lot to get what's going on under the hood.

Attached Files

•  SOP_Dijkstra_Pathfinder_PyOp.otl   6.41K   168 downloads

[kursad]

asnowcappedromance, on 02 December 2011 - 09:34 AM, said:

terribly sorry, forgot to attach the otl file, without it the scene is useless. My bad!
Here you go!

One thing that I'd like to add is the following link:
http://eoinbailey.co...ted-explanation
It's a detailed explanation of the algorithm, it helped me a lot to get what's going on under the hood.

Hey thanks for the file. I was actually working on a similar problem. So this is great.

As a side note, the group SOP provides a way to select the connected points. It might provide a much more concise way to get a decent list of connected edges. I have been looking into ways to build the list of connected edges and this was one of the ways I came up with, although it is not as sexy as using vop and python that is for sure

[asnowcappedromance]

I'm glad you like the setup!
It's far from perfect though, haven't had any time to polish it up, going on vacation tomorrow
Yeah, I know about the group SOP but it's slow as hell and using VOPs is 10x faster that's for sure and if you're worried about this approach
being concise, believe me it is. Also, VOPs would allow you to use point clouds which is even faster, so if you would limit the search to a certain
radius you could speed it up even more. The python operator kills the speed though, the Dijkstra method is far too slow as is computes every single shortest
path for the whole geometry.

cheers,

Manu

[kursad]

asnowcappedromance, on 06 December 2011 - 09:53 PM, said:

I'm glad you like the setup!
It's far from perfect though, haven't had any time to polish it up, going on vacation tomorrow
Yeah, I know about the group SOP but it's slow as hell and using VOPs is 10x faster that's for sure and if you're worried about this approach
being concise, believe me it is. Also, VOPs would allow you to use point clouds which is even faster, so if you would limit the search to a certain
radius you could speed it up even more. The python operator kills the speed though, the Dijkstra method is far too slow as is computes every single shortest
path for the whole geometry.

cheers,

Manu

Manu, thanks for the heads up. I have not tried the group sop but I just knew that it could create the connection groups.

I have not used the neighbors nodes before and your example explains it very well. Thanks again

[vi_rus]

It's really nice realization of Dijkstra algorithm! But python is too slow for this purposes... So I decided to rewrite python code with hdk. Check out what I did)

View on Vimeo.

[asnowcappedromance]

that is indeed very impressive!!
You're totally right, Python is not the best approach to do it, I think I should learn how to write c++

[Jason]

This is nice and useful project! Thank you!

There is also the inlinecpp module if you don't want to dig into the gory internals of the HDK, perhaps?

[vi_rus]

I can share source code, if it'll helps you at c++ learning)

[asnowcappedromance]

vi_rus, on 01 February 2012 - 03:16 AM, said:

I can share source code, if it'll helps you at c++ learning)

much appreciated Sergei, I sent you a pm!

Oh and thanks for that link, Jason, I'll have a look at that!

cheers!

[hyperforce]

Hi Asnowcappedromance,

I have to say great work on implementing Dijkstra's algorithm.

I have a question.

I'm currently working on my specialization/graduation (graduation year) college program at IGAD-NHTV.

My project is to find a way to create a generator that can build functional and playable multiplayer levels that can be exported to a game engine.
I've been looking at different methods to make the generator construct logical corridors throughout my levels and a
path-finding solution seems to be the most promising.
I am however no programmer and know nothing when it comes to python script.

Would I be allowed to use your solution in my research and potentially my graduation project?
You will of course be referenced and credited for the method and OTL if I succeed in implementing it into a working solution.

Edited by hyperforce, 25 March 2012 - 01:06 PM.