Happy Holidays!

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!

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

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

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

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

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

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.