Heightfield Layer Progress pt. 2

Firstly, I apologize the current state of the SVN. Some files are missing from the VC project, some headers have messy stuff and there are some extra stuff in the UI. I often like to check in stuff I'm working on when I get to a certain point so that I can revert if the new direction is a dead-end. It usually takes few tries to get something figured out properly.

The above image show some phases of the new navmesh generation procedure. It is very much like the original Recast version, but I added some extra constraints to the data.

Firstly, the voxelized heighfield is first split into 2D layers. These layers are stored in compressed form. This 2D data can be packed more easily than 2.5D data as neighbour data is more often similar.

When the navmesh of a a portion of the level needs to updated, for example when a temporary obstacle is added or removed, the layer data is uncompressed the obstacles are rasterized, and the navmesh of that layer is rebuild.

The layer structure ensures that each uncompressed layer takes the same amount of memory during process, which helps to manage the memory layout. Less data also means more local memory access, which should speed things up too.

Secondly, I have limited the max tile size to 255. This means that I can use bytes as coordinates and further reduce the memory requirements. The same magic number limits the maximum number of regions per layer too.

I'm currently sweeping through the code and try to remove allocations as much as I can. The code will require allocations, but I have been able to remove a lot of reallocs, which makes the code more linear allocator friendly. My goal is to make the memory consumption below 64k, on tile sizes between 32-64, maybe even 32k is possible for the sizes closer to 32x32.

There are some things left to do on the generation side, like removing those excess vertices. I think I'll wait until I finish those things before I dare to measure the performance.

After that I will need to figure out how to change Detour to support multiple layers. My current plan is to store each tile at location (x,y,layer), where the layer is just some number you decide yourself. This should nicely allow other kinds extra navmesh layers too, like overlapping streaming sections, etc.

Also, another nice side effect is that the layer generation process will make 2D navmesh generation much easier. Basically you could just feed in an image and get navmesh out.