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

21 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