Since last time, I implemented smooth steering, drunken movement style and sampled velocity obstacles.
The features are coming together, but the code is still huge pile of mess. I checked in first version (R193) so that the change list does not become too big.
When using tiled navmeshes and many agents, I got quite a bit of problems with agents trying to move backwards to catch up with their path. This happens mostly around the vertices which are at tile corners.
For the time being, I added that raycast trick which tries to optimize the path corridor by checking if there is line of sight from the current location to the corner after the next corner. If so, then the beginning of the path is patched to use the results from the raycast.
The performance is still realtime (it chokes when you have large group next to each other), but I bet it is actually really horrible. Once I get the structure of the code better, I'll start looking at the optimizations.
It generally looks great. However, one problem is that around 2:30 in the video some of the later guys effectively overshoot the entrance to that enclosed area. I guess it might depend how they were animated - if they faced away from the entrance it would look really dumb, but perhaps if they faced the entrance and walked backwards/sideways it might look better...
ReplyDeleteThe orientation of the agent is really interesting problem too. There are quite a bit of information to use there. 1) desired velocity, which comes from steering and in general usually indicates what the agent might want to do, 2) clamped velocity which is the desired velocity adjusted by the VO, 3) actual velocity.
ReplyDeleteOrientation of the agents head is interesting problem as well :) Ken Perlin had some good ideas regarding that, I don't remember them so well that I would dare to paraphrase them.
I think the velocities 1 and 2 or some combination of then is probably going to be pretty good for the head or hips.
I think that all ties into something that is how can you define the style of movement. I don't think there are many general rules which fit all situations, but there might be some general parameters which can be combined to create reasonable agent movement and head/hips orientation depending on the style of movement.
Hi Mikko,
ReplyDeleteI checked out the latest trunk to test the new features. Amazing work you did here!
In particular I tested around ten agents in you dungeon demo level with default settings. This setup becomes quiet slow when the "crowd" of people is moving together.
I´m aware that you did not yet started optimizing the algorithms. According to your own suggestion to navigate agents in a "huge" crowd with fluid algorithms instead of the sophisticated ARVO sampling I´m wondering how Detour could support determining which algorithm to choose and actually call the appropriate one. Or do you think this should not be handled by Detour at all?
The current implementation is using a brute force 31x31 (961!) sample grid per agent. The slowdown comes when you have a lot of agents really close to each other.
ReplyDeleteIn case of 10 agents really close to each other, you pretty much end up in a situation where every agent will sample each other. Currently the number of agents is limited on by distance.
I have created an adaptive method, which only needs about 50-60 samples, and also in practice it is good to limit the number of neighbour agents to 5 or 6 to have some upper limit for your calculations.
Also the neighbour querying needs to get faster too. Currently it is O(n^2) or worse. I'm planning to use local neighbourhood polys + hash lookup to speed up the neighbour finding.
RVO sampling for 25 agents can be done in about 0.5ms using the adaptive method, I hope to get 25 agent simulation including all the path adjustments to about 1ms. We'll see how close I will get eventually! :)
With some LOD control plus parallelizing the stuff you should get better performance.
That sounds great! :-)
ReplyDelete