Digesting Duck

Loose Navigation Grids

2012-01-01T07:54:00.000-08:00

Due to my startup, I have not had much time to do navigation research last year. I think I have been thinking on my few odd spare cycles is the idea of loosely connected grids, which kind of mixes waypoints and grids for the ultimate dynamic navigation. I had a little time during holidays and I thought I'd give it a spin.

A Grid

The whole process starts with voxelizing the level geometry much like in Recast and finding walkable surfaces. After that the area is converted to a 2D heighfield. This is done by doing a breath-first search starting from the center of the walkable surface. The voxelization is created around a point on walkable space, so this location is guaranteed to be walkable. This initial step finds contiguous walkable area that can be stored in 2D grid.

The property I tried to improve in the voxelization phase compared to Recast is the bounds. In Recast each tile requires to voxelize a column which cuts through the whole world vertically. This makes the runtime for the voxelization really unpredictable. In this version the grid voxelization bounds are always the same, which makes the whole process more predictable in terms of max memory and processing.

Automatic Exploration

As you can see from the image, the voxelization bounds are a bit larger than the actual grid. The larger area is used for two purposes. Firstly, it allows to counter for the obstacle expansion like in Recast, and secondly, it allows to calculate which neighbor cells in the 2D grid will lead to unexplored space. The dark outlines in the grid shows cells whose neighbor cells lead to unexplored space, I call these border cells.

These border cells are used to find few good locations for new grids. The process for find new grid locations starts by sorting all the border cells so that the nearest cell to the center is first. Each of these seed cells are visited in turn and if the location is not occupied yet, a new grid location is stored, and a perimeter around the grid location is marked as occupied. I use breath-first flood fill for this. A perimeter up gridSize/2 distance is marked as occupied. The yellow ticks in the above image mark these locations.

In addition to the flood fill, overlap of neighbor grids is used to filter new grid location generation.

The whole exploration process starts from one grid and it's potential new grid locations expanding until the whole connected walkable surface is covered. That is, because the neighbor overlap is taken into account, the process will some point just terminate, since there are no more new potential grid locations.

Finally connections between the grids are found. For each grid overlapping grids are found (the check is done at cell level), and closest 6 grids are stored as neighbors.

Path Planning

I have not yet implemented this phase, but this is how I think it should be done.

In order to move an agent in the world, first an A* search is done along the high-level graph which connects the grids. This path can be continuously replanned to take into account changes in the graph.

Movement within one grid is calculated using simple grid path planner. In order to move the agent from the current grid to the next grid, the goal is set to the nearest point which in the next grid. This should create similar behavior as described in Way Portals. It is quick to calculate the overlap between two grids, so it can be calculated on the fly. Once the agent is on the next grid, the next grid is set as current grid, and overlap is calculated and movement towards the next grid begins.

Future Improvements

There's a lot of work to be done to improve grid placement during the exploration phase. Currently there is too much of overlap, and this could be improved by voxelizing a bit larger area and using that extra area beyond the grid size to find the new grid locations. This extra padding could be also used to sample jump-links as per my Paris 2011 persentation.

Conclusion

Building efficient navigation structure for dynamic worlds is tricky. I think this technique has a lot of potential. For a long time I thought that grids are too memory heavy, but the real break through for me was when I realized that the grids can be kept compressed in the memory. This reduces the memory consumption down to the same level as navmeshes.

The technique combines small grids with waypoint graph. I think it has a lot of "roadmap" flavor to it. Here's some important properties of this navigation method:

Local: Pretty much every aspect of the technique is local: generation of each grid is local, traversing of each grid is local, updates to the grid are local too. This is important to keep the memory and processing in budget.
Hierarchical: In order to make path replanning fast, the navigation representation needs to be hierarchical. Replanning should do only small amount of work, and the rest of the system should iteratively find more precise solution.
Dynamic: When something changes in the game world, it needs to be reflected in the navigation graph too. Firstly, this technique allows quick updates to the navigation representation. Building individual pieces as well as connecting them together needs to be flexible and fast.

I think this is the way to implement path planning in 2012!

Download prototype and code (OS X):

navtest.zip

Path Replanning

2011-10-23T04:24:00.000-07:00

I've been picking on path replanning again. It is interestingly annoying problem. I have currently settled on following idea to make it somewhat manageable.

Prerequisite
In ever dynamic game world, the path finding and path following becomes statistic. The changes are that most of the time your request does not pan out the way they were requested. It is really important to have good failure recovery, both on movement system level as well as on behavior level. Plan for the worst, hope for the best.

Movement Request
At the core of the problem is movement request. Movement request tells the crowd/movement system that a higher level logic would like an agent to move to a specific location. This call happens asynchronously.

Path to Target
When the request is processed, the movement system will find the best path to the goal location. If something is blocking the path, partial path will be used and the caller is signaled about the result. From this point on, the system will do it's best to move the agent along this route to the best location that was just found.

Path Following
If a disturbance is found during the following, the movement system will do a small local search (same as the topology optimization) in order to fix the disturbance. If the disturbance cannot be solved, the system will signal that path is blocked and continue to move the agent up until to the valid location on the current path unless it is interrupted.

API
This could lead to following interface between the high level logic and the movement request.

struct MovementRequestCallback
{
 // Called after path query is processed.
 // (Path result accessible via ag->corridor)
 // Return true if path result is accepted.
 virtual bool result(Agent* ag) = 0;

 // Called when path is blocked and
 // cannot be fixed.
 // Return true if movement should be continued.
 virtual bool blocked(Agent* ag) = 0;

 // Called when the agent has reached
 // the end of the path trigger area.
 // Return true if movement should be continued.
 virtual bool done(Agent* ag) = 0; 
};

bool dtCrowd::requestMovement(int agent,
 const float* pos, const dtPolyRef ref,
 MovementRequestCallback* cb);

The 'result' callback allows the high level behavior to cancel movement in case unfavorable path rest is found (i.e. partial path), or it allows the behavior to set some internal state based on the path result.

The 'blocked' function allows the higher level logic to handle more costly replans. For example the higher level logic can try to move to a location 3 times until it gives up and tries something else, and it can even react to replays if necessary.

The 'done' function allows to inject extra logic on what to do when path is finished. For example a 'follow enemy' behavior may want to keep on following the goal even if it is reached, whilst 'move to cover' might do a state transition to some other behavior when the movement is done.

The general idea is to move as much of the state handling behavior out from the general code, and try to make the replan to be as cheap as possible. The downside is that the replan cannot react to big changes in the game world, but I argue that that is not necessary and should be handled with higher level logic anyway (i.e. the path can be come much longer).

What do you think?

Hierarchical Pathfinding in Detour

2011-08-01T08:03:00.000-07:00

Uwe Koch has written a great thesis about hierarchical pathfinding with navmeshes. He presents a generalized version of HPA* implemented in Detour. The short summary: 4-5 times faster than Detour's A*, and uses 10-20 times less memory (graph nodes).

Applying graph partitioning to hierarchical pathﬁnding in computer games

Path Replanning in DetourCrowd

2011-08-01T03:53:00.000-07:00

I just added first version of path replanning for DetourCrowd. If a polygon becomes invalid along the path, the path is replanned. Invalid polygon means that the polygon just disapperas (i.e. a tile is removed), or its' flags don't match with the filter anymore. In the above video, the red polygons have disabled flags and the agents react to the changes over time.

The way it works on practice is that before the current path is followed, we peek ahead to make sure the next N polygons are valid (I used 10 in the above example). If a any polygon during that sub path is invalid, a replan is issued from the furthest valid position along the path. if the current polygon becomes invalid, or of the target location becomes invalid, the agent will stop.

There are some things I don't like about this method. Firstly, it is quite wasteful in resources. Issues almost a full replan is pretty horrible. I tried some local repair operations, but they ended up being too very complicate and hard to time-slice.

Secondly, the replanning does not react if a new venue becomes available. The topology optimization pass will catch many of these cases, but if the goal was unaccessible when the replannig happened, the current implementation will not try to replan when it reaches the end of the path.

The end of the path could be flagged or some other tricks, but I think I might be missing a bit bigger picture here. What actually does a movement request mean?

Example of nasty case

Here's a simple example which emphasizes one of the problems with replanning. There is a house and it has a door which can be open or closed. The NPC does not have key (cannot open door), and wants to move inside the house. If the door is open, the NPC can walk in, that is path A in the picture. But what should be do if the door is closed?

From navmesh point of view, it looks like the graph is broken at the location of the door. The usual fall back in case no path is found is to return a path which leads to nearest position around the target. In our case that would be the path B in the picture.

It is really hard to tell the A* that there actually is a closed door and that the nearest accessibility to goal location is semantically the door. And this is when things start to slip from a technical issue to a simulation or story issue.

Imagine a case where the agent starts to move to the building, and before it gets there the door is closed. The story seen by the player could be something like this: The bad guard tried to capture the princess, but at the last moment the princess managed to close the door, and then the guard went to hide under the trees.

Game levels are full of cases like this. The AI has no notion of the trees, but when the AI walks under a tree and stands there, the player will give meaning to it.

There are more problems with that case too. For a moment imagine that we could replan the path every time the world changed. Now if we had a situation where the door would open and close every few seconds, the agent would get dead locked at the east side of the building since the solution would flicker between paths A and B.

These are just few examples which happen when you add replanning to your navigation system.

Solution

I think the proper solution to reacting to dynamic changes in the navigable surface is to treat the planned path the same way as any other plan in the AI system. That is, it is very likely to fail, and the plan will be considered as failed, if small adjustments to it cannot fix it. This makes assumptions about the request quite clear. It may not be the best solution, but I think it puts the decision at the right spot.

Request for comments! How do you handle partial paths and replanning?

Paris Game/AI Conference 2011 Slides and Demo

2011-07-03T03:36:00.000-07:00

The Paris Game/AI Conference is over and it was a blast! There was just so much interesting stuff in there that my head was just about to burst. I really like the shooter symposium where handful of studios gave microtalks (about 15mins each) on similar subjects followed by a panel discussion and Q&A. It was really inspiring to see different ways to solve similar problems.

My talk this year was about some work I did for Killzone3. I made a handful of tools for them to improve their AI level design workflow. In my talk I concentrated on how to automatically build cover annotation for the player. Killzone has this mechanic where the player can latch to a cover and slide along it. AI cover locations are discrete points are explained and were deducted from the player cover.

The cover locations are found using voxelization and tracing the contours of voxelized areas. Then the contours are sampled to see if they are close to a wall, and further the wall height is calculated and cover planes are build from that.

I also explained how this idea can be further expanded to automatically find jump-links and other non-locomotion navigation annotation.

Here's the link to the slides and demo (with source, sorry only OSX binaries):

AIGD11_MikkoMononen_AutoAnnotations.zip

I think the presentation did not go as well as last year. I tried to fix some problems I had last year, but ended up failing in some things I think nailed last year.

Firstly, last year I had two topics, and it seems I was only able to get the second topic through. So my idea for this year was to present one battle-proven practical idea and show how to vary it. Hopefully with enough details that people can implement it and maybe fond other uses for the technique too. I think the scope was good this year.

Secondly, even if I think my presentation last year was cool (and I got a lot of good feedback from it), I think it was a distraction. So this year I tried to simplify my slides to bare bones. The regular slides format does not work very well the way I like to explain things. I find it much easier to show different debug renderings in a demo and talk on top of that.

I horrible mistake I made this year was that I did not have enough time to practice the presentation out loud, in front of other people. I chopped some topics, since my practice runs were always over time. During the presentation I was super nervous because I did not have good confidence on time, and I ended up rushing through the slides super fast.

Lessons learned, I hope my next presentation will be much better :)

Temporary Obstacle Progress

2011-04-16T01:01:00.000-07:00

I've been super busy recently. Our startup just opened a public beta. I have managed to get some progress done on the temporary obstacle handling, though.

This is now probably the 4th rewrite of the system, so things are slowly being massaged in place (it usually takes 5 rewrites :). Adding and removing obstacles works again, and I've done some good progress on making the tile cache class better. Though, the API is still a bit in flux.

I'm currently testing with cylindrical obstacles, my plan is to support only extruded convex poly obstacles at first and add support for custom obstacles types in the long run.

I get quite consistent average of 0.1ms per layer build time, and about 10% compression ratio of the layer data when using 48x48 layers. The compressed layer grid data needed to rebuild any navmesh tile with obstacles in the scene pictured above takes 75 kB. The navmesh itself for that scene takes 72 kB.

I have few things left to do to finish this feature: 1) a custom pass before the mesh is being passed to navmesh builder (to handle flags), 2) handle off-mesh connections. Once that is done, I will start making releases again. I wonder if I should call the next release Recast & Detour 1.5 or 1.9?

Detour API Changes

2011-03-25T03:17:00.000-07:00

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

2011-03-20T12:02:00.000-07:00

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

2011-03-17T10:38:00.001-07:00

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

2011-03-12T11:38:00.000-08:00

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

2011-03-11T11:54:00.000-08:00

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

2011-03-11T03:16:00.001-08:00

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

2011-03-06T08:00:00.000-08:00

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

2011-03-06T05:07:00.001-08:00

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

2011-03-03T23:48:00.001-08:00

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.

Heightfield Layer Portals

2011-02-26T06:35:00.001-08:00

I worked today a bit on the layers again. I was trying to find the minimal data that needs to be stored. There were a couple of cases which required a bit more thinking.

For example should the layer contain that extra border or not? I decided that it should not. That required me to store the edges which may lead to a connected layer and it also means that the obstacle will need to be expanded by the agent radius, but that is something I was planning to do anyways.

It turned out to be a good choice to dig up the portals anyways. Now it is possible to calculate a hierarchical graph based on the portals only. The way the layer partitioning is done makes sure that the connections between two layers are always axis aligned. This makes things a lot easier and robust. As difference to the connections between navmesh tiles, with layers there can be a portal in the middle of a tile too. I will need to add support for this in Detour later.

I think I'll add a bit more info for the portals, for example which portals are connected to each other within a single layer.

Heightfield Layers Progress

2011-02-25T03:23:00.001-08:00

I have been working on the heightfield layers a bit more. As I've explained earlier, I'm trying to make the temporary obstacle processing much faster by decomposing the walkable area into 2D layers.

Then the temp obstacles will be rasterized onto those 2D areas and build into pieces of navmesh. The idea is to try to limit the changes of a temporary obstacle processing to as local area as possible and to speed up the generation process in general by making the input data simpler.

Each layer stores area type and 2D heighfield. The area types should compress really well with RLE, and it should be possible to compress the heighfield using a simple linear spline fitting. Add LZ compression on top of that and the aux data for generating new tiles should not be a huge burden anymore.

Interestingly, this layered heighfield data is also something that can be used to make 2.5D HPA* (the papers so far have used 2D data). If someone out there is up for the challenge, let me know and I'll help you to decipher the data Recast creates.

Iterating Cube Vertices, Edges and Faces

2011-02-22T04:32:00.000-08:00

This keeps haunting me. There must be an awesome way to arrange the data so that you can do a simple for loop and iterate over all cube vertices, edges and faces. I'm sort of after something you could use in matching cube like algorithms to fetch data from a sample grid without having to use lookup tables.

Vertices or sample offsets are easy:

    for (int i = 0; i < 8; ++i)
    {
        const int dx = i & 1;
        const int dy = (i>>1) & 1;
        const int dz = (i>>2) & 1;
        printf("%d: %d,%d,%d\n", i, dx,dy,dz);
    }

Assuming that you have 3 values per sample, one along each axis, the following code can be used to walk through all the valid edges:


    for (int i = 0; i < 12; ++i)
    {
        const int ax = (i >> 2) & 3;
        const int as = (4-ax) >> 2;
        const int bs = (5-ax) >> 2;
        const int v = ((i&1) << as) | ((i&2) << bs);
        printf("va=%d vb=%d  dir=%c\n", v, v|(1<<ax), "XYZ"[ax]);
    }

But... I'm not satisfied, there must be a cleaner way.

I once figured out how to procedurally draw a cube with just one for loop, but I cannot remember how to do it anymore, IIRC it used rotating sequence of XYZ, ZXY, YZX somehow, much like how you calculate cross products.

Very Temporary Obstacle Avoidance pt. 2

2011-02-13T10:48:00.000-08:00

I exposed my previous attempt at local obstacle avoidance to some more challenging situations and oh boy did it explode! For example the above shows really complicated case, which looks really innocent. There are a couple of problematic cases.

Firstly, the obstacles that reach to the sides are problematic to handle. The sides needs to classified regarding the goal direction (blue) but they can reach back to over 180 degrees in certain cases. I had to make a lot of special case code to make sure to detect when right is still right even if it is on left side. Yeah!

The second problem case is how to handle the terminator nodes (those red dots, which indicate that an obstacle touches a wall). Initially I thought just to use the line to goal to split detect if a terminator is left or right. It worked well for many of my tests, but there are cases like in the above video, where the terminator changes sides!

So anyhow, hours of hacks and tricks later, I thought I'd give up a little.

&amp;lt;/iframe&amp;lt;br&amp;gt;

Few days later, I thought why not try the old local grid pathfinder I made some time ago. I took a well tested rasterizer, changed it to support convex polygon and in no time I had working prototype of local obstacle avoidance in DetourCrowd.

The code is pretty simple to understand, it should be pretty fast too. I did not test the impact yet, but my previous tests indicate that it is fast.

The local pathfinder operates on the yellow area you can see in the video. If the blocking obstacle is larger than that, path cannot be found. The navmesh and the obstacles are updated every now and then, I could potentially use lower update rate too.

There a couple of problems still left to be solved. Firstly, the currently is no reliable way to detect that the agent is stuck. Secondly, in some cases the local pathfinder finds a bit different route, which leads to flicker.

We'll see how this all works out. I hope to speed up the navmesh temp obstacle baking a little. It is still the best choice. I think the local grid path planner could be usable for simpler games or those who cannot spend the extra memory required by the tile cache.

Very Temporary Obstacle Avoidance

2011-02-12T01:18:00.000-08:00

In the rush of trying to make everything perfect, it is sometimes hard to remember that a simpler solution could work too. This ties to my efforts to handle temporary obstacles.

If you want a rock solid way of handling temporary obstacles, there is no other way than to bake them into your navigation graph. There is just no way around it.

But at the same time there are huge number of cases, where you just would like to sprinkle few crates and barrels here and there for the player to shoot at, and will just break your navigation.

Purely local obstacle avoidance cannot handle them (or you are really lucky, if it does!). Local avoidance gets stuck in local minima (i.e. U-shaped cluster of obstacles), or platos (i.e. row of obstacles).

There is range of algorithms that fit somewhere in between local avoidance and global path planning. Which will solve the case of some temporary obstacles here and there, but will break of the obstacles for too complicated shapes.

