- Home /
GPU instancing and collision detection in flocking behaviour simulation
Hello!
I am working on a project that requires me to simulate flocking behaviour.
CPU calculations can't get me far enough
My current approach calculates the flocking using the CPU, which maxes out the amount of possible boids (an object part of the swarm) at around 1500 instances, since each instance has to compare to all other instances in order to create true flocking behavior.
There are some other approaches like Physics.Overlapsphere or using Octrees instead of iterating over a full reference list or making use of ECS.
All of these CPU approaches won't get me over 2k Boids though.... but I need at least 4-5k boids that check collisions or distances to other objects in the scene.
GPU computing for bigger swarms
I have looked into compute shaders for this purpose, there is GPU flocking project out there that makes use of compute shaders and successfully simulates 32k boids at once, which is an insane amount!
However, these simulated instances do not collide or interact with the scene, aka other Monobehaviours. I need my boids to avoid obstacles, which currently works by registering collision and applying an opposite "fear force" onto the steering direction calculation.
My Question
Is it possible to register collisions with those GPU instanced objects? Are there other approaches that would work better, for instance ECS and GPU computing? Any suggestions on how to approach this are appreciated.
To me it sounds like you're using an O(n^2) algorithm to direct your boids... However you've not posted any code so I can't help much with that. What I would do if I were you is to try a different method. This does sound a lot like the algorithm for flocking presented in a book I've read (the algorithm is limited by it's time complexity). I say so because you mention
"since each instance has to compare to all other instances in order to create true flocking behavior."
Something you might try is to have your boids sense ONLY the immediate area about them and let the flocking happen organically via parameter adjustment ins$$anonymous$$d of iterating through your flodk checking neighbors for flocking directions.
So let's try this in an OOP algorithmic approach:
Define your boid script so that it has a reference to a trigger collider attached to itself. Define an ontriggerentered() method as per the unity API, which steers the boid while it has anything to flock with (ie. It is within the trigger sphere of a given radius) and is part of your flock by checking the layer given to the object which called the ontriggerentered () method.
If you want to tweak the algorithm using this same method but you want to limit it's visual range to some degree forward, you can perform the dot product on each object within the sphere within ontriggerentered(), and if it exceeds a certain value ignore the inject on your flocking behavior.
Work smarter not harder! :)
This is actually what I am doing currently, but it doesn't really boost performance. The boids move a lot, thus they get in and out of trigger spheres a lot. When using triggers, you have thousands and thousands of trigger calls every movement update. Physics.Overlapshere is the less resource intensive than using triggers. But still, it doesnt get me above my 2k boids. I need to utilize the GPU.
A huge resource saver was to update each boids movement direction only every 0.2 sec, calculate a future position and interpolate in the update to that position.