Multithreaded Boids
Multithreaded Boids
Multithreaded Boids is a Unity Project exploring steering behaviours with data-oriented design. The project simulates 10,000 boids while maintaining a 16.6ms frame time budget.
Due to browser limitations, the WebGL build is capped at 2,000 boids and does not reflect the benchmark data. Download the Windows build to experience the full simulation.
Tools: Unity 6, Unity Jobs, Burst, Profiler and Profile Analyzer
This project instantiates 10,000 boids steering as a flock contained within an invisible sphere. The goal was to keep the frame time lower than 16.6ms by adopting data-oriented design.
I’ve implemented this project using a Game Object workflow to prove that, even without the highly performing ECS paradigm, we can achieve great performance.
Boids are contained within a spherical boundary. Each boid casts 5 directional probes and uses an analytic ray-sphere intersection to detect and respond to that boundary.
When a probe detects an upcoming boundary, the boid calculates a perpendicular steering force to maintain speed through the correction.
Since the raycast methods from Unity's built-in physics system are incompatible with Unity Jobs and the Burst compiler, I implemented a simplified analytical solution for ray-sphere intersection that is multithread compatible and burst-friendly.
A naïve proximity lookup costs O(n²), because each boid needs to check every other boid to assess whether they are “neighbors”. For 10,000 boids, that's 100 million checks.
By partitioning the world into cells, each boid only queries the 27 cells adjacent cells for other boids, reducing the O(n²) complexity down to O(nk).
I applied a spatial hash grid by using the NativeParallelMultiHashMap, because the one-to-many associative array fits the spatial grid needs and being a blittable type makes it compatible with Unity Jobs and the Burst compiler.
Singlethreaded performance was the primary bottleneck for meeting the 16.6ms frame budget, which is why I chose to use Unity Jobs to create multithreaded code.
By distributing the logic across the worker threads, I significantly improved the frame time.
CppCon 2014: Mike Acton "Data-Oriented Design and C++" by Mike Acton
Intro to Data Oriented Design for Games by Nic Barker
Steering Behaviors For Autonomous Characters by Craig Reynolds
Spatial Hash Grids & Tales from Game Development by SimonDev
Ray-Sphere Intersection by scratchapixel
Ultimate Guide to Profiling Unity Games by Sean Duffy