Avoiding Temporary Obstacles Locally

One potential solution is to use small grid around the NPC to find around the obstacles. I have experimented with this earlier and it works really well. Another solution is to cluster the obstacles to for larger obstacles and use their silhouettes to find path around them.

That silhouette based obstacle avoidance is also discussed in an article in Game Programming Gems 3 called "A Fast Approach to Navigation Meshes" by Stephen White and Christopher Christensen. It is one of my all time favorite articles. I must have read it billion times.

I have tried to improve the algorithm few times in the past, but never quite got it right. I was working on a recent request last week and the idea popped up again, and I thought I'd give it a another go.

Basic Method

The basic process works so that you have a certain segment goal in the world where you would like to move to. First you check that if there is something blocking the way. In practice it means finding intersection between the segment from agents current location to the next sub-goal (i.e. next corner on the path) and all the temporary obstacles near by.

If something is blocking the way, we find tangent of the obstacle, and choose one side to steer around the obstacle. The side is selected based on which detour is shorter. The distance is approximated by a path from the start point, via the tangent point, to the goal location.

The first tricky problem with the method is how to handle multiple obstacles. Naively just visitin all the obstacles and finding a furthest tangents, will lead poor behavior when there is passages through the obstacles.

Obstacle Clusters

One solution to this is to first cluster all the overlapping obstacles. Then when you hit one obstacle in a cluster, you simply find the furthest tangents of all the obstacles in the cluster.

Sometimes this leads to a case where the newly chosen path will be still blocked. The solution is to check if there is some obstacles blocking the path to the new target, and iterate until the path is collision free.

Iterative algorithms are always tricky in realtime games and simulations. The goo things about this method is that just one iteration will give you a collision free solution. If the new path will lead to collision with another obstacle, that collision will eventually be the first hit and it will be corrected. The result is ugly, but it'll work. In practice this means that you can limit the iterations to 2-4 and it will handle most of the cases with gracefully!

Dealing with Obstacles Touching Walls

The next problem to solve is how to handle cases where one side of the obstacle touches navigation mesh boundary wall.

The solution I have used is to add special obstacles at the navmesh boundary, I call terminator nodes. When a terminator node falls on either side of the silhouette that side is marked as blocked and that is prohibited to be selected. If there is terminator node on both sides, it means that the path is blocked. This is really important feature of this method. It is not perfect, but it signals when it does not know that answer!

It Will Break

You should be also aware that using this method will eventually lead to situations where the path is blocked and the pathfinder cannot help you since it does not know about the blocker. You have to deal with it.

Your imagination is the limit how to handle such cases. You could for example just teleport the NPC to the other side of the obstacle, or the NPC could jump or climb over the obstacle using animation, the NPC could try to kick the blocking obstacle, shoot it, or you could detect that newly added obstacle creates a blocking wall and just break obstacles in the cluster until it is safe again.

That is, you need to have some kind of game mechanic to either break obstacles or skip them. One thing you should not do is to just disable the obstacle, since it can and will lead the agent to be inside the obstacle for long time.

Closing Words

There are quite a few more tricky details in the process I did not cover. I hope to polish those ideas a bit more and explain them at later stage. I think the method should be applicable to convex polygon obstacles too, which would make it even more usable. I have to try that out.

I think this method could be interesting choice for those who wish to add few obstacles here and there and whose game design can allow some game logic to pass through the obstacles when they block the NPCs path.

Implementing Undo the Simple Way

2011-02-02T00:34:00.000-08:00

Over the years I have implemented all kinds of undos for the editors and tools I have made. I have tried all kinds of ways, ranging from storing delta information to abstract command class that can undo redo itself. There is one kind, though, that is by far my favorite:

class Document ()
{
   static int MAX_UNDO = 10;
   struct UndoState
   {
       String cmd;
       String path;
   };
   UndoState m_undoStack[MAX_UNDO];

   int m_undoHead = 0;    // Current state.
   int m_undoTip = 0;    // The highest state that is set.
}

// Adds undo state to the undo stack.
Document:: addUndoState(String cmd, String path)
{
   // This kills all the states after the current one
   m_undoTip = m_undoHead+1;
   // Buffer getting full, shift down.
   if (m_undoTip >= MAX_UNDO) {
       for (int i = 0; i < MAX_UNDO-1; ++i)
           m_undoStack[i] = m_undoStack[i+1];
       m_undoTip--;
   }
   // Store state
   m_undoHead = m_undoTip;
   m_undoStack[m_undoTip].cmd = cmd;
   m_undoStack[m_undoTip].path = path;
}

// Takes snapshot of the document.
Document::snapshot(String cmd)
{
   String path = getTempFileName();
   ZipWriter zip;
   saveState(&zip);
   zip.save(path);
   addUndoState(cmd, path);
}

// Returns true if can undo.
Document::canUndo()
{
   return m_undoHead > 0;
}

// Returns true if can redo.
Document::canRedo()
{
   return m_undoHead < m_undoTip;
}

// Reverts to previous state of the document.
Document::undo()
{
   if (!canUndo()) return;
   m_undoHead--;

   ZipReader zip;
   zip.load(m_undoStack[m_undoHead].path);
   loadState(&zip);
}

// Advances to next state of the document.
Document::redo()
{
   if (!canRedo()) return;
   m_undoHead++;

   ZipReader zip;
   zip.load(m_undoStack[m_undoHead].path);
   loadState(&zip);
}

// Saves document state.
Document::saveState(Writer* out)
{
   // Save document state
   ...
}

// Loads document state.
Document::loadState(Reader* in)
{
   // Load document state
   ...
}

Counting the Sheep

2011-01-30T10:05:00.000-08:00

I had little time today, so I implemented off-mesh link handling for DetourCrowd. Yet another layer of state handling. The logic to detect and change state is not too complicated. I was mainly trying to see how to fit the link animation processing in the system. Not too much on how looks for now.

It looks like I might be able to make the system so that all custom handlers for steering and off-mesh connection handling will be just one (virtual) function call which handles all the agents. Something like:

void updateSteering(dtCrowdAgent** agents, const int nagents, const float dt);

DetourCrowd will just make sure the call happens in right order and the user can then do the update in anyway he feels necessary. Which brings me to a question to the readers of this blog:

How do you mix and match locomotion and other navigation animations?

For example, an agent is running and then jumps over a fence, and then keeps on running. I'm especially interested in what kind of logic might be used to trigger the change from running to jumping, if there is some kind of transition phase, etc. I know from the past that that is one nasty topic. I could really use some feedback on this. Good implementations, failed attempts, something that barely works, I want to hear it all :)

Another hard topic is how to manage potential queueing to an off-mesh link that becomes choke point. Or how to evenly distribute agents to multiple jump-links. Should the links be locked so that only one NPC can use it at time, or should there be invisible colliders at each end of the jump-link so other would avoid the location even more.

Some of those problems were touched by this paper: Situation Agents: Agent-based Externalized Steering Logic. I hope to have some time to try some of the ideas out.

DetourCrowd

2011-01-29T07:32:00.000-08:00

I finally managed to clean up the CrowdManager code and put it in proper place, yay!

The code is now located in DetourCrowd folder. My idea is to keep Detour a clean low level library and build DetourCrowd on top of that. While is was organizing things, I also moved the velocity planning code to DetourCrowd folder.

The crowd manager now allocates its' own dtNavMeshQuery, so there is no need to pass one to all the update functions anymore.

I also implemented timesliced pathfinder. The slicing is controlled using a constant called MAX_ITERS_PER_UPDATE. You can probably crank it up to 500 or so on real games. Try different values and see how it affects the performance graph (i.e. should not peek too much). I have currently set it very low for fuzz testing.

There are still some things missing:

Off-mesh link handling
Better handling of navmesh changes (i.e. how paths respond to temporary obstacles)
Off-mesh links with custom callbacks
Better handling of magic constants
Serialization
Custom movement styles

I will work on the items roughly in that order. I have a couple of other big things queued up for this spring, so no guarantees when things will be implemented.

Any feedback on the change or the crowd manager in general are welcome!

(Sorry again Windows peeps, I will try to find a PC to fix the VC project.)

2D Grids for the Win!

2011-01-24T22:57:00.000-08:00

The process of optimizing something from 10 mins to 1 second is quite different exercise than optimising something from 10 ms to 1 ms. I'm stumble upon this recently in my effort to make the temporary obstacle fast and scalable.

Once upon a time I used to work in a company where AI navigation data generation took easily 15-30 mins per level. I thought that it was waste of designers time, so I wanted to fix it. I ended up with a solution which can handle changes incrementally, so that instead of wasting 15 mins of designers time to tweak a simple scenario would become 150 ms instead.

Problems with 2.5D Heighfields

There were a lot of interesting lesson learned from building Recast. One of them was how to store 2.5D heighfields. I ended up using two different data structures, one which is fast to modify, and another which is has fast neighbour lookup.

Both of the heighfield representations has one annoying thing when trying to reach sub 10 ms performance. They need some extra data to describe the structure of the data. This additional data complicates random access and takes up additional memory. Something like 2D grid would be quite ideal data structure to work with.

Another challenge for sub 10 ms operation is amount of data. In Recast and Detour, the tiles span from the bottom of the world to the top of the world. Many games are usually quite flat–1 to 4 floors on top of each other–but it is still huge variable cost when you process different tiles. Firstly, updates unpredictable amount of time, and secondly the process uses unpredictable amount of memory. Ideally we should know the upper bound of the memory usage before hand. Even if it means a bit bloated memory usage for the general case.

Finally, the column data structure partitions the work unequally. Adding temporary obstacle at the top of a building requires to update the navmesh of the whole building, there might have been many floors which does not require any updates at all.

Side Tracks

I blogged earlier about an idea to create small navigation grids and connect them loosely like waypoints. I did some prototypes and I have done a lot of thinking on how to make it work, but so far it has been failure. But the idea spawned some other ideas.

My plan was to use simple 2D heighfields per grid to describe the world, and to use compressed cache of these tiles to describe the whole world. I liked the loose arrangement too, but I could never quite figure out how to make path following work very well in that context.

Anyways, at the same time I was working on temporary obstacles for Recast & Detour too. And I implemented a tile cache, which basically stores that layered heightfield in compressed form and uses it to kickstart a navmesh generation process. In case you just wanted to mark some areas impassable, that method speeds up the tile generation process my almost a magnitude.

I got it to a point where things are fast, but because of the layer structure, the speed is unpredictable. Adding ideas from one project to another I got a simple stupid idea: what if I partition the layered heighfield to stack of 2D heighfield layers?

2D Data for the Win

I did try that idea long time ago, but it did not work, it was slow and took too much memory. But few things has changed since. Firstly, now the process can use tiles, which means that the 2D heightfields are something like 64x64, not 1056x1522 per layer.

Secondly, the monotone region partitioning makes finding non-overlapping regions really fast. It also makes sure that the transitions between two neighbour layers will be axis aligned. Previously I had a lot of problems trying to match non-axis aligned edges. Currently Detour uses axis-aligned edges to create connections between tiles.

What this means in practice is that I have now a method that transforms a layered 2.5D heighfield into a separate layers of 2D heightfields.

The process starts by finding monotone regions in the 2.5D heighfield. During the process I also calculate which regions are on top of each other, as well as which regions are next to each other. In the next phase, I start from the first region, and flood fill to neighbours, and if they do not overlap the correctly flooded region, they will be assimilar to it. This process is repeated to all regions until they are all marked with unique label. It is a bit like depth peeling, but it considers connectivity.

Since 2D data does not need any additional structure to describe it, it is much simpler to compress it too. For example a simple lossy spline fitting could be use to store the height, and simple RLE should handle are types. Add some cheap LZ compression on top of that, and it should be a lot of win.

Going Forward

My plan is to change the rest of the navmesh generation process so that it can operate on 2D layers. It allows me to take certain shortcuts and make things faster. I hope to make the whole process from 2D heightfield to navmesh to only use stack allocator to make it more usable at runtim. In addition to that I will allow Detour to handle layers too. The current process of building a whole column worth of navmesh will remain intact.

The end result I hope to reach is fast preprocess step which partitions the data to a tile cache, were each tile contains 2D data only. This should allow faster generation, more local changes and better compression of the tiles.

All in all that should allow really fast and predictable process of temporary obstacles.

Explainability

2011-01-24T21:38:00.000-08:00

I have been doing a lot of UI design recently at work. We just got first bunch of feedback from the users and as you can imagine they had a lot of trouble trying to navigate through the app. This made me thnk about.

I had a recent discussion with a good friend of mine and he told me that most of his UX work nowadays is about copy. At that point in time my biggest concern was to make our UI slick and lean while he was pondering how to communicate something through words. That slick and lean was the version that went to user testing and did not receive too much praise.

As I worked further on my layout I noticed interesting thing. We did not have explainable names for all the stuff in UI. The concepts were there, but they were not exposed. Sometimes I had omitted text to make the layout look better, or crammed things together to make it more compact.

We had put a lot of effort to make the app discoverable. That is, there is one layer in the UI design which allows you to explore and test all the features of the app one at a time. There is one layer, which allows really quick access to all these features via shortcuts and modifier keys. It looks pleasing to the eye too. To make the entry to the app even smoother and the structure more understandable, we added another layer of design: explainability.

Everything we have put in the UI has name and relation. Pretty much every feature and its' relation to others can be explained with just one paragraph of text (as a matter of fact, that is often my litmus test). So the UI extends outside the app too. Explainability implies literate, but not litter. Tufte's rule of adding as much information as possible with as little ink as possible still applies.

Sounds stupidly obvious, but it took me good 15 years to understand it!

My Recent Failures in Polygon Clipping

2011-01-19T23:48:00.000-08:00

I have been prototyping some prerequisites for cookie cutter temporary obstacles recently. And the short story is that it won't happen. The longer story is, I had a couple of different ideas how I would implement the clipping.

First Attempt

I always wanted to try out the dynamic navmesh subdivide algorithm from AGPW4. The same algorithm is also used in FEAR SDK. The idea is that to subtract polygon A from polygon B, you split polygon A with each edge of poly B. You know, like BSP.

The good thing is that the algorithm is really simple to implement and the resulting polygons are also convex. The bad thing is that it creates a lot of extra vertices and polygons. After few overlapping intersections you have left nothing but magic fairy dust. And not the good kind.

I did a couple of test to remove the extra vertices. Some test were successful but in overall the whole effort just turned into a giant epsilon fest. That is not the kind of code I would like to support and maintain.

So the lesson was that if you choose to use the BSP-like algorithm to cut your polygons, make sure your code can handle T-junctions. That way you can always track which edges to connect without any additional epsilon magic.

Second Attempt

I think I might have gotten the previous attempt to work to some degree with a lot of sweat. But the fact that it would create huge amounts of polygons really turned me away from it. I like how grid based methods make it easy to handle obstacles. So my second attempt was to use that.

The idea was that I would create a grid which covers a whole polygon plus some padding and rasterize the obstacles into that grid. Then I would use monotone partitioning to create polygons from that raster data. Finally I would clip those polygons against the edges of the original polygon.

While this was kinda silly idea, I think it was worth pursuing. I gave me a lot of ideas, which I will discuss later. Anyways. This idea suffers from the extra vertex mania.

Third Attempt

Despite a lot of failing, I was not done yet! As my last resort I tried to use a proper intersection and tessellation library. While I was able to solve the case for one polygon with multiple obstacles, the performance was not too tempting. While the GLU tesselator is robust and scales pretty well, things are different when you want to do things that are below 1ms.

That would have still left me with all kinds of epsilon tests to handle the (necessary) new vertices added at the polygon edges. Vertex welding is not particularly complicated thing to do, but it can and will create degenerate and flipped geometry in odd cases. I don't like odd cases.

While my attempts to create cookie cutter obstacles has failed, the process has sprout some great ideas to pursue. The one big lesson I learned during this research so far has been that it is really interesting to write code which has known upper bound, let it be memory usage or processing requirements. And I think that is the key to make something dynamic happen quickly–hard, known, bite sized limits in computation and memory.

Time-sliced Temporary Obstacle Handling

2011-01-18T01:59:00.000-08:00

While I was testing the temp obstacle handling, I noticed that some locations would take quite a bit more time to process than others. For example in the level that is shown in the video above, the rebuild times would range from 1 ms to 15 ms depending on how many tiles the obstacle would affect and how many layers there were in that particular location. The number of obstacle affect the build time too. The added performance cost is pretty linear to the number of obstacles (and their size). In my tests each obstacle takes about 0.05-0.1ms to process.

To fight the variance I implemented a time-sliced version of the generation process. In the above video, the temporary obstacles are updated incrementally so that on each update the process consumes 1 ms. The code will find its way to the SVN later this week.

First Iteration of Temporary Obstacles Checked In

2011-01-14T03:00:00.000-08:00

The very first iteration of temporary obstacle handling using compressed lean heighfields just got checked in (R258). Unfortunately, it is not yet "just plug it in" solution, but merely some simple modifications and a sample implementation how it can be implemented using the toolkit.

I ended up calling the minimal representation to create a compact heighfield "lean heighfield". I'm not sure if it is particularly good name, but at least it is more distinct than "compressible heighfield".

If you were previously regenerating tiles using Recast at runtime, this modification allows you to save and compress the voxelized results and speed up the tile rebuilding almost by an order of magnitude (it usually varies between 5-10 times faster).

I will keep on prototyping some more to see if I can support modifying the Detour meshes directly.

In the process I also changed the navmesh builder, so that the detail mesh is now optional. Detail mesh is important if you have large tiles or one big navmesh, or if you require some approximation of the height at runtime. When using small tiles–which is good practice when you are likely to change them alot at runtime–the detail mesh is not always necessary. Not requiring to the detail mesh speeds up the generation process and requires less memory.

[EDIT] As usual, the Visual Studio project is lagging behind. I will try to allocate a slot on some win machine to put it up to date.

Temporary Obstacle Progress

2011-01-11T17:12:00.001-08:00

I managed to make some progress with the temporary obstacle handling. Most of the required pieces are now in place, next up is bunch of massaging to make it great.

So the stuff I have working now is a preprocess step which rasterizes the tiles, creates a minimal representation of the heightfield and then "zips" it. These data chunks are stored in tile cache. Upon request tile cache will create a piece of navmesh for you which includes all the temporary obstacles too.

I use tile size of 48x48 in the video. It takes about 2 ms to update one tile. So in worst case adding one obstacle takes 8 ms. Interestingly the conversion from the minimal representation to compact heightfield takes about 25% of the time, and generating detail mesh takes another 25% of the time.

For those in dire need for the extra nanoseconds, I think I'll provide dummy detail mesh generation process which just triangulates the polygons instead of trying to add more detail. Or maybe even support that at runtime like in the old days.

