Boids Simulation
Boids are a bird-like flocking simulation similar to cellular automata. The basic rules include cohesion forces that cause the entities to prefer grouping up and orienting in the same direction, and separation forces that keep them from clustering too tightly. The key challenge to performance is neighbor look-up time. While every entity may only consider a handful of neighbors, finiding the nearest ones can be computationally expensive. My solution involves creating a virtual grid of cells, with each entitiy self-identifying it's location in the grid. These positions are put into a sorted list which allows neighbor searching to be limited to the adjacent 3x3x3 sub-grid rather than the entire list. While this approach initially seemed trivial, efficiently implementing it in compute shaders to eliminate CPU readbacks took some effort.
The video above is a demonstration of 150,000 entities simulated in real-time at a consistent 30 frames per second at 1080p resolution, using in-engine performance benchmarking and recording from the same system, using a modern consumer desktop GPU. The simulation consists of five "swarms," indicated by color. Each swarm has a unique set of parameters, such as cohesion and gravity forces. A designated number of entities are given the "leader" characteristic (30 in this demonstration) which causes them to seek out specific waypoints, allowing CPU-side influence of navigation. Every individual entity also carries arbitrary data, such as health, for further simulation influence or gameplay usage. An "attack" buffer and asyncronos "death" read-back buffer are implemented but not demonstrated here.
Note that this many moving individual parts is straining on video compression and causes the scene to look blotchy in video, but screenshots don't do the effect justice.
In practice, performance can be improved dramatically a few ways. Simply having entities outside the camera's field of view dramatically increases performance as real-time occlusion culling is impractical and essentially unused, though I am exploring some ideas to reuse the hard surface collisions planes for this. Additionally, reducing the number of entities to a more manageable number for gameplay, such as 15,000 entities, increases performance to well above typical monitor refresh rates when V-Sync is disabled.
