I spent quite a lot of time last Friday on trying to fix some cases I had with ORCA and to implement line obstacles. I kept on running into cases which simply cannot be solved using it.
For example I could not solve the case in above picture. Regardless of my effort, I ended up having cases where the segments would block the movement completely. The ORCA planes would be aligned according to the dark edges and they would limit a convex region which is used to clamp the velocity. I think some of the problems might be due to the fact that the navmesh is offset by the agent radius.
I'm anxiously waiting for the next paper which improves ORCA. Until then, I'm sticking with the sampled approach. Which leads me to another thing I tried last week.
Improving Sampling
At the time when I was working on my first iteration of the adaptive sampling for RVOs Phil Carlisle's student Scott Bevin mailed me that he was using similar method in his thesis too.
One main difference between out methods were that I was using a regular grid as sampling pattern and he was using 8 samples on a circle aligned at the movement direction and subdivide towards the best sample. At the time I was too busy with my Paris presentation so I did not have any time to investigate it further.
I tried his method but it did not quite work in crowded situations. There simply was not enough initial samples to get good answers.
But the idea of aligning the sample grid helps a lot! I initially thought that it would cause a lot of problems because it might produce more feedback into the velocity control loop. I think I was wrong. The desired velocity usually is quite stable, so when the pattern is aligned towards it, I did not see any additional feedback effects.
As you might spot from the above picture, my implementation used two rings of 7 samples plus one sample at zero velocity. The inner circle's rotation is offset slightly to get better coverage. Since the samples are aligned towards the desired velocity there is always a sample exactly at the desired velocity too. This makes the overal control very smooth, the jaggies from the non-aligned method are gone.
Conclusion
In practice the new sampling pattern improved the movement through small corridors a lot. The hesitating movement is almost completely gone now. The agents do slow down quite a bit if they approach a choke point from an angle. From their point of view they are almost approaching a wall. Adding that extra sample at the zero velocity improved stopping a lot.
All in all, I'm pretty happy about the results now. Not perfect, but tolerable. I can now finally turn my attention into fixing the remainder code structure issues with the crowd code.
Is that checked in now? Would be interested in taking a look. I implemented reynold local avoidance recently and it produced pretty bad results (I think I fluffed the steering scale somehow to be honest). Sampled method seems intuitively simpler to implement.
ReplyDeleteI've seen people use samples around a sort of expanded arch shape too (bit like the vertical footprint of a hot air balloon if that makes sense?).
Do you take samples for objects that are behind you btw? Feels like from a "social forces" viewpoint that is at least partially desirable, given you can sense close agents even if you dont see them (or remember their trajectory).
Yeah, it's in. The balloon shaped shape sounds interesting. What I'm doing already is that I bias the samples towards the desired velocity. In the above example the bias is 0.4. This reduces a lot of samples and makes large avoiding maneuvers slower.
ReplyDeleteI currently consider up to 6 neighbours around the agent regardless of the direction. In my tests omni directionality improves the behavior in crowded situations as the agents gets pushed away too.
The code is structured so that you feed in the obstacle segments and circles and it will spit out the adjusted velocity. So if you wish to prune the obstacles in different way than I like, you can do that.
I had the same problems with ORCA. In the paper it reads like it's no problem and you can simply use the line segments. Took me a long week to come up with a pretty complicated solution, but it seems stable. However, it does need a lot of preprocessing, which will probably make it useless if the mesh is dynamic. The basic idea is to check which edge might become an actual obstacle for agents that are within a certain cell. But even with this information I have to process some chains of segments further at runtime to find out which segment is the one to check. I don't think I can explain it good in a comment, but the idea is like this: First I find the segments that can be touched from the cell. Then I categorize them in 3 groups: Vertex/segment/chain obstacles. Vertex obstacles are those (parts of) obstacles where only one vertex can be touched (e.g. a "V"-shaped), segment means only one segment can be touched (base of a triangle), and chain means that more than one segment or the vertices between them might restrict the agents movement. This last group needs the realtime processing. Its quite a lot of code and hard to explain without pictures. But also I don't shrink the NavMesh so it might not apply to you at all.
ReplyDeleteI hope I'll find time to put up some of my ideas in the web, like you do.
Regarding ORCA and your obstacles that are offset by the agent radius. I think you would either need to use a different navmesh that was only inset by a very small amount, or do a two pass avoidance scheme - one with very small radius agents versus your obstacles and another pass with the normal agent widths versus each other.
ReplyDeleteSounds like a lot of duct tape :) If ORCA would handle the agent vs. agent case way better than sampling (in all conditions), I might go through the trouble to try to fix the segment case too.
ReplyDelete