Apart from the few offenders, each Recast call takes very little time, so it is possible to timeslice the generation.

Compressed Heighfields

2011-01-09T23:27:00.001-08:00

One of the items on my TODO list for 2011 is support for temporary obstacles. I posted earlier about the possibility to compress the heighfield and use part of the Recast process to regenerate tiles much faster.

I have been prototyping heighfield data compression recently. The above picture shows the test scene I have been using. It has both simple plane like surfaces as well as building with many levels.

The compression process starts by stripping down and packing the heighfield data. I store elevation, free space and area type for each walkable span. In addition to that the ground grid stores number of layers per column. See my previous post on the topic for a bit more details.

That is the minimum amount of data to reproduce a compact heighfield for a particular tile. The minimal heighfield data for the test scene takes 713kB. This is more than the 512kB I reported earlier. The reason is that each tile also contains border, which is required in order to make the tiles match ar borders.

The compressed data for the whole scene takes 82kB. This is the amount of data that needs to kept in memory to regenerate any tile in the scene. It is quite a bit more than the 32kB I reported earlier. The difference between the tests is that the old data was compressed as one huge chunk using zip and my recent prototype compresses each tile individually and uses libLZF which does not compress so well, but it is a lot faster.

For a comparison, the actual navmesh for the test scene takes 98kB. I will provide some timings as I get further with the implementation.

Changes in the Build Process

Currently the build process for a tiled navmesh goes like this:

for each tile

- rasterize triangles

- find walkable cells

- mark areas

- build regions

- build contours

- build poly mesh

- build detail mesh

- store navmesh

With compressed heighfield the process changes to follows:

Preprocess

for each tile

- rasterize static triangles

- find walkable cells

- mark areas

- store compressed heighfield

At Run Time

for a changed tile

- uncompressed heighfield

- mark obstacles

- build regions

- build contours

- build poly mesh

- build detail mesh

- store navmesh

Triangle voxelization is usually dominating facter when generating a tile. For example it takes 71.5% of the time to generate the highlighted tile in the test scene.

The perfectionist in me still would like to find a way to use just the Detour data to adjust the navmesh for temporary obstacles, but I think this test has been worth the effort so far.

Loosely Ordered Mega Navigation Grids

2011-01-06T05:10:00.000-08:00

I got this stupid idea while reading AiGameDev article on fixed point math used in PathEngine. A light lit up above my head when I read about the section related to streaming. PathEngine does not try to match the navigation representation at neighbor tile borders, but instead the navigation tiles overlap and the agent switches to another mesh when it is over it. At first it feels odd, but it is kinda awesome too.

That is sort of my idea. What about a navigation representation which is based on overlapping 2D representation of the space? Sort of like HPA*, but you don't have square tiles laid out on a grid, but the tiles could be place anywhere in 3D and would have height data too? That way you could have full 3D navigation–overhangs and all that jazz–but the dynamic awesomeness of a 2D grid!

So I thought, I'd test it out. In the above screenshot there is the very first step. I initially had the idea to use cubemap, but the irregular sample distribution on ground made a lot of things really complicated.

What you see on the screenshot is 32x32 voxelized section of the scene. The blue area represents 2D heighfield placed at the location of the red cross. Notice how there is black patch under the bridge, since the bridge is visited first.

My idea is to use a graph at the higher level to find a path through the tiles. And to use my earlier attempt at local grid planner to find the path between waypoints. The overal design fits well into the Navigation Loop thinking too.

I see all kinds of interesting opportunities for this method, such as using different accuracies for different waypoint patches, dynamically creating new patches as the scene changes, etc.

The main idea behind the design of this idea was how to handle changes in the navigation data at runtime, without sacrificing any of the properties of navmeshes.

The amount of data is of course one concern. Heightfield and some flags probably take around 1kB per patch, but the great thing is that you most likely need to store very few patches, just the ones around the agents and use cache to manage them, sort of mega-texture for navigation grids.

Happy Holidays!

2010-12-24T03:41:00.001-08:00

Merry Merry and Happy Happy!

Thank you for the past year, and good luck for the following one! Here's a little game to fill the idle moments during the holidays:

Mottainai-1.0_OSX.zip (Mac only, sorry!)

See you next year!

Computational Geometry Sucks!

2010-12-10T08:19:00.001-08:00

Computational Geometry is hard. Most of the examples out there are crap and the good stuff is without exception hard to understand.

You can usually whip up a 100 liner to solve a problems, if your input is cloud of random points. This is what pretty much all the Java code out there does, but the input data for your game is not a random point cloud!

I hate computation geometry, but yet it is so important! It drives me crazy.

I was recently looking for a robust 3D convex hull algorithm which would work for a couple of hundred points in realtime. That is, something sub 2.0 ms on a 2GHz Core Duo.

I wrote a couple of solutions myself, including one which was O(n^4) and surprisingly did not scale beyond 25 points. Finally I was hinted towards this patch for Bullet Physics, and it turned out to be a real gem!

It is fast, scales well (it's O(n log h)), and is robust too. My litmus test is a grid of 4x4x4 points. It passes that and even handles coplanar input. Pretty much all the Java code out there fails on that input.

So I took that patch, regexp'd it, copy pasted some Bullet code, deleted stuff I did not need, shuffled things around a bit, and made it output triangles and I'm finally a happy man!

Style vs. Technique

2010-12-01T01:11:00.000-08:00

This is a very dear topic to me, I just wish I was able to output my through about it efficiently.

I recently posted a link to a paper and video in twitter:

Situation Agents: Agent-based Externalized Steering Logic
http://www.cs.ucla.edu/~pfal/Petros_Faloutsos/Crowd_Simulation.html
http://www.cs.ucla.edu/~mubbasir/pdfs/situation-agents-paper.pdf

I got a reply that the results are not very realistic. And it is very true, especially the formation examples look quite unrealistic indeed.

But compared to what? Some generic situation in real-life? Our generic assumption about how things should behave? Maybe you were in a similar situation yesterday and you comparing the video to that.

There was a one important lesson I learned from art school: when you critique someone's work, you better be able to explain your point of view. You have to define your point of view, your artistic vision and potentially references to existing methods.

In order to have a good critique over the above example both the presenter as well as the commenter needs to point out their artistic point of view. Otherwise the discussion is pointless.

More scientific way to justify your point of view is to hypothesize, collect data, build a model, and compare your method against it. This approach is well executed in the following research:

A Synthetic-Vision-Based Steering Approach for Crowd Simulation
http://www.irisa.fr/bunraku/GENS/jpettre/

When the model is tuned based on the input data, the output looks and should look much like the data that was used to tune it.

My critique to the above method is that can it reproduce different kind of styles? For example if two actors would act out exaggerated situation where and a nerd and a bully avoid each other, could the method capture that style?

In my humble opinion in order to critique a technique you either have to have an artistic point of view (one that you can also explain to others) or if you compare things to realism, you better have good data! Otherwise the discussion will be just bike shedding.

Seeing potential of a method is not easy either. Ken Perlin showed an interesting picture pair during talk at Paris AI Conference this year. In one picture there was a raytraced marble sphere, picked from his original noise paper, on other picture there was a shot from a movie which had beautifully rendered stormy ocean, which was build using his noise function.

Examples are generic and try to show off the technicalities of the technique, but it takes an artistic vision to turn a technique into something worth watching.

Detour Return Codes Take 2

2010-11-26T04:46:00.000-08:00

I just update the Detour status labels based on recent feedback. The code is in in R255. The return value is now bitfield instead of a single enum. This to pass both error messages as well as few bits of information about the quality of the result.

The high level statuses are DT_FAILURE, DT_SUCCESS, and DT_IN_PROGRESS. The rest of the bits are used to describe mode detail about the status. To test if a status is one of the above, you should use the helper functions dtStatusSucceed(), dtStatusFailed() or dtStatusInProgress().

Example:

dtStatus status = m_navQuery->init(m_navMesh, 2048);
if (dtStatusFailed(status))
 return false;

In many cases of success and failure, you can get one or more bits of extra information why things failed or if the quality of result is degraded. The detail flags are:

DT_WRONG_MAGIC: the input data you passed had wrong magic number. In practice this means that you are trying deed bad data to Detour. Failure.
DT_WRONG_VERSION: the input data is in different version than Detour expects. Failure.
DT_OUT_OF_MEMORY: the operation could not allocate enough memory. Currently this applies to init methods. Failure.
DT_INVALID_PARAM: one or more of the input parameters had invalid values. Usually this means that you passed a poly ref which is not valid. Failure.
DT_BUFFER_TOO_SMALL: the buffer to store the result was too small. Success.
DT_OUT_OF_NODES: query ran our of nodes during search. If this happens often, you should increase maxNodes. Success.
DT_PARTIAL_RESULT: query did not reach the end location, returning best guess. Success.

In case a function call fails, it usually returns only one flag. If a function call succeeds, it may return multiple flags indicating the result quality. The flag DT_BUFFER_TOO_SMALL is also use store/restore tile state and in that case it is returned to describe why the function call failed.

Some more examples:

dtStatus status = m_navQuery->init(m_navMesh, 2048);
if (dtStatusFailed(status))
{
 if (dtStatusDetail(status, DT_OUT_OF_MEMORY))
  printf("Out of memory initializing navmesh query.\n");
 return false;
}

dtStatus status = m_navQuery->findPath(sref, eref, spos, epos, filter, polys, &npolys, MAX_POLYS);
if (dtStatusSucceed(status))
{
 if (dtStatusDetail(status, DT_BUFFER_TOO_SMALL))
  // The path result is longer than MAX_POLYS.
 if (dtStatusDetail(status, DT_PARTIAL_RESULT))
  // Could not reach end location, the path leads to a location near the end point.
}

Sundries - Visual Scripting

2010-11-12T00:22:00.000-08:00

I found this old sketch of a visual language for AI behaviors while browsing through an old harddrive. I think it is from 2006 or 2007 or something. Few notes:

Concurrency: tasks (blue stuff) can be run at parallel and a certain point of a task (percentage of completion, distance to end of path, etc) can trigger another parallel task.
Variables: the usual flow diagrams break down when you have too many things to connect, solution? Use local variables!
Ordered: the connections have order. This was important lesson learned from countless hours of debugging Crysis flowgraphs.

The arrows at the top of the tasks are execution points. When triggered, the task starting at that location will start executing.

There was also a syntax to define how the next tasks would have been triggered. In the above examples the next task is always triggered when the previous on is finished. I had an idea to also have some kind of notation to require all tasks to be finished before the next one was carried on.

The orange boxes are variables. Grey boxes are functions. Some functions take variables as input (could be stacked ala werkkzeug).

I think that "patrol point is not valid" should have a trigger line coming to it from the same bundle where the patrol point selection and restart is triggered (that eval would be 2 and restart would be 3). The grey text in the patrol box should actually read "Patrol(StartPoint)".

The overall design was much inspired by werkkzeug and PD.

Path Corridor Topology Optimization in Action

2010-11-07T03:04:00.000-08:00

I just commited a change to the Crowd Manager which implements path corridor topology optimization (SVN R251).

In the above video, only the very first path is calculated using regular A* for all agents, after that the path end is adjusted by stretching the path corridor as I have explained earlier.

When the agents start to move, the path corridor is optimized as I explained in my previous blog post.

In the example the path topology optimization is done for only agent per update at most twice per second. Only 32 nodes are visited during the update. Search for optimizePathTopology in CrowdManager.cpp to see how it is implemented.

Feel free to try it our yourself!

Path Corridor Optimizations

2010-11-04T09:43:00.001-07:00

Path corridor consists of a current start location, end location and list of polygons connecting the two. This is the structure which used at runtime to navigate from the current location to the end location. We can use A* or his bearded friends to find this path corridor in the first place.

When the agent wants to move, we first calculate the furthest visible corner along the corridor and move towards that point. As the agent moves we adjust the path corridor. If the agent moves from the current first polygon to the next on the corridor, the current first polygon is dropped and the corridor's length shrinks.

The same idea can be used to adjust the corridor even if the agent does not move towards the goal (i.e. is being pushed around by other agents). The corridor adjusts based on how the agent moves. Even despite the detours, we can always quickly query the next visible corner using the funnel algorithm and try to move towards it. Eventually we will reach the end location.

This is flexible and fast way to move the agent towards the end location. But there is room for improvement. There are several cases where the shape of the corridor may lead to visually poor results. For example, if the agent is following a target or it needs avoid other agents too much, the path can get tangled up. Often there would be a trivially shorter path to the goal only if we could adjust just few polygons in the corridor.

This kind of problems can be solved using two kinds of optimization methods: visibility optimizations and topology optimizations.

Visibility Optimizations

The idea of visibility optimizations is to try to alter the beginning of the path corridor so that we could take more direct route towards the next corner. This problem usually only occurs if there are vertices in the navmesh which do not belong to a border. In Recast & Detour this happens if you use tiled navmeshes.

If the extra corners are not removed, sometimes it looks like the agent is trying to avoid invisible obstacles or sometimes they are just small odd kinks in the road.

One way to optimize the beginning of the path is to do a walkability raycast from the current location to the corner which comes after the next corner. That is, try to shortcut the next corner.

Detour walkability raycast returns the list of polygons it visited during the trace and that data can be used to patch the beginning of the path. Note that the raycast is not used to optimize the string pulled path, but the path corridor. This is really important difference.

The visibility optimizations should be done as often as possible, potentially every update. If the optimization is not done often enough, you will get visible jerks in the agent motion. To keep the computation in bounds, you should limit the ray distance (something like 20-30 m is good range).

The walkability raycast works ok, but It would be interesting to try other methods too which might do better optimizations. One potential idea would be to treat the edges between the navmesh polygons as portals and use the well known portal visibility algorithm in 2D to try to optimize the path.

Topology Optimizations

If the agent follows a target, or if it is moving in a large crowd the topology of the path corridor can get tangled up, like in the above picture. The visibility optimization can only handle problems that are visible from the current location but there can be an obvious shortcut which needs a bit more reasoning.

One way to fix topology problems is replan the whole path, but this is very wasteful and the time it takes to complete an A* search is really unpredictable. At worst case when it cannot find the goal it will visit all your navigation polygons!

The topology problems that a human inspector would notice are usually quite local. Only if we could replan the first 20m of the path. Well, yes we can!

One way to efficiently implement path corridor topology optimization is to search towards the end locations using A*, but instead of doing the full search we limit the search to something like 30-50 nodes (step 1 in above picture). This makes sure that we can guarantee that the search returns in finite time.

When the search has been done, we start traversing the existing path corridor from the end (step 2 in above picture). As we move towards the start location, we check at every polygon if it was visited during the search. If that polygon was visited, we trace the graph back to the start and substitute the beginning of the corridor with the trace result.

Conclusion

There are two kinds of optimizations which can be used to optimize the path corridor. They make the visual appearance of the navigation more pleasing. Firstly, we can make sure that we try to aim as far as we can see by doing visibility optimization, and secondly we can periodically optimize the topology of the path so that the agent tries to move towards the goal without taking too obvious detour.

The intuition is that the visual optimization tries to optimize the very near term reactive plan, whilst the topology optimization tries to optimize the medium term plan. The reactive plan should be updated very often, but the mid term plan can be updated less frequently, say few times a second.

Detour API Change

2010-10-29T05:08:00.000-07:00

Heads up!

I changed the Detour API so that it always returns a status (success, failure and few others) instead of number of polygons on path, etc. When you sync to a version > R250, I suggest double checking the calls to Detour.

Many of the changes also changed the function signatures so you will get compiler errors and know where to changes stuff. Some functions such as init() can now have multiple failure cases si simply checking true/false will not result on correct behavior.

The biggest change was for the functions which previously returned number of results. Now the result count is passed as a parameter and the return value tells you if the operation succeed or failed. For example pathFind() changed from:

m_npolys = m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, MAX_POLYS);

to:

m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, &m_npolys, MAX_POLYS);

To ease the migration, I made the change so that result count is always initialized to 0 in the beginning of the call, so it is safe to use that as an indicator of success too.

Currently majority of the failure cases are reported when one of the input dtPolyRefs was null. There is only one succeed case, so it is good value to check for success.

If you have some ideas for more verbose error reporting or find bugs, let me know!

Following Moving Target

2010-10-29T00:49:00.001-07:00

One interesting sub-problem of navigation is following a moving target. This could be a group of ninjas following your warrior, a horde of blood thirsty zombies trying to eat you, limping band of pirates on their patrol route.

So how do you go about implementing a moving movement target? Fire off new path request every frame (too expensive! decision aliasing!)... every few frames (still too expensive! still aliasing!)... when the target moves (it moves all the time, bad optimization!)?

The right answer is that you adjust your path corridor.

The path corridor consists of start point and end point and the list of polygons from the start to the end. When we move our character, we adjust the beginning of the path corridor so that the previous definition holds after the character has moved. We can do the same for the end of the path too!

Take a look at the case pictured at the top of the post. The looting party of three follows the target. The dark polygons represent the path polygons of each agents path corridor. When the target is moved along the navmesh as indicated by the arrow, following will happen.

When the target point is moved, we keep track of the polygons we moved through. Then we "fuse" those polygons to the end of the current path corridor. The fusing process tries to find the shortest common path amongst the two. Sounds complicated, but it is really simple algorithm really.

And that's it! Now we have a new path corridor which describes the navigation from the agents current position to the position it tries to follow.

Detour Implementation

The code is in SVN R249. If you use the Move Target tool with shift+click it will use the target adjusting instead of pathfinding. Turn on Show Path from the debug draw options to see the effect.

The CrowdManager example supports both adjusting the current path corridor of an agent as well as keeping track of the changes that might happen whilst a movement request is still being processed.

Future Improvements

This method of following comes with it own set of cons too.

The method does not try to find the shortest path, it just tries to patch the current path with minimal effort. Depending on your application this may be good or bad.

If you have quit small tile size, this may lead to odd behavior in open fields. Even if there is direct line of movement to the goal, the path will take detour based on how the target moved. The open field case eventually would optimize itself. Since the path optimization distance is limited, the agent will move to "old" direction for some time before the optimizer kicks in.

Conclusion

Patching the path corridor is really efficient way to implement path following. It has some limitations, but they are quite negligible when the follow distance is quite small, like when following player quite closely or when following a formation point.

My recent work on path following has surfaced and interesting problem to solve, that is the path corridor optimization. When the world is constantly in motion–and in games it always is–the quality of the initial path is less and less important. I hope I will have more time in near future to figure out how to optimize the path corridor in certain uses cases.

If the above method sounds crappy and limited, it still does solve the case for moving target for a whole range of the use cases. And did I mention it is really fast?

RVO Sample Pattern

2010-10-19T00:20:00.000-07:00

