Detour API Changes

Once you update to R289 you will notice that the Detour API has changed a bit. This change was necessary so that Detour could support multiple layers per tile location.

Here's quick migration guide you should follow when switching to the latest code.

1) There is no need to remove the padding of the polymesh coordinates before the vertices are passed to dtCreateNavMeshData(). So if you had code, like this before, remove it! If you are not using tiles, this does not apply.

 // Remove padding from the polymesh data. TODO: Remove this odditity.
 for (int i = 0; i < m_pmesh->nverts; ++i)
 {
   unsigned short* v = &m_pmesh->verts[i*3];
   v[0] -= (unsigned short)m_cfg.borderSize;
   v[2] -= (unsigned short)m_cfg.borderSize;
 }

2) Since the polymesh data is not offset anymore, you can feed the polymesh bounding box directly to navmesh builder:

 rcVcopy(params.bmin, m_pmesh->bmin);
 rcVcopy(params.bmax, m_pmesh->bmax);

3) I made the BV-tree building optional as it is not needed for tiles which has just a couple of polygons. To keep the old behavior, you need to add this line to your navmesh build params:

 params.buildBvTree = true;

4) When you access tiles, you need to specify tile x, y and layer indices. If you don't use layers, just pass 0 (zero) as layer index. For example:

 m_navMesh->removeTile(m_navMesh->getTileRefAt(tx,ty,0),0,0);

That's it. The navmesh data number bumped so you will need to rebuild your data too.

I also removed the test code from Sample_TileMesh. From now on the Sample_TempObstacles will be my sandbox. The code to build tiles at runtime will live under DetourTileCache. It is all a bit of mess still, I'll keep you updated about the progress.

I think I will move back to numbered releases so that I can keep the SVN a bit dirty when I need to. Once the temp obstacle stuff is done, I think it is time to release Recast & Detour 1.9.

Oh, and I updated the VC project too!

Simulating Human Collision Avoidance

There were many good collision avoidance papers published last year. One trend that I saw already when I was preparing my Paris Game AI Conference presentation last year was that the next step in the human like collision avoidance will come from inspecting motion capture data.

One of my favorites from last year was A Velocity-Based Approach for Simulating Human Collision Avoidance by Karamouzas & Overmars. Technically their solution is very close to the sampling based RVO, but there is one very important difference; quoting the paper:

Our analysis, though, focuses on the predicted time to collision between interacting participants and the deviation from their desired velocities, whereas they studied the effect that the minimum predicted distance has on the participants’ accelerations.

In practice it means that they did bunch of measurements with real people and noticed that the velocity sampling range depends on the predicted time of impact.

That is, if the agent things it will hit something 3 seconds in the future, it is likely to adjust the speed and angle just a tiny amount, but if the collision is imminent, the agent may adjust the velocity a lot. The plot at the top of the post shows how the sampling range changes based on the predicted time of impact.

This is tiny detail, but very important one. The resulting animations (accessible via the link above) look pretty good too.

Bulletstorm is Using Recast

Much to my girlfriends disappointment, I just got my copy of Bulletstorm today! She was expecting the courier to bring her a fragrance from Venice and UPS brought this gory awesomeness from Warsaw instead.

Congrats to Mieszko and the gang at People at Can Fly for shipping such a great game! And thank you for mention me in the credits :)

Layers in Detour

Well.. this may look like a unmeasurable step in no direction at all, but it is indeed layered tile pieces working in Detour! There are a lot of rough edges to be fixed, but I'm glad I got this far.

Some things were a bit painful to debug. Looks like the tile stitching needs to be redone at some point in the future. As you can see in the above picture, the navmesh is missing a detail mesh. I have an idea how to make a semi good detail mesh really quickly.

Anyways, once I check in the stuff it means that Detour and Recast APIs will change a bit. I will write migration guide once I have polished the code a bit.

Temporary Obstacle Processing Overview

I was asked on twitter to give an overview of the navmesh generation process. Click on the above picture to see what happens when a temporary obstacle is added.

What is missing from the picture is the logic that triggers tile updates when an obstacle is added or removed. I have not quite figured that all out. The plan is to have one class that allows you to add and remove temp obstacles, and then you update that class each frame, give it a time quota, and it will figure out which tile layers to update based on the obstacle shape and finally update the navmesh.

The tile layers will be always updated all the way from the compressed data, so adding or removing an obstacle will be the same process, but the temporary obstacle set used to build the layer will be different.

The obstacle shapes are expected to be expanded by the agent radius.

Each obstacle marks an area type into the grid. This means that you can punch holes or just mark certain areas depending on what you do. My plan is to support a couple of obstacle types, like extruded polygons and circles, but nothing prevents you from inventing you own shapes too! Maybe you can have some kind of cone to describe a line of fire of an agent, or a sphere which describes the radius of an explosion.

I'm quite excited about the performance I measured earlier today! The final step is to connect it all to Detour. It will be mostly boring bookkeeping coding on how to connect the tiles and such.

Heightfield Layer Progress pt. 3

Today was scary day. I finally added some data collection to my heightfield layer code I've been working on recently. The numbers look super promising!

I measured the time to build navmesh for the above level, which I have been using earlier too. For build time and memory usage I measured the time that it takes to build a layer of navmesh from existing heighfield layer (rcHeightfieldLayer if you are familiar with the code). That is pretty much the bare bones of the process at runtime. I did not measure the time to rasterize temp obstacles yet.

I tested with a 32x32 tiles. The build time for a single tile layer varies from 0.01ms to 0.2ms, 95% of the tiles take less than 0.1ms. As expected there is some variation from run to run in the timings. The build process for one tile takes less than 15kB of memory. I'm really happy about that as all data could potentially fit in cache.

The data that needs to be stored in the memory takes 545kB for the above level, which compresses to 77kB using fastlz. What is interesting here is that the memory requirements for layers is smaller than for compressed compact heightfield even if there is a lot of waste in the layers. I think the win comes from the fact that there is no need for additional information about the layers.

Here's the complete test data in numbers.

Removed Old Sample

FYI – I removed the Solo Mesh Tiled sample which has been obsolete for quite some time already. It does not provide any advantage over using tiled mesh all the way through and has become a slight maintenance burden. I will keep the merge functions around for the time being, but eventually they might go away too.

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.

Insomniac is using Recast for Resistance 3

Just heard interesting news from GDC. Insomniac is using Recast to create navmeshes for Resistance 3! AiGameDev.com has coverage of the talk on their forum.

I was kinda expecting this based on the screenshots in Mike Acton's slides his unfinished usability presentation :)

I would love to know how they arrange the data so that they can do pathfinding on SPU. Their future directions look very much inlined with my ideas, i.e. rebuild tiles on SPU for sleeping temporary obstacles.

Can't wait to hear the whole presentation.