So how do you go about implementing a moving movement target? Fire off new path request every frame (too expensive! decision aliasing!)... every few frames (still too expensive! still aliasing!)... when the target moves (it moves all the time, bad optimization!)?
The right answer is that you adjust your path corridor.
The path corridor consists of start point and end point and the list of polygons from the start to the end. When we move our character, we adjust the beginning of the path corridor so that the previous definition holds after the character has moved. We can do the same for the end of the path too!
Take a look at the case pictured at the top of the post. The looting party of three follows the target. The dark polygons represent the path polygons of each agents path corridor. When the target is moved along the navmesh as indicated by the arrow, following will happen.
When the target point is moved, we keep track of the polygons we moved through. Then we "fuse" those polygons to the end of the current path corridor. The fusing process tries to find the shortest common path amongst the two. Sounds complicated, but it is really simple algorithm really.
And that's it! Now we have a new path corridor which describes the navigation from the agents current position to the position it tries to follow.
The code is in SVN R249. If you use the Move Target tool with shift+click it will use the target adjusting instead of pathfinding. Turn on Show Path from the debug draw options to see the effect.
The CrowdManager example supports both adjusting the current path corridor of an agent as well as keeping track of the changes that might happen whilst a movement request is still being processed.
This method of following comes with it own set of cons too.
The method does not try to find the shortest path, it just tries to patch the current path with minimal effort. Depending on your application this may be good or bad.
If you have quit small tile size, this may lead to odd behavior in open fields. Even if there is direct line of movement to the goal, the path will take detour based on how the target moved. The open field case eventually would optimize itself. Since the path optimization distance is limited, the agent will move to "old" direction for some time before the optimizer kicks in.
Patching the path corridor is really efficient way to implement path following. It has some limitations, but they are quite negligible when the follow distance is quite small, like when following player quite closely or when following a formation point.
My recent work on path following has surfaced and interesting problem to solve, that is the path corridor optimization. When the world is constantly in motion–and in games it always is–the quality of the initial path is less and less important. I hope I will have more time in near future to figure out how to optimize the path corridor in certain uses cases.
If the above method sounds crappy and limited, it still does solve the case for moving target for a whole range of the use cases. And did I mention it is really fast?