I spent quite a lot of time last Friday on trying to fix some cases I had with ORCA and to implement line obstacles. I kept on running into cases which simply cannot be solved using it.

For example I could not solve the case in above picture. Regardless of my effort, I ended up having cases where the segments would block the movement completely. The ORCA planes would be aligned according to the dark edges and they would limit a convex region which is used to clamp the velocity. I think some of the problems might be due to the fact that the navmesh is offset by the agent radius.

I'm anxiously waiting for the next paper which improves ORCA. Until then, I'm sticking with the sampled approach. Which leads me to another thing I tried last week.

Improving Sampling

At the time when I was working on my first iteration of the adaptive sampling for RVOs Phil Carlisle's student Scott Bevin mailed me that he was using similar method in his thesis too.

One main difference between out methods were that I was using a regular grid as sampling pattern and he was using 8 samples on a circle aligned at the movement direction and subdivide towards the best sample. At the time I was too busy with my Paris presentation so I did not have any time to investigate it further.

I tried his method but it did not quite work in crowded situations. There simply was not enough initial samples to get good answers.

But the idea of aligning the sample grid helps a lot! I initially thought that it would cause a lot of problems because it might produce more feedback into the velocity control loop. I think I was wrong. The desired velocity usually is quite stable, so when the pattern is aligned towards it, I did not see any additional feedback effects.

As you might spot from the above picture, my implementation used two rings of 7 samples plus one sample at zero velocity. The inner circle's rotation is offset slightly to get better coverage. Since the samples are aligned towards the desired velocity there is always a sample exactly at the desired velocity too. This makes the overal control very smooth, the jaggies from the non-aligned method are gone.

Conclusion

In practice the new sampling pattern improved the movement through small corridors a lot. The hesitating movement is almost completely gone now. The agents do slow down quite a bit if they approach a choke point from an angle. From their point of view they are almost approaching a wall. Adding that extra sample at the zero velocity improved stopping a lot.

All in all, I'm pretty happy about the results now. Not perfect, but tolerable. I can now finally turn my attention into fixing the remainder code structure issues with the crowd code.

Crowd Manager Progress

2010-10-03T23:38:00.001-07:00

The Crowd Manager stuff is slowly coming together. I think I have some of the bottom layers figured out now (i.e. that PathCorridor class). Still heaps to work to do. I was lucky to be able to do few weeks full time work earlier this Autumn and got a lot of progress, but now I'm back to my freetime schedule so things progress quite a bit slower.

The way the Crowd Manager has evolved in the SVN is pretty much the way I usually massage my code. I start with something that just works. In my case it was the ugly but working prototype I made for my Navigation Loop presentation. First I ported that code almost one-to-one to use Detour. After that I have tried to refactor the hell out of it until I have seen the code from arranged from many points of view.

The point is to find the best structure of the code based on the constraints you have. Fully explore the depth based on each constraint. My major constraints have been speed, concurrency and reusability.

Speed was my first goal, which I pretty much reached. I have recently worked more on the concurrency and a lot more on trying to find good structure how to organize the code so that it is reusable.

I don't have much experience writing concurrent [1] code, so my approach has been to make all the hard work–like A*–asynchronous (PathQueue) and try to arrange the other code so that the work is done embarrassingly parallel (to make the transition from concurrent to parallel easier), to use read-only data, and try to reduce the sync points to as few as possible. Very much like the Nulstein stuff.

One of the most complicated things about writing toolkit or library code is how to organize the public API. I don't like huge monolithic systems which want to control all the updates themselves. They are simple to get something rolling quickly, but once you need to shuffle your own code around a bit, you start to get pretty horrible problems in update orders and what not. I'm big fan of Casey what it comes to API design, but I don't think I master that yet.

One of the hardest parts of arranging the code has been how to facilitate custom implementations of parallelizing the code, steering, collision avoidance and dynamic constraints. They are right there in the middle.

As with the rest of the RC&DT, the Crowd Manager will be again piece of usable example glue code, which uses the "real" public API. Ideally it should show you how the relation ship between different parts of the navigation loop, where to put the sync points, and which steps rely on previous ones. Also the sample will include some example implementation of steering and dynamic constraints.

The public API will be some classes which implement path corridor management, local avoidance and such. The sample code should help you to get things up and running quickly, but I try to make the sample code simple, light and rough enough that you will not have problem later to tear it into parts and rewrite to fit into your code base.

So there is still a lot of work to do, and I will probably postpone some of the features [2] to get a working piece of code out in reasonable time frame.

ETA? Before Christmas (fingers crossed).

[1] Concurrent = code "in-flight" at the same time, Parallel = code executed in parallel

[2] Like using off-mesh connections and more robust handling of mesh changes. Not complicated code, just annoyingly puzzley to figure out correct state handling, and how to juggle that state around.

Experimenting with ORCA

2010-09-19T05:01:00.000-07:00

Ever since RVO2 library came out, I've been itching to dust off my old ORCA test and try to get it to work. I really like the simplicity of the method.

I don't have the required intuition to debug linear programming, so I opted to calculate the union of the constraints as polygon clipping instead. I start with a rectangle, which roughly describes all the admissible velocities, and chip away each of the constraints using poly-plane clipping algorithm in 2D. In above picture the result polygon is drawn in white.

As suggested in the RVO2 forums, in case the resulting polygon would be empty (no admissible velocities), I remove the constraints one at a time, starting from the furthest agent. You can see this effect in the above picture, the green constraints would make the polygon null, so it is discarded. This is simpler initial alternative to 3D linear programming.

While implementing the method I ran into quite a few problems. These can be due to my lack of understanding the method, or because my actual implementation differs somewhat from the RVO2 code.

Firstly, I'm visual person so I always need under-the-hood view before I can understand some method. There was quite a big leap from the agent position and velocity to the actual constraint plane. So I first spent some time trying to see where the planes come from.

Secondly, I have hard time understanding all the intrinsic details of optimal velocity, and I'm even more confused when I compare the paper vs. the library code.

When reading the paper I get the feeling that the planes should be recalculated if you choose another optimal velocity but the library does not do that. The lib calculates the planes once, as if optimal velocity would be current velocity and then uses linear programming to try to find solution to different optimal velocities.

I get super horrible feedback effect if I set optimal velocity to the current velocity, so I used desired velocity instead and things kinda work. Kinda.

Thirdly, I cannot see how the method is able to choose good constraint planes by selecting a single choice for each object. I hope I'm missing something big here.

For example, let's take a look at the picture at the top of this post. That green plane messes things up big time. Had the method chosen the other side of the obstacle, the case would have had good solution.

Even in slightly crowded scenes that kind of problems occur a lot. Many cases I traced through, calculating the constraint using optimal velocity of zero would have solved the problem. I could not figure out good rule when to choose which one of them. I tried some obvious ideas but there always was another case which failed after the change.

I would love to love the ORCA method, but I have had a lot of trouble getting it to work.

I have a hunch that the structure of the combined velocity obstacle plays big role in temporally coherent velocity selection. Fiorini & Shiller described the structure very well in their early papers, but I have not seem much research on that field ever since.

On Navigation Robustness

2010-09-14T09:25:00.000-07:00

One important point of the Navigation Loop method is that the loop is robust. From one point of view, this is realized by making each successive step in the loop to produce more accurate solution. On the other hand, the robustness comes from the fact that system stays in control.

Steering velocity is passed for the local avoidance to not to produce velocity which will collide with others, after the final movement a collision detection is applied so that small errors can be corrected and finally the new location is ensured to be inside the navmesh so that the next iteration can work with solid data again.

Traditionally path following is implemented so that you first find spline (linear or curved) through the world and try to follow it. Two horrible things will happen with this method.

Don't Walk That Tight Rope

Following a spline iteratively will always result somewhat low pass filtered results. You will cut curners. There are several sources in the net to help you with that task, but regardless what you do, you will never be able to exactly follow that spline (unless you are just interpolating over it), which means that you will collide with something or get into areas where you cannot move away. This effect is further amplified if you use physics to move the NPC, since the navigation data and collision data never match exactly.

So the first source of problems comes with trying to follow the path and trying to detect when you are too far away from the path that you will need to replan the whole path. This method is usually really quick to get up and running, but the end result is either 90% success rate (we need at least 99.9%!) or horrible bowl of special case code spaghetti to capture fix all the known problem cases (most of which you will learn 1 week after you have shipped).

The lesson is that you should never ever ever try to follow a path as means of navigating through the world. Instead you should have more loose structure of the path (the path polygons) and find the next corner to steer to each update and adjust the path corridor as you move to next polygon. This way you never get out of the path and you always have correct direction to steer to regardless even if you veer of the ideal path.

Always On the Mesh

The second source of problems is that the NPC may get into location where it cannot reach the navmesh anymore. You should always constrain your NPCs to be inside navigation mesh when they are walking. The navigation mesh represents areas where the NPC can walk and stand with moderate effort. The input parameters for the mesh generation are adjusted so that this holds true [1].

You should have special case code to handle locations outside the navmesh like off-mesh connections (jump over things) or animations and actions around MGs or other entities. These actions should always enter/exit on navmesh.

When you keep the NPC inside the navmesh, you can always have good and valid data to use for pathfinding. Of course some sloppiness needs to be tolerated because of floating point accuracy.

If you don't keep the NPC inside the navmesh then you have similar problem as with trying to follow a spline. The two representations will get out of sync and you will spend a lot of time writing code to cope with it.

Physics... (sigh)

Robust navigation is not just "it kinda pulls this dude past this obstacle", it must pass the nastiest of the tests when the player sheds havoc on your NPCs.

The physics and navigation representation never match 100%. For this reason something that looks completely valid from navigation point if view may result dead lock collision with physics system.

So a lot of the problems comes from the fact that physics is always in control. If you want to have robust navigation it must be in control and instead you should treat physics system as a sensor for the NPC.

The physics should be used to plant the NPC firmly on ground, or you should use it to detect when someone is throwing a barrel at the NPC and blend to ragdoll, etc. There is nothing realistic or believable about things bouncing off an invisible capsule!

When you move your NPC, the navmesh boundary is the final hard constraint and is always satisfied. Before that you can have simple collision handling between the agents for cases where local avoidance fails (and it will, if not badly, you will get at least accuracy errors).

To sum it up, don't try to follow a tight rope, you will fail. Always keep the NPC on navmesh, or you will fail. Physics is good tool, but bad master.

I know removing the physics roundtrip will be hard to swallow, but give it a try! :)

[1] If the navmesh generator does not produce mesh for all the locations you wish to be navigable, then you need to change the params or add extra annotation to handle these locations. For example the NPC might be able to walk down certain steep slopes, but these may be rejected from the navmesh. It is not trivial to detect these areas as you would need to extract the direction the agent could move. Annotation and special navigation code is easier solution for this case.

My Summer of Code 2010

2010-08-29T23:20:00.000-07:00

This where all the magic happened!

You may have noticed the increased traffic on the commits and the blog. But now Mikko's Summer of Code has come to an end. I used a few weeks of downtime between projects to flush my TODO queue. I'm starting a new project this week and I will be back to my 1 day a week schedule with RC&DT.

Here's some thoughts on what are likely to happen in near future.

Multi-Agent Navigation

I got the multi-agent navigation to much further state than I expected. The code is currently huge pile of spaghetti. The next step is put it all together. I have been trying to think about the API and it seems to be quite a big task. I think it is good that my progress is slowing down so that I can let things simmer in a bit.

If you have some thoughts how you would like to integrate the multi-agent navigation to your project, please let me know!

Would you like to use it as a component? Do you want a manager you can tick or do you prefer to do that yourself? Do you use physics for collision detection? Where in your agent update cycle you are planning to put the path following code? Any input is welcome. If you don't want to share the secrets here you can always send me email too.

Everyone is integrating path following slightly differently. I hope to support as many people as possible. On one extreme there are the folks who just would like to get plug'n'play, and on the other side are the folks who would like to get the max performance which means that I need to split the API so that you can tear everything apart as necessary.

My current idea is to roughly separate the code into roughly four pieces:

mover
steering
obstacle avoidance
collision detection

The mover takes care of handling path corridor and movement along navmesh surface. In theory you could use it to create NPCs or even player movement. It will also keep track if new path should be queried.

Steering is game and behavior specific so I think I will add some helper functions to the mover class which allows you to build your own. I will provide some examples how to do it too.

Obstacle avoidance will be separate class which can be used even without any of the mover stuff. Basically you feed in obstacles and the agent state (position, radius, velocity, desired velocity) and it will spit out new velocity which should result in less collisions than the desired one. The first implementation will be the sampled VO, I'm looking into adding ORCA stuff too later.

Collision detection will be responsible of finding the neighbors to avoid and to collide with. This is potentially something that your engine does already. I might include this only in the example code.

Many of the tasks required for multi-agent navigation are embarrassingly parallel (see all the for loops in the current CrowdManager::update()). My idea is to tailor the APIs so that when possible you just pass in the data that is absolutely necessary. For example the obstacle avoidance code will not figure out the neighbors itself, but you need to feed them.

I will create an example which can be used for learning and also something that can be integrated as is, for those who just like to get quick and dirty integration.

Detour Error Handling

There are some cases where Detour should be more verbose on error cases. My work on the multi-agent navigation has revealed some short comings in the error handling code too and the sliced pathfinder work surfaced some ideas too.

I'm planning to improve the Detour API at some point so that it will report errors better. The change will be most likely that every method will return a status instead. This allows me to report invalid input data and more elaborate reason why path finding may have failed or report that path finding succeed, but actually returned partial path. There are some discrepancies on the raycast() function return values too.

Temporary Obstacles

I got quite exited about the heightfield compression findings and got some really good feedback on it too. It is definitely something I wish to prototype more in detail.

This also ties into better Detour error handling. I will need to finally figure out how to handle interrupted and invalid paths. Detour will not replan automatically, but it will let you know what something went wrong or that something will go wrong in the future so that you can schedule new path query yourself.

RVO 2 Library

2010-08-27T02:08:00.001-07:00

RVO2 Library has just been released. It uses optimal reciprocal collision avoidance (ORCA).

http://gamma.cs.unc.edu/RVO2/

I have had tried to implement ORCA a couple of times before but did not succeed. It'll be interesting to compare my earlier attemps with the sources and give it another go. I did not quite get what they are doing in linearProgram3() with projLines stuff, though.

There is one comment in the examples, which I found particularly charming:

Perturb a little to avoid deadlocks due to perfect symmetry.

Handling Temporary Obstacles

2010-08-25T15:08:00.000-07:00

I have been using some idle cycles every now and then to try to think about a nice method to update the navmesh without requiring to completely rasterize and rebuild a tile from scratch. This would be useful for obstacles, which may break and may be pushed around and usually only contribute blocking areas into the navmesh.

Cookie Cutter Obstacles

One method to do that is to punch holes in the navmesh using CSG. Some path finding middleware support that and some games shipped using it. So it definitely works, but I don't like the method.

Firstly, you have to work around the floating point accuracy, which is paramount pain. Secondly, it usually is too accurate, which means that you get some small polygons all over the place. Thirdly, it does not scale well when you have multiple overlapping obstacles. So it is an option, but very very low on my list of things to try.

Local Grid

Another option would be to use local grid and rasterize all the temporary obstacles into it and then use another simple pathfinder to find around the way.

The good thing about this method is that overlapping obstacles is not a performance issue anymore. Because grids often have lower resolution than actual world geometry, they tend to simplify the obstacle area too, so it solves the small triangle problem too.

The down side is that you have second representation of your world. The problem it creates is that what to do when the path is blocked? There is no way to reliably pass that data back to the navmesh and replan the path, as it would require to change the layout of the mesh. Simply blocking certain polygons temporarily does not fix it.

Recreate Piece of a Navmesh

Currently the way I prefer to handle dynamic obstacles is to recreate the tiles where an obstacle has changed. Tiling helps to limit the amount of work that needs to be done. While it works well in practice it is overkill for many situations, including the temporary obstacle case.

That has lead me to thinking that how much of the work that goes into rebuilding a tile could be cached?

In practice the answer is that at minimum you need to have the data that is stored in Recast compact heightfield to rebuild a tile and have the benefits of the grid. At the compact heightfield level each obstacle could be rasterized in the heightfield as specific area type and then the rest of the Recast pipeline would be run to obtain the final mesh for a tile.

There are some shortcuts that can be taken to make the rest of the Recast process quite a bit faster than usually. One optimization is to use monotone region building function. Another one is to use more loose parameters for detail mesh calculation. For small tiles, this can halve the build time which is spent after rasterization.

In practice it means, that if we could start from compact heighfield, we could rebuild a tile on 1 ms instead of 10 ms. And by using the simpler methods the work can by split into similar sized chunks so it is possible to handle the building over several frames.

But compact heightfield can be a lot of data which makes the idea impractical. Only if we could compress it...

Compressing 2.5D Heightfield Data

By inspecting the data stored in the compact heightfield, we can see that the data per span does not vary very much between neighbours. Also it happens to be stored in a way that helps usual compression algorithms to pack it well too.

The 2.5D heighfields in Recast are stored as columns stacked on top of each other. If there are multiple voxels on top of each other, they are stored as single span. This is often called run length encoding (RLE).

The spans in compact heightfield are stored in one flat array. In addition to that there is a grid of cells at XZ-plane, which stores index and span count for that column. So when you need to find all the spans at certain location, you first lookup the index to the large span array from the cell and loop through all the spans that belong to the column.

The layout is also awesome to store links to neighbours, you only need to store a small sub-index, which added to the index found from the neighbour cell to finally find the actualy span.

Because of the memory layout, all the parameters of spans can be easily stored in one contiguous array, which is good for compression since neighbour parameters are often the same. In practice only the span y and area type are needed to rebuild compact heightfield.

For the base grid, it is only necessary to store the span count per grid cell. The index can be recalculated by accumulating the counts.

The above picture shows 2.5D heightfield of size 208 x 503. The resulting compact heightfield data that is required by Recast to build the navmesh is 1662 kB.

When the data is stripped down to the minimum as explained above, the amount of data is 508 kB. Since the data is so similar it is only 29 kB after being compressed with zip! The height data should compress even better if delta encoding is added.

Conclusion

Using compressed compact heightfield could potentially be interesting solution to handle temporary obstacles. For small tiles, the rasterization can often take up to 90% of the total time required to build one tile worth of navmesh. The method would require extra data to be stored per tile, but the data should be manageable since it can be compressed by about 1:50.

Recast API Breakage Redux

2010-08-24T11:32:00.000-07:00

I did some changes to the previous Recast API adjustments. The changes are not that big this time.

The first change you notice is that rcBuildContext is now called just rcContext. The second change you may notice that the time query functions are gone, and how there is startTimer()and stopTimer() instead. The third change is that you can disable the virtual function calls using a boolean flag if you want to.

