What are Boids?

The word Boid comes from a shortened version of “bird-oid object”, a term to describe a bird-like object. Just as standard issue birds are programmed to fly around in a flock, boids follow three simple rules to emulate that behaviour.

  • Alignment: every boid attempts to fly in the same direction as other nearby boids
  • Cohesion: boids attempt to stay together
  • Avoidance: boids try not to crash into each other

The actual algorithm will be discussed in depth later on. Before I jump into the technical details, let’s take a look at some boids in action! The simulation below is a very simple implementation of boids. Feel free to play around with it to see what each of the sliders do!

Simple Boid Simulation

Amount of Boids

This slider will change the amount of boids in the simulation.

Boid Rules

Each weight slider determines how important each rule is to the boids, while rach range slider determines how close the boids have to be to each other in order to adhere to that rule.

Cohesion

Weight Range

Alignment

Weight Range

Avoidence

Weight Range


The Boid Algorithm

The simulation above is a simple implementation of boids in javascript using an HTML5 canvas. The algorithm, as mentioned above, employs a combination of three behaviors: avoidence, cohesion, and alignment. First, the algorithm initializes the boids: As shown above, boids are initialized with a random position and a random velocity (the x component of velocity is represented by dx, while the y component is represented by dy). The algorithm then iterates through each boid and applies the three behaviors by adjusting the velocity of each boid.

Below is some pseudocode for the three behaviors:

Cohesion:

Cohesion calculates the average position of all the surrounding boids and instructs the current boid to move towards that average position. This causes large groups of boids to stay together and form a cohesive flock.

Avoidence:

Avoidence moves the boid away from other boids that are too close to it, which prevents boids from crashing into each other.

Alignment:

Alignment causes the boid to move in the direction of the average velocity of all the surrounding boids. This also allows boids to easily stay together and form a flock.


A few more steps are done in order to make the boids behave correctly, such as normalizing their velocity so that they don’t move too fast as well as preventing them from leaving the canvas. Additionally, a velocity is applied to them if they are close to the mouse, causing them to run away from your mouse.

Once I finished a basic boid algorithm, I moved on to apply it in other scenarios.

Another Boid simulation, but with a twist

Boids are pretty fun to watch and play around with, so just for the fun of it, I set up another simulation with some extra rules which allow groups of boids to fight each other (think Boid Wars™). In the simulation below, boids are grouped together and assigned a color. Boids in the same group will try to stay together and follow their group leader. The group leader is responsible for leading the group towards the nearest enemy group. Finally, boids can fire little bullets at each other, and if a boid is hit by a bullet, it dies. Additionally, each group is assigned a random interval for how often they can retarget their enemy and adjust their route, just to keep things interesting. Don’t forget to click the start button below in order to kick off the simulation. Warning: this simulation can be very intensive with a lot of boids. Please use a smaller amount of boids if you don’t want to crash your browser.

Amount of Squads Amount of Boids



So, why do I care about boids?

I started this project partially because I was intrigued by boids, but mostly because of the potential oppurtunity to learn about compute shaders. Compute shaders are a way to write code that runs directly on the GPU, allowing certain processes to be performed extremely quickly. Compute shaders are great for performing a massive amount of simple tasks in parallel, such as calculating the position of a boid.

I began by implementing boids in Unity3D using a simple CPU-based implementation. I then implemented the same boids in a GPU-based implementation using a compute shader. The CPU code is pretty similar to the code I showed above, so I will mainly focus on the compute shader code (which happens to also be pretty similar).

The compute shader begins by declaring the entry point to the program, allowing other scripts to be able to access it: #pragma kernel CSMain

Next, I declare a struct that can hold a boid’s position and velocity, as well as a buffer that can hold a list of boids.

After that, I can tell the compute shader to accept some parameters, such as the number of boids to calculate, their speed, and more.

Finally, I run the boid algorithm in the CSMain function of the compute shader. We can specify the dimensions of the thread groups, which dictates how many threads will be in each group running at once.

The rest of the shader is pretty much the same, with minimal syntax differences.

Did it work?

The whole point of this project was to learn about compute shaders in order to improve the performance of the boid algorithm, and eventually the performance of other algorithms too.

I implemented three boid algorithms in Unity3D: a CPU implementation, a GPU implementation using a compute shader, and a GPU implementation that uses a compute shader as well as GPU instancing to draw the boids.

Tangent: GPU Instancing

GPU instancing is a way to draw multiple copies of a mesh using the GPU. It is highly efficient, and can be used to draw a large number of objects at once, which is perfect for drawing boids.


Anyway, these three implementations proved to me that compute shaders are a great way to speed up certain algorithms. Below is a graph that shows the performance of the three boid algorithms.


  • With 100 boids, they all performed at high speeds, with the GPU instancing implementation being the fastest at over 600 fps.
  • Once there were over 1000 boids, the CPU implementation started to fail, and would run at an average of 8.7 fps. Both GPU implementations were still running strong, with average frame rates of 94 fps and 625.6 fps.
  • Finally, with 10000 boids, the CPU and GPU implementations were rendered useless, with average frame rates of 0.1 fps and 1.5 fps respectively. With that amount of boids, the GPU instancing implementation held its own at an average 87.9 fps!

The bottom line

Compute shaders and running algorithms on the GPU are great ways of increasing performence and working with large amounts of objects. I am extremely excited about learning how to use compute shaders, and I can’t wait to use them in upcoming projects (I think that using them in dynamic LOD meshes is a great way to improve the performance of the algorithm).

Thanks for reading!

Resources