asnowcappedromance Posted December 2, 2011 Share Posted December 2, 2011 (edited) 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 Dijkstra_Pathfinding_Manu_v3.hip Edited December 2, 2011 by asnowcappedromance 1 Quote Link to comment Share on other sites More sharing options...
Ole Posted December 2, 2011 Share Posted December 2, 2011 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! Quote Link to comment Share on other sites More sharing options...
asnowcappedromance Posted December 2, 2011 Author Share Posted December 2, 2011 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.com/blog/dijkstras-algorithm-illustrated-explanation It's a detailed explanation of the algorithm, it helped me a lot to get what's going on under the hood. SOP_Dijkstra_Pathfinder_PyOp.otl Quote Link to comment Share on other sites More sharing options...
kursad Posted December 7, 2011 Share Posted December 7, 2011 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 Quote Link to comment Share on other sites More sharing options...
asnowcappedromance Posted December 7, 2011 Author Share Posted December 7, 2011 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 Quote Link to comment Share on other sites More sharing options...
kursad Posted December 9, 2011 Share Posted December 9, 2011 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 Quote Link to comment Share on other sites More sharing options...
vi_rus Posted January 30, 2012 Share Posted January 30, 2012 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) Quote Link to comment Share on other sites More sharing options...
asnowcappedromance Posted February 1, 2012 Author Share Posted February 1, 2012 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++ Quote Link to comment Share on other sites More sharing options...
Jason Posted February 1, 2012 Share Posted February 1, 2012 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? Quote Link to comment Share on other sites More sharing options...
vi_rus Posted February 1, 2012 Share Posted February 1, 2012 I can share source code, if it'll helps you at c++ learning) Quote Link to comment Share on other sites More sharing options...
asnowcappedromance Posted February 1, 2012 Author Share Posted February 1, 2012 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! Quote Link to comment Share on other sites More sharing options...
hyperforce Posted March 25, 2012 Share Posted March 25, 2012 (edited) 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 March 25, 2012 by hyperforce Quote Link to comment Share on other sites More sharing options...
asnowcappedromance Posted March 26, 2012 Author Share Posted March 26, 2012 sure, no big deal, be my guest 1 Quote Link to comment Share on other sites More sharing options...
Farsheed Ashouri Posted March 26, 2012 Share Posted March 26, 2012 I can share source code, if it'll helps you at c++ learning) Could you please share your code here? I need to learn HDK. Thank you in advanced. Quote Link to comment Share on other sites More sharing options...
vi_rus Posted March 27, 2012 Share Posted March 27, 2012 Could you please share your code here? I need to learn HDK. Thank you in advanced. SOP_Dijkstra_Creator.rar Quote Link to comment Share on other sites More sharing options...
hyperforce Posted March 27, 2012 Share Posted March 27, 2012 (edited) Manuel, I'm trying to implement your solution into my level generator and its working fairly well. (I've added in an image) The 3D grid is invisible in the image, but I've photoshoped in some dark red markers to give you a sense of depth in the image. cooking times get rather long very fast however and the more complex it gets the higher the chances are one or more lines aren't generated correctly. I'm not sure if this is related to the algorithm or due to the foreach nodes. I am getting a lot of "breaking while loop" warnings however. The 3D grid i'm using has roughly 10.000 points with roughly 8-12 connections each. vi_rus, would it be ok if I try to implement your HDK version? And if it is, do you have an example file that I can try to implement? Thank you in advance. Though I'd understand if you refuse. Edited March 27, 2012 by hyperforce Quote Link to comment Share on other sites More sharing options...
petz Posted March 27, 2012 Share Posted March 27, 2012 (edited) if you are going the hdk route anyway, wouldn´t it be the easiest to use one of the many existing graph-libraries like bgl (boost graph library), igraph, ...? most libraries provide numerous shortest path algorithms that should be pretty fast for around 10000 points. petz Edited March 27, 2012 by petz 1 Quote Link to comment Share on other sites More sharing options...
hyperforce Posted April 19, 2012 Share Posted April 19, 2012 I thought I'd show you what your Dijkstra's Algorithm solution has allowed me to build so far: I'm using it to build the corridors and where they cross smaller rooms as you can see below: Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.