On Navigation Robustness

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.