Power of Less

I'm reading the book called The Power of Less. It is one of those books on how to get things done. In the first chapter the there is a list of six principles of productivity. They are:

1. Set limitations
2. Choose the essential
3. Simplify
4. Focus
5. Create habits
6. Start small

How does that apply to game project? I must admit that every successful project I have worked so far have pretty much worked the way noted above. Most of them through accident, though. Note for programmers, focus-on-everything a.k.a. "make it generic" is not included in the list for a good reason.

Sketch for Hierarchical Pathfinding Using Detour

Several people have asked me how to implement hierarchical pathfinding using Detour, usually because they have so much pathfinding data that it is not feasible to keep it all in memory. This is common scenario in MMO game for example.

If I were to build an MMO pathfinding from ground up, I would make sure the world structure would have easy to use abstraction already build it. That is, if I were to travel long distances, then it makes sense to find path via certain land marks first and then in final stage find the actual path.

If you need to retrofit pathfinding to existing game, the following method might work for you.


Tiles as Path Abstraction
Detour allows you to break down the world into tiles and lot in only the data that you need. This data structure can be exploited to create hierarchical path finder.

The idea is that you first find which tiles needs to be travelled in order to get to the destination and then you find path within one tile at a time until you reach the destination. We need connectivity graph between the tiles to do the high level search.


Building High Level Graph

Take a look at a the highlighted tile in above picture. There are two separate contiguous areas A and B in that tile. A is at the street level and B is partially underground. The areas are not connected, so depending how you enter the tile, each tile may have different kind of connectivity to neighbour tiles.

The first step in building the higher level graph is to identify these contiguous areas of the navmesh. The simplest way to do this is to first find all the portal edges of the tile and flood fill along the polygons and visit all the portal edges of the mesh. Finally you can use this data to identify contiguous areas and which portals belong to them.

In order to build navigation graph from this data we need to deduct A* nodes from the data. There are several ways to do this, I'll explain two of them: 1) Nodes at portals, 2) Nodes at area centers. These two methods allow to trade off quality of the path and speed of the search.


Nodes at Portal Edges



As the name implies this method places an A* node at each portal edge center. After that the area information is used to connect the nodes within single area to each other and finally, using all the tile data, nodes at overlapping (connected) edges are at the merged.

This method allows higher quality paths if you use actual path distance between the nodes instead of using euclidean distance between the nodes. The con of this method is that it can potentially create a lot of nodes and links.


Nodes at Area Centers



This method places the A* nodes at the center locations of the contiguous areas. The connections between the nodes are calculated using the all the tile data just like the nodes were merged in the previous method.

Multiple links between area can be removed, and in general this method creates a lot less links than the portal center method. The trade off is that the high level path quality is likely to be worse than with the edge method.


Area Flags



If you want to use flags which enable and disable agent movement on the mesh, then you need to take this into account when building the high level graph. You should partition the mesh so that each area with different flags ends up having own node or link. In this case the nodes at area centers can be easier to implement.


Finding the Path

There are several ways to use this information to find path once you have found the high level path.

Firstly you could just load the tiles that are necessary to find path from the start location to the goal location. This is not the most effective way to do it, though. Ideally there should be a way to identity which tiles to visit during pathfinding. But if your main concern is memory, this method allows you to load the correct tiles and focus pathfinding.

Another way to use the information is to just find path within one tile. That is, always find path to the exit portal of the current tile and path find again from there. The tricky part is how to choose a good point at the exit portal. One way, perhaps a bit naively, would be to choose the nearest point on the edge and move there.



A bit more advanced method could be to use the the tile portals with the string pulling method Detour uses and find "straight" path along the tiles first and then use the intersection point between portal edge and the high level straight path as target to exit the current tile. Rinse and repeat until the goal location has been found.

Alternatively you could also use a "workspace" which is something like the next 4 tiles to get a bit more quality off the second method without trading off too much memory.


The key to optimize pathfinder, and applies here too, is to make a little work as possible. This is even more true when your world is dynamic, as a lot of work can potentially be thrown away when something changes.

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.