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.