These changes should make the rcContex simpler to implement and maintain.

Available in R206, the VC project is broken until I get back to my win machine again.

Path Following Performance pt. 2

2010-08-23T14:43:00.000-07:00

Got the performance to quite constant sub 1 ms with adaptive sampling even in heavily crowded situations. The RVO samples (red) still dominate the performance. I think I'll stop here for a moment, remove a couple of quadratic loops, start figuring out how to package it better and open the flood gates for a couple of trillion bug reports.

That yellow spike is new path requests for all agents in a single frame. I'm quite happy about the Detour performance here. It stays about the same on larger meshes too. I'm particularly happy that I could keep the raycast there to optimize paths a little each update.

Path Following Performance

2010-08-20T06:52:00.000-07:00

I started working a bit on the path following again. Naming things better and moving stuff around. I also added a simple profiler to the stuff too as seen on above picture. The case shows 25 agents moving in a quite simple level.

The bad news is that the performance is bad! The good news is that it's ok.

There are two times tracked in the above picture. The red-ish line shows how much time is spent in the brute force RVO sampling, and the lime-ish line shows the time taken by the total navigation loop calculation.

My goal is to get this case to around 0.5 ms, and I think it is doable.

Visibility Optimized Graph Experiment

2010-08-20T04:02:00.000-07:00

I blogged earlier about A* node placement. I had the change to try out the visibility optimized node placement today. First impression, not impressed.

It generates quite aggressively goal directed paths, much like if you over estimate your heuristic (or was it vice verse). The final segment to the goal is always perfect, though.

In case someone wants to give it a try, here's the code I used:

static int isectSegSeg(const float* ap, const float* aq,
                      const float* bp, const float* bq,
                      float& s, float& t)
{
   float u[3], v[3], w[3];
   dtVsub(u,aq,ap);
   dtVsub(v,bq,bp);
   dtVsub(w,ap,bp);
   float d = dtVperp2D(u,v);
   if (fabsf(d) < 1e-6f) return 0;
   d = 1.0f/d;
   s = dtVperp2D(v,w) * d;
//    if (s < 0 || s > 1) return 0;
   t = dtVperp2D(u,w) * d;
   if (t < 0 || t > 1) return 0;
   return 1;
}

...

if (neighbourNode->flags == 0)
{
   float sa[3], sb[3];
   getPortalPoints(bestRef, bestPoly, bestTile,
                   neighbourRef, neighbourPoly, neighbourTile,
                   sa, sb);
   float s,t = 0.5f;
   if (!isectSegSeg(bestNode->pos,endPos, sa,sb, s, t))
       dtDistancePtSegSqr2D(endPos, sa,sb, t);
   t = dtClamp(t, 0.1f, 0.9f);
   dtVlerp(neighbourNode->pos, sa,sb, t);
}

Custom Detour Query Filters

2010-08-20T02:31:00.000-07:00

I just committed the change for custom query filters and slight optimisation for the A* (SVN R200).

Custom Query Filters

I kept the earlier default behavior of the filter, so the API and functionality change is really small. Instead of calling dtNavMeshQuery.setAreaCost() you now call dtQueryFilter.setAreaCost().

There was quite some discussion if the passFilter() and getCost() should be virtual function calls or not. For people working on PowerPC processors it can be quite a big deal as both the functions are called per node during A*. On PC, the perfomance loss of using virtual function is not super bad (about 5-10%) compared to the flexibility it gives.

There is a define in the dtNavMeshQuery.h called DT_VIRTUAL_QUERYFILTER. If the define is set, the above mentioned functions are declared virtual and you can override them. In other case, the default implementations are inlined which should lead maximum performance. This was the best compromise I could think of.

Your custom query filter should be as fast as possible, as it can easily dominate the A* performance. If you want to query an agent flag, cache it locally inside the custom filter before you call pathFind(). If you need to do physics queries, try to cache them too before hand too. Use as little extra data as possible.

A* Optimization

While I was testing the impact of the virtual calls I noticed that the edge midpoint calculations were taking quite substantial time, so I tried caching the results. I earlier thought that having smaller node size and recalculating the edges on the fly would be more efficient than storing the node positions. It doubles the node struct size and all.

It turns out I was wrong (may vary per platform). Anyways, the node position is now stored for each node. This also opens up possibilities to try different node calculation methods. Caching the node positions resulted about 15% speed improvement.

This is the piece of code that calculates the node position:

            // If the node is visited the first time, calculate node position.
           if (neighbourNode->flags == 0)
           {
               getEdgeMidPoint(bestRef, bestPoly, bestTile,
                               neighbourRef, neighbourPoly, neighbourTile,
                               neighbourNode->pos);
           }

Be aware not to create neighbour nodes on top of each other (that is, zero length connections). For example if you want to place that new node so that it is the nearest point on the edge from parent node, then you should clamp the edge 't' to lie between for example 0.001 and 0.99, or something similar. You can use getPortalPoints() to query the segment which connects best and neighbour.

I also added a debug view mode which displays the nodes and link to their parents. This should help to see how well the node placement might work.

Navmesh Node Locations

2010-08-19T10:45:00.000-07:00

I have previously calculated the A* node locations on the fly to save memory. That is when I expand to neighbour polygons, I calculate the edge mid location on the fly. While profiling the filter change proposal, I also tested caching the A* nodes locations. This gave me the benefit to also being able to draw them.

There was one particular location in one of my test levels which always bothered me. I had plotted it out few times in Photoshop, but now I can finally see what was going on.

The above picture also illustrates the reason why navmeshes sometimes produce unoptimal paths. The A* is actually ran on that "skeleton". The problems pretty much always occur where small and large polygon are next to each other.

To answer the question in the picture. That detour is selected because the route along the skeleton is shorter than crossing through that large polygon. When you see the skeleton it is easy to understand, but when it is not visible, it looks plain odd.

Proposal for Custom Cost and Polygon Filter for Detour

2010-08-19T07:30:00.000-07:00

I have been recently discussing a potential solution to issues 47 and 103 with Neil Armstrong. That is, how to allow the user to pass custom cost values for A*. In some cases the different travel costs could be based on NPC type, or maybe even some local context like trying to avoid the polygon where the target is.

I think this kind of functionality is really important to achieve correct gameplay, and usually there is no one solution that fits all.

I'm proposing a change to the dtQueryFilter which would allow custom logic on polygon filtering as well as custom cost for searches. Here's the interface and the current implementation as an example:

struct dtQueryFilter
{
   dtQueryFilter() :
       includeFlags(0xffff),
       excludeFlags(0) {}
  
   virtual bool passFilter(const dtPolyRef ref,
                           const dtMeshTile* tile,
                           const dtPoly* poly) const
   {
       return (poly->flags & includeFlags) != 0 &&
              (poly->flags & excludeFlags) == 0;
   }
  
   virtual float getCost(const float* pa, const float* pb,
                         const dtPolyRef prevRef,
                         const dtMeshTile* prevTile,
                         const dtPoly* prevPoly,
                         const dtPolyRef curRef,
                         const dtMeshTile* curTile,
                         const dtPoly* curPoly) const
   {
       return dtVdist(pa, pb) * areaCost[curPoly->area];
   }
  
   float areaCost[DT_MAX_AREAS];

   unsigned short includeFlags;
   unsigned short excludeFlags;
};

The input to the cost function is a line segment from pa to pb which travels along curPoly and the previous and next polygons.

I'm not big fan of interfaces and I was worried how much overhead it would add. In my test case the path queries vary from 0.030 ms to 0.135 ms (there are some small fluctuations from run to run). When the passFilter() is virtual function instead of inlined function it adds 0.010 ms to 0.020 ms per path query. I think the interface is worth it.

So this post is request for comments. Unless anyone disagrees or proposes better solution, I will check in the changes.

[EDIT] I did few more tests and the above did not actually include the cost as virtual call, only the polygon filter as virtual function call. In total the virtual function call version is something around 5-10% slower.

Recast API Breakage

2010-08-19T02:31:00.000-07:00

I just committed a change (SVN R197 R199) which adds rcBuildContext, and breaks that API. Sorry for the trouble! I hope you welcome the new changes.

The newly added rcBuildContext abstracts the timer, logging and build time reporting. I'm planning to add more error and warning handling support via that interface in the future, for example drawing and high-lighting bad geometry.

Majority of the Recast functions now expect a valid pointer to rcBuildContext as first parameter. Allocators and a couple of really simple utility functions are an excetion. If you don't care about build timing or logging, you can just pass a pointer to an instance of the default implementation of rcBuildContext. Like this:

rcBuildContext dummy;
...
rcErodeWalkableArea(&dummy, m_cfg.walkableRadius, *m_chf);

There is an example implementation in the SampleInterfaces.h/cpp. I also moved the other example implementations of interfaces there (FileIO, DebugDrawGL).

The files RecastTimer.h/cpp and RecastLog.h/cpp were removed in the process. I added RecastAssert.h which is used in some places to check that validity of the passed parameter (more validation later).

I wish a smooth migration! Let me know if there is something I overlooked.

Off to update the Win32 project. [EDIT] updated.

Detour Sliced Path Find

2010-08-17T11:32:00.001-07:00

Well, while I was in teh mood, I though I'd give it a go.

I just checked in (SVN R196) some extra methods for dtNavMeshQuery which implements sliced path finding. It works as follows:


// Request
m_pathFindState = m_navQuery->initSlicedFindPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter);

...

// On update
if (m_pathFindState == DT_QUERY_RUNNING)
    m_pathFindState = m_navQuery->updateSlicedFindPath(maxIter);

if (m_pathFindState == DT_QUERY_READY)
    m_npolys = m_navQuery->finalizeSlicedFindPath(m_polys, MAX_POLYS);

There is new tool called "Pathfind Sliced" which allows you to see it in action. The tool advances the search one node at a time so you can see how the closed list is update in realtime.

The actual path find is a tiny little slower than the findPath() because it does more validation. It should catch the case that some of the data is being removed while the query is in flight, and if the update encounters invalid data it will return DT_QUERY_FAILED.

If the removed data was already in the closed list of the search, the path result will contain invalid data. The rest of the API can handle that, but I recommend restarting all currently running path requests after you have added or removed a tile.

Detour Navmesh Data and Queries Separated

2010-08-17T08:11:00.000-07:00

I just checked in code (SVN R194) which separates the navmesh data from the queries. In the process I also cleaned up how the data is accessed via dtNavMesh.

API Changes

In a nutshell this means that instead of using dtNavMesh, you use dtNavMeshQuery, except when you initialize the data of course. That is pretty much the only change if you are using Detour in single threaded system.

All the query methods have been moved to dtNavMeshQuery. The dtNavMesh class now only has methods to add, remove or change the data.

I removed bunch of getters. Now the right way to access the data pointed by dtPolyRef is:

bool getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;

It takes polygon ref as input, and stores pointer to tile and polygon as output. The function returns false if the poly ref is not valid.

Parallel Stuff

The new change allows you to better control the memory access of Detour for multi-threaded systems. The navigation mesh data stored in dtNavMesh is considered read-only by the dtNavMeshQuery. This also allows multiple dtNavMeshQueries to work on the same data. If you organize your data modifications and queries right, there is no need for locks.

The basic outline of multi-threaded use of Detour is as outline by Bjoern in [1]:

Update the navigation mesh (set flags, add or remove tiles)
Collect new pathfinding requests or pathfinding-change requests. Requests are deferred and not processed when posting them.
Process all pathfinding requests.
Make pathfinding results available.
Clear out all closed pathfinding requests and prepare for the next main loop cycle.
Back to stage 1.

I recommend reading Bjoern's post if you are interested in parallelizing your path finder. Also, any feedback is welcome. I will not be providing task scheduler, though, no point asking for it :)

So this is the first step towards more parallel Detour. The big task yet to tackle is to make all the queries to finish in more predictable time. The findPath() is really unpredictable in its' current form.

There are two options to improve that: 1) slice it, 2) add hierarchy. The final choice might be both.

Slicing means that only a set number of nodes are visited by the A* every update. It is simple to implement, but since the data can change between the updates, there needs to be much more bookkeeping in the process. Also, slicing means that the dtNavMeshQuery will store an intermediate state. That is, it would not be possible to run other query methods between the path find iterations, as they might mess up the open and closed lists.

I think in the long run the hierarchy is the way to go, but it needs new data structures and all sorts of things to be prototyped before it is ready to go in.

As an intermediate step, I'm probably going to implement iterative findPath() at some point.

[1] Parallel Detour navigation mesh

Some Recast & Detour Projects

2010-08-17T00:27:00.000-07:00

The image is composed of a screen shot from the game Kingdoms of Amalur: Reckonin, GSoC10 projects for CrystalSpace and Blender.

Recast & Detour has seen quite nice adaptation during the past year. During the Paris Game AI Conference I run out of fingers to count the AAA projects currently in production which are using some part of Recast and Detour. In addition to that looks like there are countless indie, open source or hobby projects which I'm totally unaware of too.

Some projects have ported the code to different platforms, some have made quite heavy modifications to add features needed specifically for their game, and some are just using some parts of the code. It's awesome that Recast and Detour are being put in use! This also means that quite a few bugs have been reported and fixed too.

Here's some recent projects I'd like to highlight (if you like to share yours, drop me a line or comment below):

Kingdoms of Amalur: Reckoning
I'm glad that I'm allowed to share that up coming game Kingdoms of Amalur: Reckoning by Big Huge Games is using Recast and Detour.

Google Summer of Code 2010
Thanks to Nick and Leonardo, Blender Game Engine and CrystalSpace both leveled up on pathfinding this summer.

I'm thankful to all the people who have sent bug reports, fixes, improvements, suggestions or challenged me. It has made the toolkit so much better!

Heads Up, API Changes Coming Soon

2010-08-16T02:14:00.000-07:00

I try to get two API breaking changes done this week.

1) Recast Context: This change will add additional parameter to most of the recast calls. I have yet to decide if the parameter will be the first or last. The idea behind this change is to remove platform dependancy of error/warning logging, timer and profiling code from Recast. See:

2) dtNavMesh & dtNavMeshQuery: This change will allow multiple simultaneous navmesh queries to happen at the same time. Basically it will strip dtNavMesh to just the data management, and add new class which has all the query functions. This makes Detour more concurrency friendly. See:

I will make separate posts describing the changes once I get things checked in.

Some More Movement Progress

2010-08-12T06:20:00.000-07:00

Since last time, I implemented smooth steering, drunken movement style and sampled velocity obstacles.

The features are coming together, but the code is still huge pile of mess. I checked in first version (R193) so that the change list does not become too big.

When using tiled navmeshes and many agents, I got quite a bit of problems with agents trying to move backwards to catch up with their path. This happens mostly around the vertices which are at tile corners.

For the time being, I added that raycast trick which tries to optimize the path corridor by checking if there is line of sight from the current location to the corner after the next corner. If so, then the beginning of the path is patched to use the results from the raycast.

The performance is still realtime (it chokes when you have large group next to each other), but I bet it is actually really horrible. Once I get the structure of the code better, I'll start looking at the optimizations.

Oh, it moves!

2010-08-10T11:55:00.000-07:00

The first test of a couple of agents moving around in a test level, yay!

I have implemented the navigation-loop stuff, simple steering, simple dynamic constraint, and simple collision handling. I need to rethink the way stuff is organized so that it is easier to grab the necessary code to your own projects.

It's always so amazing when it works the first time, even if it just barely does.

Detour Agent Movement Progress

2010-08-09T06:28:00.000-07:00

I'm moving forward with the agent movement code for Detour. Today I added a couple of functions to Detour help me realize the goal. Check NavMeshTesterTool.cpp how to use the new functionality.

dtNavMesh.moveAlongSurface() - This function tries to move an agent from start position to target position along the navigation mesh and constraints the position to be inside the navigation mesh at all times. The function is Detour implementation of the algorithm I explained in a previous post. In the process I removed the old moveAlongPathCorridor(), which supported only subset of the functionality anyways.

dtNavMesh.findLocalNeighbourhood() - This function finds non-overlapping (in 2D) neighbourhood around a specified point. It is useful for local navigation. I have explained the algorithm earlier too.

dtNavMesh.getPolyWallSegments() - This functions returns wall segments of a specified navmesh polygon. In conjunction with findLocalNeighbourhood() it can be used to generate 2D collision segments for local obstacle avoidance.

The image at the top of the post shows local neighbourhood segments queried using the new functions.

All the above functions assume that they operate on really small set of polygons. To achieve a bit better cache coherence, I added another tiny node pool, which currently only contains 64 nodes. The aim was to improve cache coherence. The node pool uses hash table to lookup nodes based on ID. When dealing with small number of nodes this actually slows things down because of the random access through the hash table.

Additionally, instead of using priority queue, the above functions use fixed size small stack and breath first search. The random access of the navmesh polygons is quite cache pooper already, but the above gives around 30-50% speed up compared to using the existing p-queue and larger node pool.

I'm planning to spend some more time this week in the agent movement stuff. The above functions are bound to change as I try to find my way through the implementation details.

Finding Local 2D Neighborhood of Navmesh

2010-07-29T05:07:00.000-07:00

As part of my quest to move the multi-agent navigation to Detour I have been testing a little how to find local 2D neighbour of a navmesh. The method should answer the question that given a point on the navmesh and certain small radius, what are the potential navmesh edges to avoid. Since the Detour navmesh is sort of 2.5D structure, it is possible that the returned polygons may curl over itself close to bridge like structures.

My initial idea was to find visibility polygon from a single source point, but practical implementations are prone to the usual floating point accuracy issues, plus you would need to do that query every time an agent moves, which has the potential to become the bottleneck of the whole local avoidance.

Instead, I though I'd try to find a good way to eliminate the polygons which cause the problems. Finding the nearest polygons is simple using dtNavMesh.findPolysAroundCircle(), finding overlapping polygons is quick using SAT. But in case of overlap which polygon to keep?

One interesting feature of findPolysAroundCircle() function is that it returns the polygons from nearest distance to the furthest. Under the hood the method uses Dijkstra to find the polygons around. The method was designed to return the most relevant information up to the buffer limit the caller passes.

Since we have this information around, we can make the polygon culling so that if two polygons overlap, the latter–or furthest from the current location—polygon is always removed. So depending on situation the most irrelevant polygon is removed.

This seems to work great in practice as you can see from the image at the top of the post. If the start location is close to the ground plane, the ground polygons are chosen the the bridge is culled and vice versa.

Below is the code that I used for testing. The function arePolysNeighbour(), which check if there is a link from the first poly to the next poly, since they are two convex polygons, they cannot overlap if they are neighbours. The function testPolyCollision() does 2D poly-poly SAT collision check on XZ-plane.

