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.

Rough Fringes

I though I'd start this time with something else than a boring screenshot. This is how it looks like over here right now. I'm still hoping that I could reclaim my snot producing organ back to its more purposeful function. Getting much better, though. Should be back in the regular action next week (so less blog posts ;).


Holes in the Navmesh

There has been one bug popping every now and then, which is pretty nasty to fix. The problem is input geometry that has short steep slopes, usually in form of bevels or some sort of decorative geometry. The result is that those polygons will create one or two voxel holes around the edges and as a result you get holes in the navmesh. Over conservatism not for the win in this case.

When Recast processes the input geometry to voxels and detect walkable areas, it uses two criteria, surface slope and step height. Step height is there to allow to climb over sharp features of the input geometry and slope is used to detect contiguous "flat-ish" regions.

There are two ways to detect slopes from input geometry. Firstly, you could detect the angle of the input polygons and mark the ones with steep slopes and non-walkable, secondly, you could run a filter over portion of a voxelized region and detect the slope from that.

The second option is more flexible, but too costly and from my past experiments I noticed that it is quite prone to noise in the input resulting other kinds of unwanted holes in the mesh. The first option is considerable faster and it is the methods used in Recast.


The Current State of Affairs

I made following test case to highlight this problem. All the obstacles but F have such height that the agent should be able to walk over them. Obstacle A is simple box with beveled edges. Obstacles B-E are the same shape, B is twice the size of the others, C is on ground, D is above to ground but still low enough for the agent to walk over, and E is two obstacles stacked on top of each other.


And here's the resulting mesh. Not very nice to look at. The other two images show first the voxels, and then the input geometry. The red polygons in the input mesh are considered too steep slopes. The dark red voxels mark non-walkable areas.



And here's a close up of three of the culprits. The problem is that because of the voxelization, sometimes the whole voxel can belong to a polygon which is marked as non-walkable.


There is already some code which tries to favor walkable surfaces over non-walkable if they are really close to walkable ones. The very first solution to fix the problem in hand would be to extend that.

Instead if really small distance--previous the threshold was 1 voxel--we could increase the favoring distance up to step height of the agent. The resulting mesh after the change is as follows.


A bit better. Some cases got fixed completely. Obstacles which are not directly connected to a walkable ground still have problems. The next step is to go through all the voxels and check if there is a walkable surface just below it at max step height from the current voxel surface. This fixes pretty much all the remaining problems. The filtering can be done by calling rcFilterLowHangingWalkableObstacles()



Filtering Neighbours

There are certain cases where this procedure can try to cut corners too much. Even without the new additions, the step height check sometimes produces too optimistic situations. The problem so far has been that the step height only tests between to neighbours.

If there are many voxels next to each other which all require large steps, then the algorithm could walk steep ledges. If this information were to come from sloped polygons, the neighbours would have been marked as non-walkable.

So I also added a fix for this case, since it is more likely to happen with the newly added code. The magic happens in rcFilterLedgeSpans() and it marks voxels which have step requiring neighbours at opposite directions as non-walkable. Finding neighbours of rcHeightfield is really costly, so I combined this function to another filter which already requires neighbours.

Below is an example of a case that this new test fixes. The corner at the middle of the edge comes from the fact that the character can stand closer to the base of the pedestal up to the peek than at the downhill where the bottom part of the base becomes wall too.

Detour Performance

I've been ill the past week, and I thought I'd use the time between naps and sneezing to catch up with things I think that needs to be done, but have been to numbing to do unless you are somehow light headed. Profiling while trying to get new exiting features finsihed is one of those tasks.

I have not checked the performance of Detour in quite a while. New features have been poured in, meshes have now detail, arrays changed to linked lists, and what not.

I added a simple test case code which loads a map, sample, generates the mesh and runs batch of pathfind requests. The results were not too devastating, but I sense that there is room for improvement later on.

The menu to launch the tests are behind a magic button, since I have not distributed all the meshes I use, the code is a bit hackish, etc.

The pathfind request in the title image takes about 0.111 ms. That is complete with querying two nearest polygons at the start and end locations, A*, and string pulling the final result. The mesh consists of about 710 polygons, and as you can see the A* touches almost all the polys there.

