Sunday, January 31, 2010

Fresh Start for Areas

I got a little time today to work on the areas. I got pretty nice progress. I have most of the generation stuff worked out, next up is to figure out how to make it fast and to define how things map eventually to Detour so that it is possible to specify different costs for different areas as well as to filter out movement on certain areas completely.

The general work flow is such that it is possible to paint certain surfaces on the voxel representation that those areas will translate to polygons with area tagged to them in the final navmesh.

You may notice from the picture above, that certain areas get some extra vertices. This is due to the watershed partitioning which is not 100% accurate. It usually not visible when you have non-axis aligned data, but it is more underlined when you do. In certain cases the monotone partitioning algorithm may be more suitable.


  1. Nice, does this include areas marked automatically by the rasterization process? For example using 2 different agent heights to separate crouch and standing areas?

  2. Eventually it will. I ran into some problems the last time I tried implementing that, I hope to address it after I get this simpler stuff in all the way to Detour.

    Basically the problem with the agent height stuff is how to mix it with other area types (plus that it generates a lot of noise). You may get lots and lots of tiny polygons all over your map as combination. I think I got the filtering quite good the last time. I hope to find simpler solution to all this now.

  3. How do you plan to set these areas up data-wise? Would it be possible to have the tags available runtime rather than just resolving the resulting weights when the navmesh is generated?

    Aside from modifying weights (sometimes dynamically), I really find tags useful for also completely filtering out areas or requiring that a character only move through areas with specific tags.

    Furthermore, I find tags are generally useful for doing centralised world markup - putting all AI world interpretation data in the same place. Therefore it would be useful to for instance be able to have multiple tags on the same area.

  4. I'm still a bit contemplating how to implement the flags/tags/area-types.

    I'm currently leaning toward a solution where you have 6bits of area types, and 10bits of flags. The area type specify cost and flags can act as boolean filter.

    The generation process will allow to mark areas. The shape of the area along with its' type will be there in the final navmesh. For testing purposes I just created a box area type, but I hope to support other shapes as well as per input triangle area type.

    You are free to convert certain area types to flags too. For example roads, dirt and tall grass might just be different weights, but water might get its' own flag.

    On every game and engine out there flags and types and their filtering usually have the nastiest implementations. I hope to avoid the common pitfalls, and I know I won't be able to please everyone.

    The current type/flags thing is meant to be pretty much static thing and something you can apply to all agents.

    On top of this, I might also add some kind of custom cost thing, which allows you to add cost locally for certain query. More about that once I get the first things done :)

  5. Now,how to add some kind of custom cost things in your recast navigation tool?