float pa[DT_VERTS_PER_POLYGON*3];
float pb[DT_VERTS_PER_POLYGON*3];
npolys = m_navMesh->findPolysAroundCircle(startRef, startPos, radius, &filter, polys, m_parent, 0, MAX_POLYS);
for (int i = 0; i < npolys; ++i)
{
   bool valid = true;
   const int npa = getPolyVerts(m_navMesh, polys[i], pa);
   for (int j = 0; j < i; ++j)
   {
       if (arePolysNeighbour(m_navMesh, polys[i], polys[j]))
           continue;
       const int npb = getPolyVerts(m_navMesh, polys[j], pb);
       if (testPolyCollision(pa,npa, pb,npb))
       {
           valid = false;
           break;
       }
   }
   polyflag[i] = valid;
}

I'm a little worried about the performance, but it is not necessary to update the neighbourhood every tick, so several optimization methods may apply. I have to do some more testing, whether there are some corner cases which are not yet handled using the code. And I will need to check the performance more in detail too.

All in all, I think I have pretty much all the ingredients to build multi-agent navigation for Detour. The rest is just API design and hard work :)

Finding Navmesh Polygons Touching a Convex Shape

2010-07-21T00:15:00.001-07:00

I added new query method to dtNavMesh to find polygons which touch a convex shape, findPolysAroundShape().

The function is similar to findPolysAround(), but with different boundary condition. As a matter of fact, I also renamed the findPolysAround() to findPolysAroundCircle() to make it less confusing. The function can be useful for creating some gameplay features such as doors.

The new method is somewhat slower than findPolysAroundCircle() because it uses polygon-segment intersection test to see if an edge should be visited.

Available in R186.

Constrained Movement Along Navmesh pt. 3

2010-07-19T23:57:00.001-07:00

The most boring topic of the year makes a comeback! I have been struggling a bit to make robust movement along navigation mesh, but I think I finally nailed it.

Why should you care?

The basis of solid navigation loop is good collision handling. For navigation meshes this means a way to handle movement along connected graph of convex polygons. That is, how to move from one polygon to another and how to handle the case when the desired move collides with blocking navigation mesh edge.

The method should also return the polygons it walked through during the movement. This is used to fixup the path corridor so that on next update we have valid path to follow again.

First idea: Raycast

My very first implementation of movement code used raycasts. I used similar iterative code as the good 'ol ellipsoid vs. trimesh collision detection. The problem with that solution was that the rays end up being parallel to the polygon edges when sliding or hit vertices when aiming for next corner. I ended up running into a lot of floating point accuracy errors and quite interesting special case hacks to get rid of them.

Second idea: Point in Polygon

My second attempt changed the whole idea upside down. I can calculate the sliding movement inside a convex polygon by clamping the target point to be the nearest point in the polygon. To handle the connected graph of convex polygons (like navmesh) we can check if the nearest point would lie on an edge which leads to neighbor polygon, and follow that until the goal polygon has been found.

While the basic idea is sound, here area a couple of cases where it does not produce desired result. Firstly there are some corner cases where it will miss potential move to neighbour polygon because it does not check visibility (see my previous post). Interestingly this is not a problem when using triangles.

Second, nasty problem is that it does not handle well the case that the nearest point is at a polygon vertex. In this case either edge are equally good candidate to follow and I could not find goo heuristic which would handle all the corner cases I had in mind.

This method is a bit similar to the jump-and-walk algorithm which is used to locate triangles in triangulation. It is known to work on triangulations which have convex boundary.

Third idea: Search

This idea extends the previous by making it breath first search instead of iterative loop. That nicely solves the problem of trying to choose good branching at each iteration, all branches are followed instead.

The search expands to all edges which touch circle containing the start and goal location (start+delta). The search is stopped when the goal polygon is found or no more polygons can be visited. In case the goal is inside a polygon, the goal location is accepted, else the nearest point to all visited blocked polygon edges is chosen.

In pseudo code it looks something like this:

// Applies constrained movement from startPos to goalPos.
// The result is stored in clampedPos.
// Returns number of visited polygons.
int Navmesh::navmeshMoveAlong(Vec3 startPos, PolyRef startRef, Vec3 goalPos,
               PolyRef* visited, Vec3& clampedPos)
{
   Stack stack(16);          // Tiny stack
   ClosedList closed(32);    // Tiny closed list
   Vec3 bestPos, p;
   float bestDist = FLT_MAX, d;
   PolyRef bestRef = UNDEF;   
   // Search constraint
   Vec3 searchPos = (startPos+goalPos)/2;
   const float searchRadius = vdist(startPos,goalPos)/2;
    // Init
    bestp = start;
   stack.push(startRef);
   closed.add(startRef,startRef); // Self ref, start maker.

   while (!stack.empty())
   {
        // Pop front.
        PolyRef cur = stack.pop();
       Poly* poly = getPoly(cur);
       // If target is inside the poly, stop search.
       if (pointInPoly(goalPos, poly))
       {
           bestRef = cur;
           bestPos = goalPos;
           break;
       }
        // Follow edges or keep track of nearest point on blocking edge.
        for (int i=0, j=poly->nv; i<poly->nv; j=i++)
       {
           const PolyRef neiRef = poly->nei[j];
           const Vec3& sp = getVertex(poly->v[j]);
           const Vec3& sq = getVertex(poly->v[i]);
          
           if (neiRef == UNDEF)
           {
                // Blocked edge, calc distance.
                p = closestPtPtSeg(goalPos, sp,sq);
               d = vdist(p,goalPos);
               if (d < bestd)
               {
                    // Update nearest distance.
                    bestPos = p;
                   bestDist = d;
                   bestRef = cur;
               }
           }
           else
           {
                // Skip already visited.
                if (closed.find(neiRef)) continue;
                // Store to closed with parent for trace back.
                closed.add(neiRef,cur);
                // Non-blocked edge, follow if within search radius.
                p = closestPtPtSeg(searchPos, sp,sq);
               d = vdist(p, searchPos);
               if (d <= searchRadius)
                   stack.push(neiRef);
           }
       }
   }
    // Trace back and store visited polygons.
    followVisited(bestRef,visited,closed);
    // Store best movement position.
    clampedPos = bestPos;
    // Return number of visited polys.
    return visited.size();
}

So it is a tiny special case pathfinder. The result is movement which can quite liberally move along the navmesh and if it encounters walls it will slide. The slack is necessary when you need to shortcut a little for example when very close to the next corner along the path.

The code above is meant to perform well when you do really small increments. It aims to be faster than regular pathfinder which is tuned to perform well with potentially thousands of nodes.

For such local case you may maintain the open list (stack) and closed lists using simple arrays. There are many cases in the code which may trash your cache (accessing the navmesh data), but by using small arrays for open and closed lists you can avoid some of it. Since we expect the lists to be small, we can potentially use simple linear searches which simplifies the code.

Next Step

My next task is to figure out nice way to calculate 2D local collision environment from 2.5D navmesh. This is to be used with velocity obstacles. Then I should be ready move on porting the VO code to Detour.

Recast Area Types Per Triangle

2010-07-13T00:02:00.000-07:00

I just committed a change (R185) which allows you to pass area type per triangle for rasterization.

API Changes

From Flags to Areas

Firstly, the flags are now gone from the rasterization functions and area type is used instead. Now same concept of marking things walkable or not is used throughout the pipeline.

If you want to make a triangle non-passable, use area type of RC_NULL_AREA. If you don't care about area types at all, you should use general RC_WALKABLE_AREA.

rcMarkWalkableTriangles() uses that area type that to keep the existing behavior. I also added rcClearUnwalkableTriangles() which does the opposite, that is sets the area types of a triangle to RC_NULL_AREA if the triangle slope is too steep. Handy if you have an array of area types to start with.

The change to the rasterize methods is minimal, instead of passing a flags now you pass an area type.

Compacting Heightfield

When the heightfield is processed to compact heightfield, there used to be a flag parameter. This is gone now, so flags parameter from rcGetHeightFieldSpanCount() and rcBuildCompactHeightfield() are omitted now. Every voxel that has are type other than RC_NULL_AREA will be included in the span count as well as in the compact heightfield.

Filtering

The area eroding function used to have a trace of some old ideas of mine which required you to pass area type to it. The area type is removed now. I changed the function name to rcErodeWalkableArea() to better reflect what it is actually doing.

Aliasing

The new feature comes with a new set of problems. One problem is aliasing. In many ways voxelization works the same way as z-buffer. When surfaces are intersecting each other at low angle or almost parallel we will get aliasing error usually referred as "z-fighting".

This can cause nasty noise at the boundaries of different types of areas. One simple way to fight this is to apply media filter to remove the speckles. I have added rcMedianFilterWalkableArea() just for that.

Median filtering will smooth things out a bit, so if you want to keep as sharp as possible outlines for rcMarkConvexPolyArea() you may want to apply the filtering before you mark the areas. Otherwise I recommend to apply the filtering just before you build the distance field and build regions.

Median filtering is not super expensive, but not free either. On average add 1-2% to the generation time (that is, 10ms on 1000ms generation process).

Accuracy

In order to not to increase the memory footprint of voxelization process, I took some bits from the height range and moved them to the area types in rcSpan structure. This basically reduces the height range from 32k to 8k.

For majority of the users this is fine. One of my test levels which goes 6 stories above and below the ground uses max height of 1450 (human sized character, cell height 0.2).

If you run out of bits there, you can adjust the bits in rcSpan struct (remember to also change RC_SPAN_HEIGHT_BITS). This is likely to increase the rcSpan size from 8 bytes to 12 bytes (on 32 bit machines) and that will reflect in memory consumption.

Sorry for the API breakage, but I hope this will make things more flexible for many people!

Sumo vs. Ninja

2010-07-12T00:45:00.001-07:00

Steering Behaviors is interesting method to create life-like behaviors for agents. It is tempting to use it for local avoidance. It is simple and intuitive to understand, but it comes with one really fatal drawback. When it breaks–and it will–it is eventually impossible to tune to get the desired behavior.

Velocity based collision avoidance methods on the other hand are a bit harder to get up and running, but get past the point where steering behavior based local avoidance fails. They sure come with their own share of problems too, like all sorts of jittering and feedback effects. But those problems are manageable and tunable to greater depth than anything based steering behaviors.

One way to look at describe the difference between these two methods is that steering behaviors based avoidance is basically a sumo-suit your character wears. As you bump into something, you are gradually pushed away. But when things get tight, you get stuck, and just tumble around.

One the other hand you want your characters to be suave like ninja, slipping through even the tightest of all encounters.

Eventually you want the agents to be as forward looking as an octopus, so that they can plan their avoidance velocities even better.

Custom Memory Allocator for Recast and Detour pt. 2

2010-07-09T06:26:00.000-07:00

Ok, the update of the last post got kind out of hands. I did not expect to get this all done today.

The custom memory allocator for both Recast and Detour are submitted in R178 in SVN. The latest update also fixes the Visual Studio project and one array allocation bug which surfaced in VC.

As highlighted in the previous post, the API has changed on how the objects are required to be constructed. There is now alloc and free functions for each object (dtNavMesh, rcHeightField, etc). I used the same pattern all over the place, so it should be easy to spot.

[EDIT] Few more bugs were still there. Folks living at the SVN edge, please try R183.

Custom Memory Allocator for Detour

2010-07-09T02:53:00.000-07:00

I just checked in custom memory allocator code for Detour (R176, or once googlecode stops giving me error 500).

I opted for similar method that is used by other open source libraries such as Bullet Physics or Box 2D. I initially wanted to use an interface which would be passed to each of the allocation functions, but the implementation became really ugly and confusing for those who don't care about it.

If you have a strong case why it should not be handled that way and have good example how to do it better (or pointer to some lib which does it great) let me know.

Thanks to Cameron Hart for initial patch and discussion.

I really don't like how C++ handles memory allocation. It is so half heartedly build into the language. Even the standard library has its' own way of circumventing it.

I'm planning to give the same treatment to Recast too soon.

[EDIT] Added similar support for Recast in R177.

NOTE: From now on the Recast objects (i.e. rcHeightField, rcPolyMesh etc) are required to be allocated and freed using special functions (rcAllocHeightfield() and rcFreeHeightField() respectively). The samples are up to date, in case of confusion check them out.

My Paris Game AI Conference Presentation

2010-07-07T11:13:00.000-07:00

I have now successfully vacated my vacation, purged the most urgent work related queue, and finally got some time to clean up the "slides" from my AIGD10 presentation. Without further due, here's link to the presentation code and executables for Windows and OSX:

AIGD10_MikkoMononen_NavLoop.zip

Use right mouse button to navigate the presentation. Some of the diagrams are interactive, I have included some usage notes below them. It is not meant to be intuitive, just a quickly hacked version of what I hope powerpoint would be :)

The code is quite ugly at points and probably not as efficient as you might like. I have tried to make comments around the important chunks of code where things need improvement. I left some things unoptimized for the sake of readability.

I'm still wondering what might be the best way to transcript the presentation. Here's quick overview of the navigation loop idea.

Navigation Loop

The idea of navigation loop is to cover all the things from A* to velocity selection which are needed to make character move in the world. One of the main goals was to make the agent movement as flexible as possible so that you can concentrate on movement styles or even multi-agent navigation instead of focusing all your energy to try to stay on path (that naked tight rope dancer is that).

Your system will get horribly, horribly, horribly convoluted when you try to follow (linear) spline path and especially when you mix and match collision representations!

The path to the goal is represented all the time as linear array of connected polygons. We never find straight string pulled path to the goal location. This linear array of polygons is found before we start to move the character. You can use your favorite search method to do that. It probably will be A*, I use breath first search in the demo.

Foreach (Simulation Step) {

At each simulation step you first calculate the next corner to move to. This can be implemented efficiently using the Funnel Algorithm. Instead of trying to stay on path, we can always query the next sub-goal towards the target using Funnel Algorithm.

The next step is to apply steering. The demo contain a couple of different styles from robotic straight path moving, to smooth path movement to drunken movement.

The next step is to move the agent. This is done so that the agent is always constrained to the navmesh. The result from this movement step is a linear array of polygons that we visited through when we moved the agent [1].

As final step is to finally fix up the corridor based on the visited array. Most of the time this fix up will shrink the path corridor, but in case the movement lead the character outside the corridor, new polygons will be added in the beginning of the array.

The result of this loop is that no matter how we steer, we are always able to query the next subgoal. If the steering is not totally stupid, the agent will reach the target with certain probability.

Later in the presentation you can find how to extend the loop to contain velocity planning stage.

Data Dependancies

The navigation loop idea assumes certain things about the data. The dynamic obstacles are always assumed to be traversable in one way or another. The system tries its' best to resolve collision conflicts, but in certain cases you need to detect dead-locks and figure alternative ways to handle them, i.e. disable collisions or use special animations to switch places.

The local velocity planning cannot deal with local minima (pockets, U-shapes, etc). If you have larger or more complicated obstacles they need to represented in the navigation graph.

Conclusion

I'd like to thanks David Miles and Thomas Young for laying down the ground work on their earlier articles and talks. I have not seen similar complete system represented before, but I don't claim it to be particularly unique. Such holistic systems as quite common in motion planning literature.

The sort of "anti-points" of this presentation were: 1) A* != navigation, 2) (Linear)Spline is horrible representation of a path. Unfortunately I know that the old fragments of wisdom on navigation will stick with us for years to come .

___

[1] I have blogged a couple of times about constrained movement along navigation meshes. I think the idea is sound, but I'm still figuring out a couple of implementation details.

Firstly, the idea works really when on triangles, but not so well on polys.

Secondly there are certain cases where the demo implementation fails when the next clamped location is at a vertex and both of the neighbour edges are valid exit edges. Need to have better heuristic for this. The system is always able to resolve this the next update, but it is annoying nonetheless.

Greetings from Paris Game AI Conference 2010

2010-06-29T09:15:00.000-07:00

The title image is a bit of an insider joke to those who had the pleasure to experience the technical problems of my talk.

I spent last week in Paris. Three of those days I spent with fellow game AI devs at Paris Game AI Conference. It is a rare situation to meet so many talented and enthusiastic people. I also had talk at the conference. I will post more about that soon, along with the demo and the slides. I think I will write more detailed posts on the topic too.

Bjoern has good coverage of the talks on other blogs and sites, I'm just going to give you few observations.

Empathy and AI

I had the feeling that this year there were more veteran devs in there–Bruce Bloomberg, Ken Perlin, Noah Falstein, just to name few. My big take away from them was to design with user experience in mind and engineer the simplest possible solution to achieve that.

That is, rather than asking if you should use behavior tree or finite state machine, you should ask what is that you want the user the experience and then work it out the easiest solution from there. It is not easy, though. I think such problem solving skill comes with experience. You sort of need to have a feeling of the potential solutions and their strengths. I think Ken's advice is really good rule of thumb, create the simples possible solution first and iterate from there.

You get a good head start by thinking the problem from the users point of view. For example, what kind of feedback is needed to understand the AI, or what kind of interactions you want to use to have with your AI?

Mikael Hedberg had interesting talk how that thinking evolved in the case Battlefield Bad Company. For example they measured that an average screen time of an AI is about 5 seconds. If the death of an AI opponent takes approx. 2 seconds, it is worth putting quite a bit of effort to get that part right.

Good death and hit reactions is the key to make the AI opponent to feel good interactive toy. When working on shooters, just make that awesome first. And while the designers are having good time killing all the foes, add some magic to make them fight back better.

Bruce Bloomberg's talk was also great example of this mindset. I don't think I can ever be so honest about how to simplify the content creation process and the technology based on how the player perceives things as they have been.

Few months back, there was a video of a magician called Jamy Ian Swiss circulating the nets. He used the word empathy to describe this property of user experience driven design. The video is worth watching.

Gameplay vs. AI

Another really welcome development I saw was how people categorize AI programming. In past there usually has bee really clear cut between what belongs to AI and what belongs to gameplay. It seems that a lot of people, from designers to programmers, consider game AI to be a broad concept.

And that is true! In current games the concepts from AI are being applied very broadly across all the gameplay related things from audio to animation. I think this is very good change. The biggest advantage is that the solutions that were before only "available" to AI programmers can now be used to solve other problems too. Sometimes the barriers are in our minds.

It was also interesting to note that this year most of the people were using really simple solutions to their problems. It may have been also the result of Alex's great choice of talks. Most people were using (hierarchical) finite state machines instead of more complex solutions. The reason could be that many talks were biased towards game characters, but it also resonates with the aim to find as simple as possible solutions.

All in all, it was awesome conference, can't wait to get there next year! Big thanks to Alex and Petra for all the arrangements. I'm going to enjoy the rest of my vacation and work hard next week to put the demo and code online.

Stealth Mode

2010-06-17T04:33:00.000-07:00

