Constrained Movement Along Path Corridor

I just added simple path iterator code for Detour. I have been postponing this Detour feature for quite some time now since I was not sure how my recent research on obstacle avoidance would affect it.

Even if path following sounds easy, it can be really hard to get to work on all cases. I've yet to see any good piece of code which does path following robustly. There is a simple stupid case which is really hard to get right, that is, what to do when you encounter in-between path point?

Most code out there just checks if the character is close enough a path point and starts steering towards the next one. The problem is that depending how you generate the steering velocity, this can lead to circling around the path point or if you increase the threshold too much there is a shortcut.

I know quite a few games which have successfully shipped with the most awful path following code out there.

The most inspiring recent method to follow path can be found in Indicative Routes for Path Planning and Crowd Simulation. It feels a lot similar as the distance based GPU heightfield raycasting. While interesting, the method has one failure. In order not to shortcut, the radius of the agent should be reduced from the radius of K. Which in practice creates the silly singularity problem again.

The most simple and most robust path following code would of course just interpolate over the spline, but if you want to do some sort of local steering to avoid other moving agents that will not work anymore.

I don't know the perfect solution, but here's my current shot at it.


Global and Local Planning

I split the navigation into two problems, global navigation and local navigation. This is a common way to overcome the uncertain environment in for example robot navigation research.

The point of global navigation is to find a high level path to the target location. In practice when using navigation meshes this means finding the list of convex navigation polygons which will lead us to the target. I use A* for this search. The global navigation structure is static, but can change to reflect changes in the game world.



The second part is local navigation, it will execute the maneuvers to move the agent from the start location to the goal location via the path corridor.

Since I'm aiming to solve the navigation problem amongst multiple moving agents, I cannot use one shot shortest path generation since its' results will be invalid immediately when any other agent moves. For this reason, I do not find the full straight path spline to the goal. Even if straight path string pulling is really fast with Detour, finding the whole path would just was the processor time.

Instead, on every tick a character wants to move, only few next points (A and B in above picture) of the straight path are calculated. These few path points are used to calculate a velocity to steer the agent towards the target.

This method also ensures that if an agent overshoots to reach a path point, we still always get the shortest path towards the target and prevent silly things like trying to go back to a intermediate path path which we have actually already passed.

In order to avoid the singularity case when the agent is close to one of these path points, the point B is used when the character is really close to point A. This is not optimal, but currently I do not have really good alternative for this. With Detour this will not cut corners, though, because of the way the movement model along the navmesh works.

Moving Along a Path Corridor

The goal of the movement model along navmesh polygons is to move the agent through navigable space, or in case of collision slide along the navmesh boundaries.

In order to keep the whole system robust, the agents are kept and assumed to be inside the navigation mesh at all times. In practice this is not the case. When an agent is close to a polygon edge, floating point accuracy will make the agent to flicker in and out of the polygon boundaries.

The above picture illustrates a case where agent A is moving in the direction of the arrow towards T. Because the movement vector is colliding with a polygon edge, the target location projected on the polygon boundary so the it results sliding motion. There are several ways to do this.

A classic way to do it is to iteratively cast ray (or ellipsoid), clamp it based on the hit surface normal, until the movement is resolved. This method is quite hard to get robust because there are a lot of cases where you need to handle collision between parallel segments.

Since our movement model is supposed to travel inside convex volumes, we use a bit different and more robust method. The whole iterative ray-casting loop can be replaced by finding a closest point from the target location on the boundary of the polygon.

If you want sliding movement inside a convex polygon, that is all you need to do! While this may not be numerically most robust method, the logic to implement this method is robust. We simply move the agent and clamp it to the polygon boundaries. Even if the agent is slightly outside the polygon because of precision, it can be all the time treated to be inside.

This method can be extended to move along path corridor.

• We start from the current navigation polygon (PA), current location (A) and start moving towards the target location (T).
• If the target is inside the polygon, we set the current location to the target and we are done!
• In case the target is outside the polygon, the current location will become the target location clamped to the nearest point on the polygon boundary (B).
• If this clamped position is really close to the portal edge which leads to the next polygon (E), we move the current polygon the next one (PB).
• If the clamped position does not touch the portal edge, we cannot move know that we cannot move any closer to the target and we'll stop.
• This process is repeated until we either reach the target location or cannot move anymore.

The process may sound a bit backwards, but because the way it is implemented we can dodge a lot of robustness issues.

Towards Obstacle Avoidance

The way to extend this to obstacle avoidance is to adjust the velocity. First, the velocity towards the target is calculated as per above description, and then it is adjusted according to your favorite local avoidance method. For example the method described earlier in this blog could be used, finally the resulting velocity is used to calculate the next movement step.

Since the obstacle avoidance may sometimes need to deviate from the corridor, I expect that I need to revise the navmesh collision response at some point. Instead of allowing to move only to the next polygon along the path corridor, it should be possible to move to any neighbor polygon and just append or remove polygons in the beginning of the path. There are a couple of details still, which I have not solved, though.

_

I hope I did not skip too many details while writing this. I just got the last pieces together today while implementing this. The updated code can be found from the Recast SVN at google code. The path iterator can be found in Sample_SoloMesh.cpp, in toolRecalc() method, check the path find tool code. The Windows project is yet to be updated.

[EDIT] Visual studion and Win32 exe updated.