A* seems to be the bottle neck, I'm pretty sure there are room for improvement in there. Once I get into optimization mood, I think I need to find better profiling tools, simple perf timer query does not seem to be accurate enough (I'm using the preferred unix way to get the timer value).



The above picture shows how much path you can get for 0.051 ms (the start it at right near the text, the end is at left where the yellow line finally ends). Depending on your per frame budget that can be a little or a lot. I'm not panicking yet.

Off-Mesh Connection Progress pt. 3

Almost there! I just got the Off-Mesh connections to work with tiles. It was a bit more work than I expected.

I like tight data structures and that was one of the things why things got quite complicated with Off-Mesh connections. Previously all the links were stored in one big array, and each polygon would have base index plus number of links which specified the links per polygon. It was reasonable painless to extend that to allow add few links in between using double buffering and bit of precalculation.

The way I chose to implement the Off-Mesh connections required some of the data to be resolved at runtime. That made managing nice array of links eventually too complicated. So after long struggle I switched to linked list which is build initially so that it creates contiguous strips for internal edges and after that all dynamic edges are allocated from simple free list.

I have not done any performance testing yet, I don't expect it to be that much slower and I hope it will help me to improve some more dynamic features later.

The link structure currently is a bit too heavy to my taste, it's 12 bytes. Typically links take somewhere between 30-60% of the memory consumption per tile. If I can get rid of bmin and bmax of the link without causing too much burden at the runtime, I should be able to pack edge and side to the extra bits of the next index, which would leave 8 bytes per link (and roughly 15-20% less memory usage in total).

A bit more testing and cleaning up and I can let off-mesh connections to be as is for a little while until I will visit them again to add the segment-to-segment links. There are some rough edges which need to be fixed for the demo too. I've yet to come up with good visualization of the Off-Mesh links which would allow me to draw them while editing and when they are "baked" into the navmesh.

There has been some contribution work done to allow Recast and Detour to work on different coordinate systems, definitely a feature which will help many users. There are couple of things related to that which I have not quite settled in yet, but that feature should see the daylight soon too.

Off-Mesh Connection Progress pt. 2

I just submitted bunch of off-mesh connection related code to the SVN. I think most of the functionality for point-to-point links are in place. The only things missing so far is tile-to-tile links and some optimizations. I also added polygon filtering functionality for the Detour API where it seemed valid.

The number of arguments to dtCreateNavMeshData() started to become so many that I put them in a separate structure, which is passed to the function. All in all, the API changed quite a bit, but not dramatically. If you have question about migrating to the new API, let me know.

The special link feature is called off-mesh connections, not off-mesh links. The reason is that these special connections are actually stored as polygons. It allows the off-mesh connections to be nicely visible in the query functions. See the path iteration code in NavMeshTesterTool::recalc() for more details.

Next up is tile-to-tile connections, then better support for serialization, and after that I think I'll have another stab at the area stuff. Segment-to-segment off-mesh connections did not come out very naturally, the implementation ideas for that need a bit more simmering.

Off-Mesh links Progress

I have worked a little towards off-mesh links (a.k.a jump-links). That is, extra annotation other than polygons which act as links in the navigation graph. My long term plan is to support point-to-point and segment-to-segment off-mesh links. The first iteration will only bring you the point-to-point links.

The term link might be a bit missleading, as the links actually appear as polygons in the system. This simplifies a couple of internal representations as well as makes the extra links visible on queries so that it is easy to handle them.

The current SVN version is in flux, so do not update just yet! I will finish this feature during next week.

The pathfinder and string pulling works ok (not fully tested), couple of other features are still missing, though. I also want to improve the link connection procedure, currently many links will slow down initialization way too much.

As you might have noticed I have worked a couple of features in parallel (areas, off-mesh links, serialization, debug drawing, static/tile mesh merging, etc) during the past months. The reason is that many of the features were dependent on other features, so have tried to finish the most common nominators first. Now that I get the dependencies better I can focus my work better and I hope that the new features will start to get finished too.