I have been a bit in a stealth mode the past months. It has been less about doing something I cannot tell you about, but I have just put a lot of time and energy into finishing up my local navigation research and preparing a (hopefully!) kick ass presentation about it for the Paris Game AI Conference next week. The image above is a little teaser screenshot from my presentation.

I will make the presentation available after the conference along with the demo code. So that might be something to look forward to. More about that in few weeks.

I'm also planning to update Project Cane at some point this summer after I clean things up a bit. Project Cane was basically my testbed to test different local avoidance ideas. It will also come with the local navigation grid code I blogged earlier. It'll be bunch of proto code, but maybe someone will use it useful too.

Then at some point I will start working on multi-agent navigation which will be part of Recast & Detour. My current idea is that it will be separate library, just like Recast and Detour are separated but related. There will be some glue code in form of examples which will show you how to use them together.

I hope to see many of you in Paris next week, if not, stay tuned for the presentation :)

Towards Better Navmesh Path Planning

2010-05-31T03:10:00.000-07:00

As many users of Detour have noticed, navmeshes sometimes create extra detours in the paths. This is due how the cost of traversal between different polygons are calculated. The distance to travel from one polygon to another is often approximated either calculating the distance between the centers of the navmesh polygons or, between the edge midpoints of the navmesh polygons. As seen on the above pictures.

Edge midpoints is slightly better in practice, but both will create odd paths when you have long thing triangles or large polygons next to smaller polygons.

There is a nice recent paper Shortest Paths with Arbitrary Clearance from Navigation Meshes which describes another method based on visibility. I'm itching to try that out!

That paper also reminds me why Recast subtracts the agent radius before building the navmesh. It is just really complicated to find thick paths. Even just selecting a valid end point is really complicated matter.

[EDIT] Here's how the visibility optimized heuristic should work (heuristic #3). The idea is that if there is direct line-of-sight from the current node (S) to goal (G) via the next edge (e), then the node at the next edge will be placed at the intersection of the edge and segment SG. Else, the node is placed at the vertex which is closest to G. (The picture below assumes that the node locations are calculated and cached as they are encountered.)

Constrained Movement Along Navmesh pt. 2

2010-05-27T11:24:00.000-07:00

I have been really busy recently at work, with my Paris presentation and some other projects of mine. That has taken its' toll on the frequency of the blog posts too.

have few hours extra time, I though I'd blog a little bit about a problem in my old code I tried to solve just recently. Very little discussed topic and one of my favorites, moving along navigation mesh.

—

The goal of the movement code is to solve the case of moving constrained to the navigation mesh boundaries. Since the walkable areas are divided into convex regions we can use this to solve the movement only inside on polygon at a time and then move to the next polygon based on which edge we hit at the end of the current step.

In case the movement target is outside the current polygon, my earlier attempt clamped the point on the polygon boundary, and followed the edge where the point lied on. While this works most of the time and creates nice sliding movement when a non-traversable polygon edge is hit, it also misses some obvious cases.

The Problem

Such example is shown in above picture. The blue arrow indicates the desired movement delta, and the location labeled 'nearest point' shows where the old nearest-point-on-boundary method would move the character. If the bold edge was connected to the next polygon where the agent is supposed to move to, the test to see if we can move to there would fail when using the old method, even if there is obvious line of sight to it.

Improved Solution

An obvious choice would be to use line intersection or ray-casting to check if there is edge crossing the movement. Instead the new solution still avoids using raycasting since there are some corner cases which are hard or just annoying to handle when using intersections (i.e. hitting vertices and parallel edges). The basic idea of the improved old method is as follows.

If the movement target is inside the polygon, we just accept the new target location. If the movement target is outside the polygon, we first detect which edge the movement delta crosses on its way to the target location and follow the edge if it leads to the next polygon or use the old method if we hit obstacle.

Finding the crossing edge can be easily figured out by testing if the target is inside the sector formed by the movement start location and each edge at a time. This test can be quickly one using using 2D cross products. Dashed lines in the above picture show the sectors.

If the found edge (or its neighbour if we clamped to either end point) is connected to the next polygon to move to, we move the current location to the nearest point on the edge and continue to the next polygon and start the iteration over.

If we instead hit an edge which is an obstacle, we move current location to the nearest point on the boundary of the polygon from the target location, just like in the earlier algorithm, to get the nice sliding movement.

More Woes

There are some cases when the start point is not exactly inside current polygon. This can be because of the floating point accuracy or because some external collision resolution pushed the point away from the mesh or something similar. It is desired that our method works even in that kind of cases.

In case the start location is outside, the trick is to first clamp the start location to be inside the polygon and proceed as before. That's it! Because of the floating point accuracy, there is still need to add a little bit of slack into the sector test so that it handles the case where the start point lies close to the boundary.

—

Handling corner cases like this is really important when building robust navigation system. The earlier method was usually not a problem when you would use small delta movements, but it happened sometimes. It should not happen. Not even in 0.01% of the cases. Nothing is more annoying than that you have a valid path which cannot be traversed.

The Design Evolution of Zen Bound Level Tree

2010-05-03T02:35:00.001-07:00

While cleaning up yesterday, I found some old sketch books. Some of then are from the era I was working on Zen Bound and early incarnation of Recast.

I thought I'd collect some sketches and screenshots how the Zen Bound level selection tree came to be and put them in a rough timeline. It was really hard process for many reasons. The total time span across about half a year, so many at many times we were diving in muddy waters. Now in retrospect it looks quite a bit more coherent process.

Here's the image, it is really wide image, zoom in!

The Moment You Get It

2010-05-02T23:28:00.000-07:00

Pretty much every on project I have worked on–which have succeeded to a degree–I have had a moment when I know that it is going to work. The above image, named navtest.png dated December 3rd 2008, was the point when I knew that Recast is going to work.

Up to that point it had been a huge struggle to find a way to partition the surface. Based on the previous incarnations of the same idea (there were 2 or 3 version before that, depending how I count it) I knew that the the triangulation can easily become the bottleneck of the algorithm. So I worked really hard to reduce one dimension from the problem, and eventually it paid out.

The following months after that it was a cake walk to add tracing the contours, simplifying them and finally doing the triangulation. Four months later March 29th 2009 I made the first commit to Google Code.

On Writing

2010-04-30T00:35:00.000-07:00

The lack of the updates on the blog recently has been mostly due because I've been writing my Game AI Conference presentation. I have done tons of research and prototyping the past 9 months, and now it has been time to draw conclusions and somehow wrap things up.

Whilst doing so, I have tried a couple of new work habits too. I'm one of those people who has a bit hard time concentrating on writing. The words just don't make sense to me. Heck, I did not even pass my A-levels in Finnish language.

I think it is mostly dyslexia, I'm one of those people who read one letter at a time, getting stuck in the curves of the letters and wander off to wonderland–unless you go and scramble all the letters the words. When I first read about it, it was a post at Slashdot, and I got scared because I suddenly read one story so fast.

A Thousand Word Head-start

Over the years one way to escape that has been to first draw a picture or diagram about the stuff I'm about to write, and then just explain what I see in that picture. I used to be graphics designer, and my favorite tool for writing was FreeHand, yes that old vector drawing tool.

It allowed me to write pictures, write a couple of paragraphs about it, and continue to explain another picture and finally bring them all together and write some sentences to glue everything into a coherent piece.

On the other hand, I enjoy writing using just notepad too. That is, the crappies writing program out there. The lack of distractions allow me to focus to the task at hand.

Google Docs for the Win

When I started to write down the "story" version of my conference presentation, I learned that Google Docs had added a feature to draw diagrams. At first I thought it was the same horrible crap they have in Word, but I thought I'd try it out. To my surprise it worked awesomely!

Firstly, it has good default color palette. Not that crappy 4-bit VGA palette with just horrible colors to choose from, nor that 216 safe web-color palette with too many horrible choices, but a couple of well chosen nice colors with few tints each. Design win!

Secondly, the tools it offers are simple to use and work well. The things that I miss from the image editor are: gradients, boolean operators on shapes, and ability to crop the drawing. I think I can live without, it forces me to leave the picture to a sketch level and keep on writing. Simplicity win!

This means that I have been able to combine the two of my best old best practices. Simple, non-distracting text editor (the flickering of that Save button annoys me, though), and simple image editor, which allows me to sketch a picture and tell about it when I get stuck. I'm visual person after all and sometimes some things are just easier for me to describe with a picture. I'm liking writing again. Now, only if I could fix my English grammar :)

Dear Google, if you are listening, please allow me to write blogger posts in Google Docs, thankyousir!

—

I just got word from Alex, that Game AI Conference 2010 just got bigger and better! The line-up is awesome, and now it has larger venue too. The event was sold out, but you have a second change to be there. You can expect an announcement of the line-up and other news very soon now. See you in Paris in June!

More Accurate Tile Connection

2010-04-22T06:14:00.000-07:00

I just fixed (R162) an old and forgotten bug in tile connection. When I was working on the tiles, there were a lot of things to do, and one thing that was left to do was more accurate overlap test.

At the time of writing the code, I took a little shortcut and make the edge overlap test to use axis aligned rectangles instead of something more accurate. While most of the time this is ok, it fails when a tilted surface is on top (or under) of another surface. In that case the edge check test becomes too liberal.

I fixed this now so that the edge connection test uses tilted rectangle, instead of axis-aligned bounding box. If you get tile border connection error, let me know.

Adaptive RVO Sampling

2010-04-16T00:15:00.000-07:00

I spent a little time trying to bring slim down the sample count of the sampled RVO method, while still trying to get really good accuracy and quality. The above pictures shows two cases brute force and adaptive versions of a scene where the accuracy and quality of the resulting movement is comparable. One takes 890 samples (think 500 would be fair comparison too in terms of accuracy) and another 50 samples. An order of magnitude optimization, my favorite!

The method now takes something between 0.01–0.04ms per agent to calculate (2.4GHz Core Duo), of course depending on the number of obstacles. My goal is to get around 25 agents at 0.5ms per frame, so that is just about there! There are still quite a lot of potential optimizations (remove square roots and divisions, vectorizations, etc) in the sampling code, so I'm quite happy with it so far.

It is possible to run the simulation at lower rate too. I'm currently testing at 20Hz, but the method works well down to 5Hz. I have not investigated on adapting the sample count based on the surroundings, so I think with some cleverness and LOD tricks, it is possible to slim the timings even more.

One more thing to note in the above picture picture is the sampling area. Instead of the full circle around the agent, the sampling area is biased towards the desired movement direction and the radius is reduced too. The rationale behind it is that more evasive movements happen at lower speed. It cuts down the sample count quite dramatically, around 40%.

Well, I think I'll will save some details to my up coming presentation at Game AI Conference 2010 too :)

Geometric vs. Sampling pt. 2

2010-04-07T05:51:00.000-07:00

I made a little test the other day to see what is actually the difference between sharp (geometric) and smooth (sampling) velocity obstacle. The first segment shows hard boundary and the second shows soft boundary.

The code in both cases are the same, but in the first case, the time of collision is threshold to imitate geometric solution to velocity obstacles. If time to collision is < 1.5 seconds, then full collision penalty is applied to the sample, else no collision penalty is added.

In the second case, the collision penalty is inversely proportional to time of collision, making the velocity obstacle to appear softer. Even in cases where the geometric method would totally block the movement, the smooth boundary allows to find the best movement direction.

There are some twitching and bugs in the first segment when the velocity obstacle completely covers the sampling area.

—

On another note, Phil's comment on the one of my previous posts put me thinking. I think he's right. Obstacle avoidance alone will not create believable locomotion. There are a lot of nuances which can be only captured in the simulation if you simulate the perception, social forces, etc.

Instead of turning this project into a behavior simulation project, I will narrow my focus even more. It is such a monster research field already. I don't think an individual can successfully research and get something done in the human/crowd behavior simulation stuff in reasonable time.

Multi-agent obstacle avoidance is one of the sub-problems, and I'm going to focus on just that. I can later build some behavior stuff on top of this research if I choose so. Actually acknowledging that there is some higher logic above the obstacle avoidance, allows me to leave some things unsolved and expose them as parameters of the model.

For example if the agent always chooses the fastest possible speed, the result is rush or panic like behavior. If you always choose the nearest speed towards your target, the agent appears shy, or stubborn.

Even if I felt a bit despaired the week following Phil's post, I think it has really helped me to define the problem I'm trying to solve more clearly. Sometimes, it is actually harder to find the problem than to solve it.

My Favorite Protyping Environment

2010-03-25T05:38:00.000-07:00

We kinda pioneered this idea with Kimmo of Mountain Sheep some moons ago. Before that I always used to have 1MB DebugDrawProtos.cpp which was hooked to my current game where I had all my protos hidden behind a console var :)

The idea is simple:

You have a simple project, where you can add one .cpp file and it will compile and appear as a new prototype to choose from when you start your application.

In order to make the threshold of adding something new low, all the protos are based on a simple base class, which has init(), update(dt), and draw() functions. Sometimes I customize this, if I'm prototyping just one feature, like with Project Cane.

This allows me to quickly create new sketches to try a bit alternative version and do AB testing between the two. Add IMGUI into the mix and you can have bunch of parameters to tweak too in no time!

This is how Project Cane is structured too. I have over ten or so different methods prototyped currently (will release it after GameAIConf) and I don't need to hesitate to add something new when I read a paper and get some crazy stupid new ideas while walking to work.

Detour Serialization API

2010-03-25T05:14:00.000-07:00

I implemented some helpers to make the Detour navmesh data serialization simpler. I chose to simplify the method I disucussed in my earlier post. A bit more for you guys to implement, but the feedback was that most people would not use my advanced features anyway. Once you get to the point of making save games and run into a problem, let me know. I try to improve the API.

Detour API Changes

This change induced a couple of API changes.

First you will notice that the init() function has changed:

    bool init(const dtNavMeshParams* params);

I simply moved the parameters to a struct, the behavior is the same. I also added a function to return the init values, so it makes easier to store the navmesh state.

Second change is in addTile():

    dtTileRef addTile(unsigned char* data, int dataSize, int flags, dtTileRef lastRef = 0);

The tile coordinates are gone, they are now stored in the tile data instead. So they need to be passed to the dtCreateNavMeshData instead:

        params.tileX = tx;
        params.tileY = ty;
        ...
        if (!dtCreateNavMeshData(&params, &navData, &navDataSize))

The obscure boolean flag is gone now, and I added an enum flag instead (DT_TILE_FREE_DATA). Much more readable now.

There is new paramter too, lastRef. It can be used to put the tile at specified location and to restore the salt. This ensures that dtPolyRefs which are stored to disk will remain valid after a save game.

You will also see that removeTile() lost the coordinates too:

    bool removeTile(dtTileRef ref, unsigned char** data, int* dataSize);

The function uses tile reference to specify which tile to remove. I added a bunch of accessors to convert between tile pointers and refs and to query tiles at certain locations.

This allows to save and load tiles without loosing the navmesh state. See Sample_TileMesh::saveAll() and Sample_TileMesh::loadAll() as an example how to use this new functionality to save and load a whole dynamic navmesh state.

dtMeshHeader now has userId field too, which can be used to identify a navigation mesh, and you could load it from your resource pack instead of reading and writing the whole navmesh with your save game.

Delta State

New addition to storing navigation mesh structure, I added functionality to store just a navmesh tile state. This is useful if you change the polygon area type or flags at runtime and wish to restore that state after you have loaded your level.

First there is a function which returns the amount of space (in bytes) which is required to save the stave of the tile:

    int getTileStateSize(const dtMeshTile* tile) const;

Now that you have allocated a buffer (you may want to allocate just one buffer which is maximum of all the buffer sizes and reuse it), you can fill it with the data using following function:

    bool storeTileState(const dtMeshTile* tile, unsigned char* data, const int maxDataSize) const;

And the just dump that data to disk.

When you want to restore the state, just read the data and call this functions:

    bool restoreTileState(dtMeshTile* tile, const unsigned char* data, const int maxDataSize);

That's it. A little less automatic than what I hoped. Save games are special, and when to store and what is so game specific that I don't want to build too much of that into the core library.

Geometric vs. Sampling

2010-03-23T01:56:00.000-07:00

Inspired by the relative success of the sampled hRVO thing, I though I'd dust off my old ClearPath proto and try out how it would compare with the sampling based method.

I have to admit that the recent ORCA explanation video also sparked some gas too. I think I got the ORCA thing finally after seeing it in that video.

Without further due here's the video.

Implementation

There are a couple of tricks I added on top of ClearPath. I use similar side bias as HRVO uses, that is based on the velocities and location of the objects, one side of the VO is expanded. It helps the agent to choose one side and reduces the side selection flickering.

Another trick I added is that I clamp the VO cone using a spike instead of a butt end like they do in the ClearPath paper. This makes the avoidance much smoother as can be seen in the head-to-head examples. It adds much needed prediction Clodéric mentioned in the comments of my last post.

I used different time horizon for static and moving obstacles, this allows the agents to move close to the walls while avoiding each other. This is quite important to get good behavior in crowded locations.

The sudden movements are caused by thin sliver section being opened and closed based on neighbour movement.

Geometric vs. Sampled

In many cases the geometric methods are much smoother than any sampling method. I think its biggest drawback is that the result is binary. You're either in or out. But that is also its strength too making the results accurate. The binary results also mean, that it is possible to get into situations where there is no admissible velocity at all.

Another con of the geometric method is the velocity selection. A common way is to just move the velocity to the nearest location at the border of the velocity obstacle. On crowded cases this results dead-locks as can be seen in the video too. I'm pretty sure that if the floating point results would be super accurate, the dead-locks would never resolve.

You can see similar clogging, which is present in my video, in the ClearPath video too (at the time they turn the speed to 10x).

The sampled VO looks smoother too, especially around the tip of the cone. In practice this means that you are less likely to run into situations where there is no admissible velocities. You will get high penalty for velocities which will collide with another agent, but sampling allows you to take the risk.

Sampling also allows to combine multiple different weights when calculating the best velocity. This allows a bit more interesting methods to smooth out velocity selection.

I'd love to see an academic paper which compares the pros and cons between these two methods and educated conclusion. Too bad most papers present their new method as the best thing since sliced bread and fail to address the cons properly.

Conclusion

The sampling method looks really good and smooth when I have 129x129 samples (like in the example picture above), but that amount of samples is totally impractical. I think sample counts around 200 start to become acceptable, I'd love to have less. I will try to see if I can cook up some wacky stable adaptive version to reduce the sample count.

I think the geometric method could be improved quite a bit if I could figure out better method to clamp the velocity to the boundary of the VO. Nearest point is evidently not good enough.

I do like both methods. I will continue trying to fix the cons of both as time permits. And I have a funny feeling that one of these methods might be good enough for a triple A quality agent movement. Well, that would still lack the animation bit, but that is another story.

