GPU Crowd Simulation — John Austin

I worked with John Decorato, advised by Dr. Doug James to build a large scale crowd simulation with NVidia CUDA. The final implementation was able to handle nearly 800,000 simultaneous agents with localized collision avoidance and flocking interactions.

Our system is based on (Passos, E., et al) and uses a highly efficient parallel sorting algorithm to spacially sort agents in a matrix. The system then can find nearest neighbors to any agent in constant time. The key optimization is that this spacial sorting algorithm can be done iteratively, as most agents do not move drastically each frame. In this way, we must only do one sorting pass per frame to keep the spacial martix accurately sorted.

We further implemented OpenSteer on top of the described system to test visual accuracy in practical use cases.

See the following video for a demonstration (though not mentioned, all following scenarios are run at 30fps). Apologies for the poor quality.