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.
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.
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.