Custom hRVO

2010-03-21T04:41:00.000-07:00

I have tried to pick up my ever growing queue of interesting local avoidance / velocity planning methods. There are certain things I liked about my TOI-sampling scheme, but the results were not quite what I would like it to be.

One of the things that initially got me into creating the TOI-sampling scheme was an assumption that it is good idea to move at maximum velocity most of the time. In practice this seems to be a faulty assumption. It creates a rushing behavior, much a like a headless chicken running around. Especially in crowded situations.

So one thing I have have been pondering is that what might happen if I just removed that assumption and used huge amount of samples instead to test different speeds too. Much like what RVOlib does.

You can see the results in the above video. I think it is much improved now. I used the sample scoring scheme as my previous TOI sampling used. The good thing about it is that it handles all kinds of nasty things really well.

One problem that this custom hRVO suffers is aliasing. The H is in lower case as the method does not quite use the hybrid-RVO method, but does has similar side bias as HRVO does. As clearly visible from the take over situation with 4 agents, the agents favor to pass each other from right. This reduces velocity selection flickering a lot in head-to-head and overtaking situations.

Another trick I added was to favor velocities close to the current velocity. In my previous attempts this has always resulted the agents to favor the wrong solutions too much, resulting cases where the agents hug each other each other, skip towards the sundown and live happily ever after.

In this experiment I also used the pathfinder from the previous blog post to avoid static obstacles.

Anyways, I think this was a successful experiment, even if not completely practical because of the huge number of samples per agent. Inspired by the Geometric Methods of Multi-agent Collision Avoidance video, I think I'm going to try the ORCA method the next to see if I can get similar quality with cheaper calculations.

Local Navigation Grids

2010-03-19T02:26:00.000-07:00

I have tested several different methods for local obstacle avoidance over the past months. A little less recently, as I have been finishing a game, though. There is something that I really like about the Uncharted way of mixing and matching navmeshes for global search, and dynamic grid for more local path queries.

There is one potentially nasty thing about that combination and that is what to do when the local grid says that the path is blocked, but the global navmesh disagrees. I'm going to sidestep that question by making an assumption that all the stuff that is not in the global navmesh can be traversed some way. Let it be moving around, kicking or putting it on fire.

Implementation

Even if the method has some problems, I thought it was worth the try. I limited my implementation to a small grid which follows the agent. The idea behind this is that the grid only tries to solve the pathfinding problem between two global navigation nodes. In case of navmeshes this area would be the area of current navigation polygon, if you use waypoints, it could be the area between the waypoints.

Simplifying the Grid

Grids are really simple on what it comes to creating obstacles. The horrible side effect of grids is that they create huge graphs and that shows in performance. Since we are using small grid, something between 20x20 to 64x64 probably suffices, this is not a huge problem, but 64x64 is still 4096 nodes to be searched with A*.

There is one simple trick we can do to reduce the node count drastically. After the grid has been build, we simplify our search representation by storing the grid as RLE spans (oh yeah, I'm big fan of RLE!). In practice this reduces the node count from N^2 to 2N. In our node grid range (N=20..64), that means at about an order of magnitude less nodes!

(I do remember reading some GDC slides which described the same trick used by some RTS, but I could not find the reference.)

The side effect is that the cost calculations become nasty and messy. But let's not care about that yet. Instead, let's dumb our search down even further by making more assumptions.

Simplifying the Search

If we were not using the local grid, the path through that area would be a straight line. Instead of building a full fledged A* pathfinder for the local grid we can use this information to create something that will do a good job if the straight line exists, and in any other case it will just get us out of the way of the obstacles and local minima.

I chose to use breath first search for this. Because of the search space representation, it is quite efficient. The open list never gets really big, in practice open list size is usually around 4, and hardly ever peeks past 8 items.

In order to get favor that straight path, the neighbour nodes which are about to be added to the open list are sorted so that the node that is closest to the straight line from start to end point is added first. This bias makes sure that the nodes close to the center line are visited first. The open list is never sorted, just the new nodes that are added to it. It's not pretty, but it works really well in practice.

Finding the Final Path

During the search an index to the parent node is stored and pathfind basically consists of finding the node where the end location lies and tracing back the nodes until we reach the start location. When finding the end node, I choose the closest one that was visited during the breath first search. This makes sure that I get path to follow towards the target, even if the way is temporarily blocked.

Finally, the Funnel Algorithm is used to find straight path through the regions. Funnel Algorithm just needs a series of segments which define left and right edge of constraints to move along the funnel. In our case the portals are the shared edge between two regions.

In my prototype the slowest part was updating the grid, which was stored 1 bit per cell. Updating the grid takes in average 0.026 ms, this includes about 6 segments and 6 agents. I'm sure you can squeeze that number down by vectorizing the rasterization phase. Path query, including string pulling, takes about 0.012 ms in average. All results on 2.8GHz Core Duo. One path query uses around than 1.5kB of memory to store the required search space representation and the final path.

[EDIT] Updated time measurements above, the originals were measured in debug build.

Conclusion

It was interesting to try to the local grid method. I think it has great potential, but the potential problems of syncing the failures from local grid to the global structure are a nasty side effect. I think it might be possible to create an "interface of assumptions", for example the one I explained on the opening sentence, to improve it.

Simple Stupid Funnel Algorithm

2010-03-08T02:45:00.000-08:00

[EDIT] Fixed that example scenario below.

There's a nice master class over at AIGameDev.com about pathfinding: Hierarchical Pathfinding Tips & Tricks with Alexander Kring. That slide about Left 4 Dead path smoothing hit my pet peeve. It makes me sad that people still use "let's trace the polygon edge midpoints" as the reference algorithm for path smoothing. Really sad.

Funnel algorithm is simple algorithm to find straight path along portals. Of the most detailed descriptions can be found in Efficient Triangulation-Based Pathfinding.

Here's implementation of simple stupid funnel algorithm. Instead of using queue and all that fancy stuff, simple stupid funnel algorithm runs a loop and restarts the loop from earlier location when new corner is added. This means that some portals are calculated a bit more often than potentially necessary, but it makes the implementation a whole lot simpler.

The above image shows six steps of the algorithm. Every time we process a new portal edge (the dashed lines highlighted in yellow), we first:

Check if the left and right points are inside the current funnel (described by the blue and red lines), if they are, we simple narrow the funnel (A-D).
If the new left endpoint is outside the funnel, the funnel is not update (E-F)
If the new left end point is over right funnel edge (F), we add the right funnel as a corner in the path and place the apex of the funnel at the right funnel point location and restart the algorithm from there (G).

The same logic goes for left edge too. This is repeated until all the portal edges are processed.

As seen in the above example, the algorithm recalculates some edge several times because of the restart, but since the calculations are so simple, this simple stupid trick makes the implementation much simpler and in practice is faster too.

inline float triarea2(const float* a, const float* b, const float* c)
{
 const float ax = b[0] - a[0];
 const float ay = b[1] - a[1];
 const float bx = c[0] - a[0];
 const float by = c[1] - a[1];
 return bx*ay - ax*by;
}

inline bool vequal(const float* a, const float* b)
{
 static const float eq = 0.001f*0.001f;
 return vdistsqr(a, b) < eq;
}

int stringPull(const float* portals, int nportals,
         float* pts, const int maxPts)
{
     // Find straight path.
 int npts = 0;
     // Init scan state
 float portalApex[2], portalLeft[2], portalRight[2];
 int apexIndex = 0, leftIndex = 0, rightIndex = 0;
 vcpy(portalApex, &portals[0]);
 vcpy(portalLeft, &portals[0]);
 vcpy(portalRight, &portals[2]);

     // Add start point.
 vcpy(&pts[npts*2], portalApex);
 npts++;

 for (int i = 1; i < nportals && npts < maxPts; ++i)
 {
     const float* left = &portals[i*4+0];
     const float* right = &portals[i*4+2];

         // Update right vertex.
        if (triarea2(portalApex, portalRight, right) <= 0.0f)
  {
         if (vequal(portalApex, portalRight) || triarea2(portalApex, portalLeft, right) > 0.0f)
         {
              // Tighten the funnel.
             vcpy(portalRight, right);
             rightIndex = i;
         }
         else
         {
                 // Right over left, insert left to path and restart scan from portal left point.
             vcpy(&pts[npts*2], portalLeft);
             npts++;
                 // Make current left the new apex.
             vcpy(portalApex, portalLeft);
             apexIndex = leftIndex;
                 // Reset portal
             vcpy(portalLeft, portalApex);
             vcpy(portalRight, portalApex);
             leftIndex = apexIndex;
             rightIndex = apexIndex;
                 // Restart scan
             i = apexIndex;
             continue;
         }
     }

         // Update left vertex.
        if (triarea2(portalApex, portalLeft, left) >= 0.0f)
  {
         if (vequal(portalApex, portalLeft) || triarea2(portalApex, portalRight, left) < 0.0f)
         {
                 // Tighten the funnel.
             vcpy(portalLeft, left);
             leftIndex = i;
         }
         else
         {
              // Left over right, insert right to path and restart scan from portal right point.
             vcpy(&pts[npts*2], portalRight);
             npts++;
                 // Make current right the new apex.
             vcpy(portalApex, portalRight);
             apexIndex = rightIndex;
                 // Reset portal
             vcpy(portalLeft, portalApex);
             vcpy(portalRight, portalApex);
             leftIndex = apexIndex;
             rightIndex = apexIndex;
                 // Restart scan
             i = apexIndex;
             continue;
         }
     }
 }
     // Append last point to path.
 if (npts < maxPts)
 {
     vcpy(&pts[npts*2], &portals[(nportals-1)*4+0]);
     npts++;
 }

 return npts;
}

The array portals has all the portal segments of the path to simplify, first left edge point and the right edge point. The first portal's left and right location are set to start location, and the last portals left and right location is set to end location of the path. Something like this:

// Start portal
vcpy(&portals[nportals*4+0], startPos);
vcpy(&portals[nportals*4+2], startPos);
nportals++;
// Portal between navmesh polygons
for (int i = 0; i < path->npolys-1; ++i)
{
 getPortalPoints(mesh, path->poly[i], path->poly[i+1], &portals[nportals*4+0], &portals[nportals*4+2]);
 nportals++;
}
// End portal
vcpy(&portals[nportals*4+0], endPos);
vcpy(&portals[nportals*4+2], endPos);
nportals++;

The cool thing is that this algorithm can be used with pretty much any navigation format. Let it be a grid, quad-tree, connected squares, way-points or navigation mesh. As long as you pass it a list of line segments that describe the portal from one node to another.

This algorithm is also awesome when combined with steering. You can calculate the desired movement velocity by calculating the next few turns and the steer towards the next corner. It is so fast that you can calculate this every iteration just before you use your favorite steering code.

So there you have it. The next person who goes public and suggest to use edge midpoints and raycasting to find more straight path after A* will get his inbox flooded with Cute Overload weekly selection to instigate his pet hate too.

Blind Sighted

2010-03-06T01:50:00.001-08:00

So how do you go about creating a game for a device you have never seen, and all you know about it is an emulator and marketing pitch? The best you can do is to try to minimize the risks.

For Zen Bound we knew from the past that the touch screen transformed the inputs much more tactile. It almost feels like you're holding the object. So in order to guess how the bigger screen of iPad might change the game, I created a 1:1 model of the device to see how it affects it.

The thing we noticed was that at that size you don't use your finger anymore, but the whole hand. Also it helped us to decide the size of the object on screen and to estimate how we might need to change the rotation speed, etc. We will see how these things work out in practice.

So the bottom line is that if you have something unknown, you can transform it to an educated guess by probing the idea with a prototype. It is wonderful how you brain reorganizes stuff when you have some point of view to it. Let it be cartboard box and masking tape.

Save Games and All That

2010-03-05T04:47:00.000-08:00

I have long postponed a task to improve Detour serialization. My use of the word may be a bit wonky, but I mean the business storing and restoring the game state. In case of Detour this also affects how you would initialize the navmesh too.

In pretty much all game projects I have participated in save games have been pretty much retrofitted into the game. It usually results a lot of stupid zombie coding and super long debugging sessions.

When I started thinking about Detour, I have tried to make decision which eventually will make the serialization implementation a bit simpler. That goes into how data is kept internally and what kind of data the API returns. For example there is no pointers, but handles instead.

Handles

Handles are simple abstraction which allows to keep track references to your data. The difference to a pointer is that handles can be invalidated, and you don't need to worry about someone having a reference to your data. The next time the data is accessed, the access will just fail, in which case the user should also invalidate the handle.

Usually in pointer based systems you use some sort of callback system, which tells the pointer owner that something has changed and you should remove the reference. Or it can result things like smart pointers or reference counting.

As the navigation data is solely owned by the navmesh, ref counting and smart pointers would not be a good choice. I also wanted the system to load the navmesh data as one contiguous chunk, which makes stuff like the usual ref counting not really a good choice.

Another good thing about the handles are that they can be stored in the disk as simple integers. These two facts: 1) simple handling of invalid references and 2) simple storing of returned data, make handles good choice when you need to pass handles to internal data through your API.

Detour Handles

Each detour handle contains three values: salt, tile ID, and polygon ID. Tile ID is simply an index to internal Detour tile array, polygon ID is index to a polygon within that time and salt is special ingredient which tells which version of tile we are using. The tile ref is constructed so that 0 (zero) value an be used as null handle.

Detour has fixed pool of tiles it reuses. Removed tiles are returned back to the pool and new tiles are allocated from the pool. Each of those tiles are identified by and index to the tile.

Every time a tile is removed the salt of that tile is incremented. This operation makes sure that if a tile changes, all handles which are pointing to the old data can be detected.

This also implies that if we save a dtPolyRef (the handle Detour uses) to disk when a save game is stored, we need to also restore the state of the Detour mesh when we restore a save game so that the handles are valid after save game is restored.

Saving Game State

The least information that needs to be stored on disk is the tile index and salt of each tile that we have in the current state of the navmesh. This allows the handles to survive the serialization. Additionally we may want to store the per polygon flags and areas too, as the API allows to change that too.

That is still piece of cake. But this is where things can get a bit complicated.

Pretty much every single game I've seen out there uses different way to load assets and even more so how they store and restore save games.

When save game is restored, some games load and initialize a full "section" of the game and then load a delta state on top of that. Some may first store the structure of the level and then load the assets that are needed.

While they both may sound like almost the same, the difference in load performance can be huge. The first, full section loading, allows us to place all the assets in such order that they are fast to load from disk, while the second method may be simpler if the world is allowed to change a lot but may and will result more fragmented loading, in which case seeking may kill your loading performance.

Streaming changes the game a bit too. I have never worked on a game which would have excessively used streaming. So I'm reaching out to you to have a bit better understanding of save game with streaming.

How do you handle asset loading and how do you restore the game state from a save-game?

Current Sketch

My current idea of how the API for serializing Detour navmesh looks something like this.


    dtNavMeshSerializer nser; 
    nser.storeDelta(navmesh); 
    fwrite(nser.getData(), nser.getDataSize(), fp);

The serializer will create a contiguous clump of data which can be directly stored into disk. The process to restore the state is as follows:


    dtNavMeshSerializer ser; 
    if (!ser.init(data,dataSize)) 
        return false; 
    for (int i = 0; i < ser.getNavMeshResourceCount(); ++i) 
    { 
        const dtTileRes& tres = ser.getNavMeshResource(i); 
        navmesh->restoreTileState(tres.tileId, tres.stateData, tres.stateDataSize); 
    }

This assumes that the structure of the navmesh has not changed in between. If the structure may change, you will need to load the tile data before restoring.


    dtNavMeshSerializer ser; 
    if (!ser.init(data,dataSize)) 
        return false; 
 
    dtNavMesh* navmesh = new dtNavMesh; 
 
    if (!navmesh->init(ser.getInitParams()) 
        return false; 
 
    for (int i = 0; i < ser.getNavMeshResourceCount(); ++i) 
    { 
        const dtTileRes& tres = ser.getNavMeshResource(i); 
        int dataSize = 0; 
        unsigned char* data = 0; 
         // Load data from disk.  
        if (!m_assetMgr.getNavmeshTileData(tres.resourceId, &data, &dataSize)) 
            return false; 
        navmesh->addTile(data, dataSize, false, tres.tileId, tres.tileSalt); 
         // Restore state  
        navmesh->restoreTileState(tres.tileId, tres.stateData, tres.stateDataSize); 
    }

Note how the addTile looks different than currently. The tiles don't actually make any sense in random order, so in practice there is no need to pass the tile x and y coordinates when tile is added. This data can be stored in the tile header and acquired from there. Also not that tile ID and tile salt are also restored when tile is loaded to make sure the handles remain valid. That m_assetMgr is your custom asset manager, which will actually handle loading the navmesh data. This example also assumes that the asset manager handles allocating and releasing the data.

In case you use Recast to dynamically create the tiles you can use serializer to store the whole navmesh data too.


    dtNavMeshSerializer nser; 
    nser.storeAll(navmesh); 
    fwrite(nser.getData(), nser.getDataSize(), fp);

Restoring the state would look something like this:


    dtNavMeshSerializer ser; 
    if (!ser.init(data,dataSize)) 
        return false; 
     
    dtNavMesh* navmesh = new dtNavMesh; 
 
    if (!navmesh->init(ser.getInitParams()) 
        return false; 
 
    for (int i = 0; i < ser.getNavMeshResourceCount(); ++i) 
    { 
        const dtTileRes& tres = nser.getNavMeshResource(i); 
        navmesh->addTile(tres.tileData, tres.tileDataSize, true, tres.tileId, tres.tileSalt); 
    }

This code also restores the tile ID and tile Salt so that handles remain valid, but it does not store state, since the tile data already contains the state data too.

Conclusion

My ideas towards implementing the serialization are getting together. I'm requesting comments. Each game has unique requirements for storing save games and loading assets. There is no way I can please all, but I can try to make it little less painful for as many of you as possible.

Please, let me know if I overlooked some scenario with my sketch. And also please share how do you handle asset loading and how do you restore the game state from a save-game? If you don't want to share it here in my blog, feel free to mail it to me too!

Power of Less

2010-03-01T23:55:00.000-08:00

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:

Set limitations
Choose the essential
Simplify
Focus
Create habits
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

2010-03-01T01:57:00.000-08:00

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

2010-02-12T06:50:00.000-08:00

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

2010-02-09T08:23:00.001-08:00

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

2010-02-05T12:36:00.000-08:00

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

2010-02-05T07:28:00.001-08:00

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

2010-02-01T06:08:00.000-08:00

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.

Fresh Start for Areas

2010-01-31T07:40:00.000-08:00

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

2010-01-29T02:36:00.000-08:00

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.