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.