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.
Detour Implementation
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.
Future Improvements
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.
Conclusion
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?
I've been using a re-pathing approach, because my agents are following other agents quite closely and I doubt the repathing will actually be that expensive (given they are only really ever one or two navpolies away at most) most of the time they are on the same navpoly anyway.
ReplyDeleteI dont repath continuously, but sample a new position every N seconds and move towards that, but it does have issues with agents that "lag" that extra amount of time before following that is pretty obvious.
I think for the case of "following", then you're case of path-corridor fixup should work well. But in the case of "chasing" it would break down as the images show. Basically following implies you want to take the same path as the previous agent (swat guy following his squad), where as chasing (swat guy following a perp) is a different use case, in that area I think I would replan, because you actually WANT the shortest path to your target and in some situations that means you literally change direction.
Imagine you are playing a game as a kid. You are chasing someone, you both stand on the opposite side of an obstacle and the goal is to touch the other kid. Of course its actually quite normal to get aliasing as you try and follow the other kid. Every twitch they make towards a direction should be matched by a change in your direction.
So to me the intent is quite different.
How about getting rid of the last example like this:
ReplyDelete* Whenever a path segment is calculated, you also calculate a "zig-zaggyness" value and store that as metadata attached to the path segment.
* When expanding your path with a new calculated segment, recalculate the "zig-zaggyness" of the total path.
* On path expansion, compare the "zig-zaggyness" of the total path to the average "zig-zaggyness" of the segments making up the path. If the difference goes beyond a threshold, recalculate the whole path.
Hey Mikko,
ReplyDeleteSurely in the ideal following case, you would want to somehow concatenate the path of follower+followed so that the follower doesnt have to spend time computing a path that is already calculated. Fixing up its own path from the previously followed path (like each path is a sliding window and you want to create an overall window which contains both paths).
Adding offset following really complicates things though.
You got me thinking though, how often can we actually reuse path data? I suppose its a function of the proximity of the agents and the overlap of the paths the agents follow.
Phil, good points. Chasing is different than following. I would even say, that chasing and intercepting would be different algos too, even if related.
ReplyDeleteThe good thing moveAlongMesh() vs. A* is that if the target does something stupid, like leaves the navmesh, may end up visiting every single polygon. Move along returns in guaranteed time.
Angryant, how would you calculate that? Or implement it efficiently :) For the open areas specifically you could test that if the corner vertices are border vertices or not and react based on that. Like try to use walkability raycasts to optimize the path further.
Phil, moveAlongMesh() can be also used to calculate the offset from a formation center, then you would follow that point. It is awesome tool!
ReplyDeleteHow often we can reuse path data *is* cache invalidation problem, thus very complicated indeed :)
Why not simply add a value which indicates how many nodes to throw away?
ReplyDeleteExample:
Path is [node-list] 1->2->3->4
where the agent is on node 1 and the target is on node 4.
Now the target moves from node 4 to node 5.
If the value is set to zero we are looking for a shortest sub-path from 4-5.
If the value is 1 we are looking for a shortest sub-path from 3-5.
...and so on
That way it's possible to set the value to what is more important in your case:
short path to target VS speed
@Phil Carlisle: Instead of using a timer, I keep track of the dtPolyRef that the dynamic end position is over. When the dtPolyRef changes I recompute the path. The dynamic end pos is free to move over the surface of the final nav poly without causing a new path to be computed, you are guaranteed to be able to reach it.
ReplyDeleteIt's important to recompute the path if your agents have different abilities - if the agent that's being chased vaults over a barrier and the chaser can't perform that action then recomputing the path is the only safe way to continue the chase.