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 pathfinding in computer games
at

24 comments:

  1. andicAugust 1, 2011 at 3:34 PM

    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. JokkerSeptember 15, 2013 at 4:56 AM

      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. AnonymousAugust 2, 2011 at 3:53 AM

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

    ReplyDelete
  3. AnonymousAugust 2, 2011 at 3:59 AM

    nice!

    --stb

    ReplyDelete
  4. OP-101August 2, 2011 at 3:39 PM

    (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
  5. Mikko MononenAugust 2, 2011 at 10:50 PM

    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
  6. OP-101August 3, 2011 at 11:19 AM

    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
  7. Mikko MononenAugust 3, 2011 at 11:37 AM

    @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
  8. OP-101August 3, 2011 at 1:47 PM

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

    ReplyDelete
  9. noneAugust 19, 2011 at 4:40 AM

    Are you gonna implement this on detour?

    ReplyDelete
  10. SorcusOctober 14, 2011 at 6:39 PM

    This comment has been removed by the author.

    ReplyDelete
  11. SorcusOctober 14, 2011 at 6:40 PM

    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
  12. Mikko MononenOctober 15, 2011 at 12:33 AM

    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
  13. SorcusOctober 15, 2011 at 2:06 AM

    This comment has been removed by the author.

    ReplyDelete
  14. SorcusOctober 15, 2011 at 2:17 AM

    This comment has been removed by the author.

    ReplyDelete
  15. Mikko MononenOctober 15, 2011 at 2:31 AM

    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
  16. SorcusOctober 15, 2011 at 2:34 AM

    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
  17. Mikko MononenOctober 15, 2011 at 2:41 AM

    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
  18. SorcusOctober 15, 2011 at 3:34 AM

    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
  19. alloshaDecember 26, 2011 at 2:04 AM

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

    ReplyDelete
  20. JokkerSeptember 9, 2013 at 7:36 AM

    This comment has been removed by the author.

    ReplyDelete
  21. Evan LuthraMarch 18, 2020 at 6:53 AM

    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
  22. adminJune 27, 2021 at 7:49 PM

    google 464
    google 465
    google 466
    google 467
    google 468
    google 469

    ReplyDelete
  23. Peterson GashAugust 26, 2021 at 11:48 AM

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

    ReplyDelete