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.