Friday, February 12, 2010

Area Complete


I have finished the area stuff to the point that I feel that it is completed. There are still some features I want to add to it. I have added them as issues and I will work on them later on. If you see some features missing which have been discussed, feel free to add it there.

Per polygon cost is it, and polygon flags can be changed now. I also improved the performance of the pathfinder a bit. Depending on the query, I got somewhere between 10%-40% speedup.

I'm not too happy about the pathfinder. This is because Detour uses polygon edge midpoints as node positions during A*. Most of the time this is ok, but sometimes it produces ugly paths, especially close to locations where you have small and large polygons side by side. Thin polygons are nasty too.

Eventually I hope to improve this, but it will be more expensive. Following paper describes one possible solution. The problem is not easy to solve, and I don't have near term plans to fix it. If you have some insights to share how it could be solved, I'm interested to know!

Detail Mesh Improvements

There was a well known issues that the fringes of detail mesh would shoot to the skies when you use small agent radius compared to voxel size. I have improved this now, even zero radius should work fine. Zero radius will still produce some artifacts at the borders, which area due to voxelization. If you have some cases which still exhibits this problem, let me know.

Path Follow Improvements

I found some bugs where the path following and string bulling would create weird paths. This was due to floating point accuracy (yes, should use fixed point!) in 2D triangle area calculation (should have known that!). Moving along path and string pulling should be improved now.

I also updated my previous post about the convex hull, since it had this same problem.

Too Many Contours

In certain cases in presence of one voxel holes, the watershed partitioning fails and that will create areas with holes. There is code in the contour generation which catches this case, but it would often fail if there were many holes. I improved this so that the code allocates new contours as necessary.

Next Up

The next thing I will work on will be better serialization. I have been postponing it because the area stuff evolved a bit and I want to add support to save mesh "delta" too. That is, if you go and change the navmesh polygon areas and flags the state of the navmesh will change and that should be allowed to saved.

I'm still a bit torn how to implement custom up-axis. I have done some tests and got some contributions from other people to fix this, but there is some thing there that is still itching me a bit.

My current longer term plan is to move on to agent movement. I will work on the issues in the issue list and bugs too, but I want to give agent and especially multi-agent handling a good push forward.


  1. I have a previous version of Raycast/Detour running in my XBLA game. I hope to integrate this code soon. I'm very excited about the area code. I have a couple questions / requests:
    (1) I have agents of varying sizes, and I want the pathfinding to take this into account. I was thinking I could do this by making the agent radius 0, and then considering the agent radius in A* and string pulling, but it sounds messy. How have you handled this in the past?
    (2) I want an agent to avoid dangerous areas, where the danger is not constant (can't use and area and bake it in). Basically I want to somehow apply my own more complicated heuristic in A*, but I'm open to other suggestions.

  2. Detour uses funnel algorithm for string pulling. There is also a version which takes into account the agent witdth. Check this paper for exaplanation:

    Efficient Triangulation-Based Pathfinding

    It is more complicated to implement, though. Plus you will need to mark each poly with flag which describes the max movement radius through that polygon. The above paper describes how to do that too.

    My preferred solution (which Detour also reflects) for multiple sized agents is to use separate graph for each of them. It means that you will need to make some compromises on agent sizes to avoid using too much memory.

    I added custom path cost request to the google code issue tracker. If you have big polygons, your approach may not work the way you'd expect it to work. I don't have really good solution to that case other than somehow subdivide large polygons.

  3. One way to improve pathfinding would be to minimize the impact of the edge midpoint selection issue by allowing us to put a maximum size of mesh polys to prevent the merging process from making overly large ones.

  4. Great!.
    Could you separate memory of area's data from navmesh data?
    Because area's data can change dynamically while mesh data is static.
    ( I want to use multiple map instance with single navmesh. )

  5. Yoo-Seung,

    I'm planning to store the flags and costs in a way that is easy to serialize. That is, you will get continuous block of memory where all dynamic data is stored which you can dump to disk ad read back when you need it. That'll be one of then things that Issue 29 is all about.

    Is that what you mean?