Multithreaded Boids

Tools: Unity 6, Unity Jobs, Burst, Profiler and Profile Analyzer

Timeline: 80 Hours (Jan 5 – Jan 23)

Ray-Sphere Intersection

Obstacle avoidance contains the boids within a spherical volume. This steering behaviour requires boids to check intersections between themselves and an obstacle.

Since the raycast methods from Unity's built-in physics system are incompatible with Unity Jobs and the Burst compiler, I implemented the algebraic solution for ray-sphere intersection that is multithread compatible and burst-friendly.

Each boid uses 5 directional probes to detect boundaries and calculates perpendicular steering forces.

Proximity-Based Lookup

A naïve proximity lookup costs O(n2), because each boid needs to check every other boid to assess whether they are “neighbours” — for 10K boids, that's 100M checks.

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 compatible with Unity Jobs and the Burst compiler.

Singlethread 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 across the worker threads, I significantly improved the frame time.