Area Complete

Areas

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!

• Fast Exact and Approximate Geodesics on Meshes

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.

Simple Stupid Convex Hull

Sometimes you just need it, you know just to make sure your 7 point polygon is actually convex. Calculating convex hull would be awesome solution, but you kinda don't have an implementation at hand and you really would not like to write one as you are solving that other problem. You fire up Google, and end up browsing stupid animating Java implementations and get frustrated.

After browsing through dozen of sources using atan and the friends and that unsuccessful adventure of trying to remove the global variables from the Computational Geometry in C example code, and few attempts to find qsort_r that is actually portable, I landed on the following code with some help from Wikipedia.

It is Gift wrap (or Jarvis March), O(nh), does not need qsort_r, has pretty compact implementation, and simple enough to debug and fix too when it fails.

[Edit] Got bitten by floating points precision again. Updated the code so that it works better when you have large numbers. Updated formatting.

 // Returns true if 'c' is left of line 'a'-'b'.  
inline bool left(const float* a, const float* b, const float* c) 
{  
    const float u1 = b[0] - a[0]; 
    const float v1 = b[2] - a[2]; 
    const float u2 = c[0] - a[0]; 
    const float v2 = c[2] - a[2]; 
    return u1 * v2 - v1 * u2 < 0; 
} 
 // Returns true if 'a' is more lower-left than 'b'.  
inline bool cmppt(const float* a, const float* b) 
{ 
    if (a[0] < b[0]) return true; 
    if (a[0] > b[0]) return false; 
    if (a[2] < b[2]) return true; 
    if (a[2] > b[2]) return false; 
    return false; 
} 
 // Calculates convex hull on xz-plane of points on 'pts',  
 // stores the indices of the resulting hull in 'out' and  
 // returns number of points on hull. 
int convexhull(const float* pts, int npts, int* out) 
{ 
    // Find lower-leftmost point. 
    int hull = 0; 
    for (int i = 1; i < npts; ++i) 
        if (cmppt(&pts[i*3], &pts[hull*3])) 
            hull = i; 
     // Gift wrap hull.  
    int endpt = 0; 
    int i = 0; 
    do 
    { 
        out[i++] = hull; 
        endpt = 0; 
        for (int j = 1; j < npts; ++j) 
            if (hull == endpt || left(&pts[hull*3], &pts[endpt*3], &pts[j*3])) 
                endpt = j; 
        hull = endpt; 
    } 
    while (endpt != out[0]); 
    return i; 
} 

Slides from the Past

I was plowing through my old files the other day and found these. We had a master class over at AIGameDev.com more or less a year ago about Recast. Or actually it was not called yet Recast back then. The slides are pretty good overview of how Recast process works.

• AIGameDev.com master class slides

For more in depth explanation, there is a video of the master class available at the site too for subscribed member. It costs some, but there are tons of other good content you gain access too.

Area Progress pt. 5

Oh noes, this dude cannot swim so he has to walk around the pond!

I'm starting to be happy about the workflow of creating the areas and the ability flags and areas are passes all the way to Detour.

Solution

The solution I settled into was to use area type and ability flags per polygon. Area type specifies the cost to travel across the polygon and ability flags specifies if the agent can travel through the area at all. There are 64 area types and 16 abilities. Should be enough for everyone. The cost value will be multiplier to travel distance across the polygon.

Other than that Detour does not imply the meaning of flags or area types at all. The actual abilities and area types are specified by the game. Recast demo has some example types and abilities just to keep the samples consistent.

Convex Volumes

The building block of marking areas is extruded convex polygon. I will add other types as people need them. You should get pretty far with that type already.

Note that, the resulting area on the navmesh will not be the same as the input polygon. This is because the area generation goes through voxelization, which snaps the area to a grid, and through contour simplification which may cut few more corners. I'm eager to hear how this works in practice.

For the time being, I don't have plans to add area marking cookie cutters which work at geometry level.

To Do

The path finding cost is not adjusted yet. It is a bit nasty task to do as I need to refactor few things, such as querying the polygons during path search. I'm also seeing funky pathing cases here and there, which I hope to fix in the process too.

Another thing that still needs to be done is adding API to adjust the polygon ability flags and area types.

The latest iteration is available from the SVN, use with caution :)

Area Progress pt. 4

Initial batch of changes required for the area generation are in. Currently only Recast end of things are affected. The rest will follow in following days/weeks.

The SVN version will be in a flux until I've finished the features. If you feel like testing or early adopting for some reason, please note that there is one additional step now. Search for rcErodeArea() in the sample sources to see how things are done, also rcBuildRegions() has lost one of its parameters. [EDIT] rcBuildRegionsMonotone() is not currently support yet, it will be.

There were quite a few corner cases to be taken care of like, if an area falls on a tile edge or maybe not. I think I got 'em all, but if you see funky things at tile borders with areas, let me know.


Request for Comments on Flags and Types and Costs

Next up is Detour implementation. If you have some comments, suggestions, wishes, good experiences from past, I'm interested to know about it!

Here's my current strain of thinking quoted from a reply to one of the previous posts. And yes, I will be very mean and lean what it comes to memory, so you're not going to get 64 bits of flags per poly :)

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.