Monday, August 1, 2011

Hierarchical Pathfinding in Detour

Uwe Koch has written a great thesis about hierarchical pathfinding with navmeshes. He presents a generalized version of HPA* implemented in Detour. The short summary: 4-5 times faster than Detour's A*, and uses 10-20 times less memory (graph nodes).

Applying graph partitioning to hierarchical path´Čünding in computer games

24 comments:

  1. Disclaimer: my implementation is very sloppy and not meant for production at all.
    The main thing to take away, in my opinion, is that HPA* combined with graph partitioning works very well.

    ReplyDelete
    Replies
    1. Could you please rebuild the Source Code patch you provided - there is no DetourPartition.h in it. futher more I cant find out how to apply it to current recast navigation revision so could you please tall us on which revision that patch was made?

      If you could send new patch to my email phenix.pink@gmail.com or publish it in some paste bin and provide a link that would be grate!

      Thank you for your effort in advance.

      Delete
  2. Would you be interested in porting the implementation into .NET C# for comparison and promotional opportunities?

    ReplyDelete
  3. (Sorry for spamming here -- I wasn't able to find your email address anywhere!)

    I was just wondering if there are any resources you could point out for how to "vectorize and partition" a binary image? I'm referring to your comment here that I replied to:

    http://altdevblogaday.com/2011/07/29/path-finding-for-princes/#comment-268906568

    This is something I've been trying to find a good solution for but thus far I don't even know the correct search terms! :)

    ReplyDelete
  4. Raigan, I don't have good off-site references, but if you are fine browsing some source code, you can find 2D implementation of monotone partitioning and contour finding and polygonization here:

    http://code.google.com/p/recastnavigation/source/browse/trunk/DetourTileCache/Source/DetourTileCacheBuilder.cpp

    The function dtBuildTileCacheRegions() takes an input image (layer.areas) where 0 means nonwalkable and other values are different areas to bake into the mesh. The first part of the function builds monotone regions and the second part (with remapping and all that) merges the regions further.

    dtBuildTileCacheContours() will walk the contours of the regions, and dtBuildTileCachePolyMesh() triangulates the contours, and removes vertices along the boundaries of the tiles so that they can be later stitched together.

    That code is supposed to be used at runtime (for tiles < 128x128) and is carefully crafted so that it allocates very little memory assuming a linear allocator.

    Maybe I should write an #altdevblogaday entry about that :)

    ReplyDelete
  5. Thanks! I think a blog post would be great -- it seems like a pretty important step/process.

    Are there any papers or other resources that are related to your solution?

    The problem in general of covering a region with the minimum number of convex pieces seems like one of those NP-hard/NP-complete problems, and also possibly one that's received some attention/study.

    I was hoping that constraining it somewhat (i.e only allowing axis-aligned rectangles rather than convex pieces) would help simplify, but sadly that doesn't seem to be the case :(

    The world I'm working in is larger than 128x128, but I'm hoping that I can spread things out over multiple frames and/or recalculate sub-regions incrementally as things move and change.

    Anyway, I'll check out the code, thanks again!

    ReplyDelete
  6. @Raigan, I took me a good year to figure out a method to partition an area to nice non-overlapping pieces. I use two methods: watershed partitioning and monotone partitioning. Watershed generally creates better looking regions, while monotone partition is really fast.

    For small partitions (<64x64), monotone partitioning can be easily done in sub millisecond. The downside of monotone regions building is that tends to create long thing partitions. One way to fight against that is to split the world in tiles. See this post as an example:

    http://digestingduck.blogspot.com/2009/08/monotone-regions.html

    My old Recast slides have some pointers about the watershed partitioning:
    http://digestingduck.blogspot.com/2010/02/slides-from-past.html

    Both of these algorithms work on discrete grid, and the point is to parition the area into regions which do not contain holes, so that they are easy to triangulate.

    ReplyDelete
  7. Awesome! I guess I'll dig into the source and see how the monotone decomposition works :)

    ReplyDelete
  8. Are you gonna implement this on detour?

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. Hi Mikko,

    First Off, this is awesome. I was writing a Ray-casting based Navmesh generator a few weeks ago. I did have a nice solution for cutting the cluster of points into nice rectangles that I can work with. But, then I saw your info on the watershed partitioning. I was wondering if you could tell me, how you determine the catchment basins for the regions as I am rather confused on how it is calculated.

    ReplyDelete
  11. Hi Sorcus,

    Take a look at these slides, it has overview of the algorithm:
    http://digestingduck.blogspot.com/2010/02/slides-from-past.html

    Let me know if you need some further details.


    --mikko

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. This comment has been removed by the author.

    ReplyDelete
  14. Sorcus, when you raise the "water level" it will cover new "land". When the water level is raised, I first allow the existing areas to grow, and after that I will check any non-connected areas and mark them with a new id. The latter can be done using flood fill.

    ReplyDelete
  15. Apologies, for the double nuke and thanks a lot for the reply. I had read through your slides once before, but I really had to go through your slides a couple of more times. I will post again when I have more questions :)

    Thanks again

    ReplyDelete
  16. Also take a look at this paper:
    http://maverick.inria.fr/Publications/2003/HDS03/index.php

    It has good explanation of watershed partitioning. It was an eye opening paper for me back in the days.

    --mikko

    ReplyDelete
  17. Thanks! Also, I have to say, your article on string pulling/funnel algorithm was very interesting. I couldn't find a proper reference to it earlier, though. I have always wondered how to actually solve the path smoothing, but I see now that the funnel works better than most things I tried earlier!

    ReplyDelete
  18. Awesome! but I can't find DetourPartition.h file in the diff file and code folder. What am I missing?

    ReplyDelete
  19. This comment has been removed by the author.

    ReplyDelete
  20. Thanks for sharing:
    Evan Luthra a young billionaire who was ahead of his time and is now investing in brilliant minds like him.Evan Luthra is one of the youngest tycoons in the IT industry today and has invested in numerous tech projects to this date. Evan Luthra started giving TedX speeches at the age of 18 and since then, he has also spoken at some of the most prestigious events including Crpto Investor Show, Blockshow, etc. He has been featured in 30 under 30 entrepreneurs list and is known to support and guide budding entrepreneurs through his incubator Startup Studio.

    Having accumulated years of experience in the tech industry, Evan Luthra is today spearheading innovation in projects that are laying the foundation of our better future. He is not just a co-founder and COO of EL Group International, but he is also an active contributor in the global entrepreneurship community. Through Startup Studio, he is able to identify emerging businesses and share his business acumen that can drive these projects to success.

    Although Evan Luthra invests in all kinds of tech projects, he focuses on blockchain projects as that sphere has become more of his specialization. He was instrumental in the success of blockchain projects like Relictum Pro, Crescent, and Relictum Pro.Evan Luthrais also influencing the world through his social media handles. With over 500,000 followers he is always sharing bits of his life and words of wisdom to let the world know that Evan Luthra is there to listen to your extraordinary ideas.

    ReplyDelete
  21. The links to the thesis and source code are dead. Does anyone have any pointer to this work (HPA*)?

    ReplyDelete