"> UselessGameDev

UselessGameDev logo UselessGameDev title

Just Boids

Fri 18 August 2023 #UselessGameDev
This text is a written version of the video above, with future plans to incorporate graphics and figures for illustration.
As I'm working my way through the backlog of videos that were published before this website, I suggest reading the article alongside the video for a comprehensive experience.

You know what’s useless but pretty in games? Boids. Flocks. Swarms. Schools.

It feels like video games that have extra CPU cycles always want to show it off by having some boids in the background, to show you they’re doing OK performance wise.

So today, we're simulating boids.

How it works

The way boids work is, they don’t have a manager overseeing and coordinating the movements of all the boids together, instead each entity decides where to go and what to do based on its environment, and a set of simple rules.

Let’s define the environment first. Each boid keeps an updated list of neighboring boids. For now we just iterate over the list of all boids in the scene (but we’ll fix that later) and filter it to only keep the ones that are within a certain radius.

var boidsInRange = AllBoids.FindAll(b => b != this
                 && (b.transform.position - transform.position).magnitude <= radius
                 && InVisionCone(b.transform.position));

We also only keep the ones that are in our field of vision, that we can do simply by testing the dot product of the line of sight of the boid and the direction vector that links it to a neighbor.

That’s about it for now. List of friends that are next to us.

Rules

Let’s talk rules. By default, a boid just goes forward without thinking. Each rule will have an impact on the direction by slightly steering the boid.

The three basic rules as defined by the original boids paper are Separation, Alignment, and Cohesion.

Separation is just avoidance, to avoid running into each other, they steer away from the crowd.

The way I implemented that is by having every neighbor exert a force on the boid, the intensity of which decreases with the distance between the two boids.

Sum each of them, and you got your separation steering force.

private Vector3 SteerSeparation()
{
    Vector3 direction = Vector3.zero;
    var boidsInRange = AllBoids.FindAll(b => b != this
                 && (b.transform.position - transform.position).magnitude <= radius
                 && InVisionCone(b.transform.position));

    foreach (var boid in boidsInRange)
    {
        float ratio = Mathf.Clamp01((boid.transform.position - transform.position).magnitude / m_separationRadius);
        direction -= ratio * (boid.transform.position - transform.position);
    }

    return direction.normalized;
}

Next is Alignment. Boids will try to go in the general direction as other boids are going. This is basically the same as the separation rule, but instead of steering away from neighbors, the weighted sum of vectors uses the line of sight vector of the neighbors.
With this rule you kinda see a group behavior emerge all of a sudden, which is pretty cool. Although, they quickly end up all facing the same direction, so we need a final rule.

Cohesion. A boid will find the center of all of its neighbors, and try to head towards that. Which means when they’re all going the same direction like before, if I activate Cohesion, they will sort of head inwards the flock and focus the beam.

That’s it, we have boids. That’s the basics anyway.

Add-ons

What features can we add on top of this to improve the behavior of our flocks?

Obstacles

Firstly, collider avoidance. We’re not running an army of ghost birds here.

The easiest way I found to do this is to fetch all overlapping colliders from the current position, within a certain radius.

And then it works just like the Separation rule, colliders exert a force on boids. It only works for small-ish colliders because you only get the pivot of each collider and not the actual points that are close to you. But it works fine at the moment.

private Vector3 SteerColliders()
{
    Vector3 direction = default;

    // Get all colliders within range
    Collider[] hitColliders = Physics.OverlapSphere(transform.position, radius, m_colliderLayers);;

    foreach (var hitCollider in hitColliders)
    {
        var diff = (hitCollider.transform.position - transform.position);
        direction -= diff.normalized / diff.sqrMagnitude;
    }

    return direction.normalized;
}

For the hard way to do this, which is a lot more accurate, at the cost of some performance, check out Sebastian Lague’s video on boids.

Exploration

And also, I wanted to add a steering rule to encourage exploration. Just to avoid boids swimming around in the same spot.

So I added some sort of fog of war, and got to developing a rule that pushes towards the fog.

The way I did that is by adding a field of… "fog probes". So you have a bunch of probes spanning the entirety of the world, or at least the area that the boids can explore. A probe is simply an object that tracks, using a boolean, whether or not it has been discovered.

If a boid touches it, it toggles.

And then we add a simple rule, that works exactly like the Separation rule but in reverse, boids are attracted to non-discovered probes.

