Monday, May 31, 2010

Towards Better Navmesh Path Planning

As many users of Detour have noticed, navmeshes sometimes create extra detours in the paths. This is due how the cost of traversal between different polygons are calculated. The distance to travel from one polygon to another is often approximated either calculating the distance between the centers of the navmesh polygons or, between the edge midpoints of the navmesh polygons. As seen on the above pictures.

Edge midpoints is slightly better in practice, but both will create odd paths when you have long thing triangles or large polygons next to smaller polygons.

There is a nice recent paper Shortest Paths with Arbitrary Clearance from Navigation Meshes which describes another method based on visibility. I'm itching to try that out!

That paper also reminds me why Recast subtracts the agent radius before building the navmesh. It is just really complicated to find thick paths. Even just selecting a valid end point is really complicated matter.

[EDIT] Here's how the visibility optimized heuristic should work (heuristic #3). The idea is that if there is direct line-of-sight from the current node (S) to goal (G) via the next edge (e), then the node at the next edge will be placed at the intersection of the edge and segment SG. Else, the node is placed at the vertex which is closest to G. (The picture below assumes that the node locations are calculated and cached as they are encountered.)


  1. It's a really interesting paper, thanks for sharing! It's funny though, as I have been doing some experiments by myself with the cost function a few months ago to get better results, and I ended up implementing the *exact* same thing they describe as their "third metric" without knowing about it. And by the way, the results did look significantly better (at least with the data I'm working with), as it will favor paths heading more straightforward to the goal, which looks a lot more natural.

    I also agree using Minkowski sum in the navmesh makes a lot of problems so much easier to solve. It gets a little trickier when having to deal with multiple agent radius though, I wonder about your thoughts on that. Would you store one navmesh per agent radius? I could be wrong, but it would seem quite memory intensive, especially on consoles where memory is fought harshly for. :)

    Personally I ended up doing arbitrary tesselation around the obstacles, since I have mostly 2 radius to work with currently (hopefully), and ignoring these (marked) polygons when doing a search for an agent with a bigger radius. It's working nice, with a small loss for the smaller agent, which loses some of the nice properties of the polygon path necessarily being delimited by tile edges or obstacles, which helps a lot finding the "real" corners of the path and not from some arbitrary polygon. Nothing terrible to work with though. :)

  2. My solution would be have as few as possible agent size groups, and to have different navmesh for each agent size. Then I would spend a little efford on trying to have as little as possible navdata in memory at once, by just loading the necessary tiles (as in Detour navmesh tiles).

    Then I would use flags to try to take into account the small differences the different agents using the same mesh might have (there always are some).

    I don't think your method is bad either. The worst part being that the smaller agent type will have more polygons to traverse during A*.

    Have you measured the difference between having more tesselation vs. two meshes?

    But I think in the end it might be faster to have higher tesselation than to use the truly variable with path search.

  3. At first glance this paper present simple layering - each agent's radius is a layer.
    Plus string pulling as a post process - after search pull string from current polygon center up to nexts until we intersect obstacle. And so on.

  4. how did you find this paper mikko? do you regularly search for any new papers on this topic?

  5. Jad, it is good to check Ke-Sen Huang's page every now and then, lots of pointers to good papers:

    But these things surface every now and then when I google on something related to my work.

    I think I found this one via Ke-Sen's page.

  6. cool thx, I have trouble keeping up to date while still focusing ...

  7. This comment has been removed by a blog administrator.

  8. This comment has been removed by a blog administrator.

  9. This comment has been removed by a blog administrator.

  10. This comment has been removed by a blog administrator.