Friday, April 16, 2010
Adaptive RVO Sampling
I spent a little time trying to bring slim down the sample count of the sampled RVO method, while still trying to get really good accuracy and quality. The above pictures shows two cases brute force and adaptive versions of a scene where the accuracy and quality of the resulting movement is comparable. One takes 890 samples (think 500 would be fair comparison too in terms of accuracy) and another 50 samples. An order of magnitude optimization, my favorite!
The method now takes something between 0.01–0.04ms per agent to calculate (2.4GHz Core Duo), of course depending on the number of obstacles. My goal is to get around 25 agents at 0.5ms per frame, so that is just about there! There are still quite a lot of potential optimizations (remove square roots and divisions, vectorizations, etc) in the sampling code, so I'm quite happy with it so far.
It is possible to run the simulation at lower rate too. I'm currently testing at 20Hz, but the method works well down to 5Hz. I have not investigated on adapting the sample count based on the surroundings, so I think with some cleverness and LOD tricks, it is possible to slim the timings even more.
One more thing to note in the above picture picture is the sampling area. Instead of the full circle around the agent, the sampling area is biased towards the desired movement direction and the radius is reduced too. The rationale behind it is that more evasive movements happen at lower speed. It cuts down the sample count quite dramatically, around 40%.
Well, I think I'll will save some details to my up coming presentation at Game AI Conference 2010 too :)