To fetch the probes that are next to a boid, we iterate through the list of every probe and filter them based on a radius, like for the neighboring boids.

And that’s where the problems start.

Problems

You see it’s the second time we iterate through the full list of something to get neighboring objects. And since every boid scans the list of every other boid, that’s an n² complexity, and that’s bad, especially if we want to have, say, 1000 boids. Even for a simple distance check.

And I’m not just saying that as an optimization freak, currently 15 boids run at 3 fps on my computer. That’s bad.

Quadtree

So this is a perfect opportunity, and some might even say I did it on purpose because I like talking about cool data structures, to implement a Quadtree. Yayyy.

What’s a quadtree? It’s a type of tree that helps partition a 2D space, to effectively store and retrieve objects based on their position.

It splits the space into 4 quadrants, and those are also split into 4 quadrants, and so on. And the bottom tiles store a list of objects, in our case boids, that are present on the tile.

And we can prune some of these, for instance if a big tile has no boids on it, there’s no point in splitting it. Basically every tile that doesn’t store objects doesn't need to be split. Also, if there is a single boid in a quadrant, there’s no need to split it all the way down to level, 5 or whatever. We’re just splitting a quadrant when its contents are above an arbitrary capacity threshold where we feel a need to split, for instance, 3.

So to find the neighbors of a boid, we just have to query the list of objects on the same tile, and maybe a few neighbouring tiles. Looking up in the tree is super fast because based on the position, you can progressively narrow down which tile the boid is on. For the complexity nerds, that’s a logarithmic complexity, which is way more acceptable than what we had before.

So we can store boids in a quadtree, and already things are improving because instead of filtering the entire list of every boid in existence to find neighbors, boids now can now find neighbors super quickly.

Same thing for the fog probes, instead of having every boid scan every probe, we can store the probes in another quadtree and have every boid scan an easily accessible list of neighboring probes.

This takes us from 3 fps for 15 boids to 20 fps for 1000 boids.

It’s good, but not good enough.

Parallelization

The next step is parallelization. Right now we’re computing the steering forces of every boid sequentially, when by definition, as I said earlier, each boid is independent from the others, meaning we could have a thread per boid, or more realistically a thread for a batch of 100 boids, doing the calculation, to speed things up.

Now the collider rule cannot be threaded. Physics stuff must be called from the main thread.

But Separation, Alignment, Cohesion and Fog can all be moved to a thread, provided you cache some of the values like transforms on such.

To do this I used the new Awaitables feature of Unity 2023, which allows async functions to be parallelized, among other things. It's a great helper class for async functions which makes them on par with Coroutines, feature-wise.
There's more detailed in the video.

Back to my problem, I set up a kinda janky way to parallelize the computation. I split the load in batches of boids, and created one async task for each batch. By varying the size of the batches, and thus the number of threads, I can find the right balance between many small threads and few large threads.

So I used that, which in my case though is probably not what I should have used because it would have worked better to set up a pool of worker threads using the Unity Job System, but I wanted to try this new easy way to do it sooo…

Results! We went from 20 fps to 45 fps with 1000 boids! That’s pretty nice, we’ll take that. Beyond that we could add some tricks like not updating every boid at every frame, half of the flock on even frames, and the other half on odd frames.

Or we could move everyone to the GPU and use a compute shader because it’s extremely good at exactly what we’re trying to make, and uh… yeah. Maybe one day.

3D

But right now we don’t want to make better boids, we want to make 3D BOIDS! And for this we just have to liberate the third dimension on our boids to allow them to go everywhere, and they should do just fine, provided we convert our quadtree to an octree.

Which is the same thing, but instead of splitting a 2D rectangle into four quadrants, we split a 3D volume into 8 uhhh… octants? It does take a bit of tinkering, especially since I wanted to unify my Quatree and Octree classes under one main class that contains all the common logic, but after that’s done, we can feast our eyes on some mother-flocking birds.

Conclusion

And that’s it, I love boids, they’re cool, it’s nice to see how we can sort of replicate hive behavior easily on our computers and I liked making this, I hope you enjoyed watching as well, and I’ll see you in the next one until then, check out the patreon for the full source code for this Unity project and join the discord to chat about stuff!

Have a good one!

Check these out

Interesting stuff featured in the video and/or more stuff about boids:

Music Credits