Whilst pondering LogicalError's question to my previous post and sipping that second cup of coffee this morning, I got a pretty interesting idea.
One thing that adds a lot of realism to NPC locomotion animation and can be quite frustrating to implement is something that is usually called as idle-to-move and move-to-idle animations. The idea is that when you start moving, you have special kind of animations which are played before the locomotion animations kick in. This allows the animators to create cool animations which can do turns and have anticipation in them.
The usual implementation problem is: how to make sure that those animations can be played so that the AI is moving in right direction and doesn't bump into things? I've seen all kinds of solutions to this, ranging from just checks is the target point is in navigable idea, to batch of raycasts to iterative collision sweeps.
Navigation meshes will help quite a bit in that process, making the line checks cheaper. The problem is that that check can be too exact. What if you adjusted your target just by 0.745 degrees and you would be able to do your nice animation? Some more random samples? An even harder case is those other potentially moving agents. Usually the grand solution is postponed until it is time to ship the game and the feature will drop into the cut-features list.
The idea I got this morning was that, if the trajectory of the animation can be thought to be relatively straight, we could actually use velocity obstacles validate potential directions and lengths of animations and choose one that fits the best.
The velocity obstacles can be scaled to take the maximum time into account. If the max time is infinity, the VO will look like cone, but as the time horizon is scaled down, the tip will be more rounded and will move further away from the apex (FOVT). You can check more details in the Clear Path paper. This is useful if you need to calculate collision free movement for certain duration of time.
I assume that the multiple VO contains all nearby moving agents as well as solid navmesh edges as obstacles in the follow paragraphs.
So based on the animation, we would calculate how long it takes and based on the end location we could calculate the velocity during the animation. Then we could calculate the multiple velocity obstacle with max time set to the length of the animation and try to find a direction which is closest to the direction we would wish to move and which has exactly the same velocity as we are requesting.
In practice this means that if the target velocity is inside the MVO, then we would pick a point which is at the intersection of the VO edges and a circle which radius is the length of our velocity. Voila, problem solved!
Move-to-idles are usually even harder since we need to hit a point certain distance away from the target we want to reach. Potentially it might be possible to use VOs for that too. An idea could be to place the agent at the target location and maybe inverse all the velocities of the other agents or something weird like that to be able to project set of points which could be available to arrive to the target obstruction free. Or you could just trigger move-to-idle if at certain distance and the VO tells you that the path is clear for the duration of the animation.
Given the idle-to-move idea, of course nothing prevents you to extend that idea for stuff like jumps and rolls and other gameplay animations.
The idea is a bit sketchy still, but I see a certain potential to it. Let's use VOs to solve all our problems! ;)