Multithreaded Boids
Multithreaded Boids
This Unity Project served as a learning experience for data oriented design, spatial partioning and multithreading.
Additionally, I also applied two steering behaviours, flock and object avoidance.
Finally, I made use of the Profiler and Profile Analyser to guarantee my solutions were meeting performance thresholds.
TODO: Explain that the data portraited is related to the desktop version of the demo and not the web version; the web version is ease of viewing experience.
The WebGL version is a single-threaded compatibility build.
For full performance, please download the Windows build.
This project was develop in Unity 6 from January 5th to January 23rd, for a total of 40 hours.
I instantiated ten-thousand boids navigating as a flock contained within an invisible sphere. My 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 still achieve great performance.
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 for updating the spatial hash grid and calculating probes, steering and movement across the worker threads, I significantly improved the frame time of my project.
Performing a proximity-based lookup costs O(n2), because each boid needs to check every other boid to assess whether they are “neighbours”. By partioning the space, such that each boid only queries adjacent cells for other boids, I was able to reduce the O(n2) complexity down to O(nk).
I applied a spatial hash grid by using the NativeMultiHashMap data-type, because it is a one-to-many associative array and a blittable type — therefore compatible with Unity Jobs and the Burst compiler.
The steering behaviour for object avoidance needs to calculate the intersection between a boids velocity and the obstacles surface. Since the raycast methods from Unity's built-in physics system are incompatible with Unity Jobs and the Burst compiler, I coded a method for calculating ray-sphere intersections that is multithreaded compatible and burst-friendly.
The calculations use an algebraic solution which can handle situations where ray origin is inside the sphere. This solution is versatile, but boids are always contained inside a spherical shape, thus I adapted the code to remove conditional branching for other intersection types.
Profiled on a Intel Core i7-9750H CPU @ 2.60GHz.
TODO: Write reflection ection.