Boids in 3D

I created a 3D Boids simulation the result of which can be seen here. In "Controls" a lot of parameters (visual and simulation-related) can be changed - some of them will be even be described below! There is also a fullscreen mode (button in the lower right) and some presets.

The boid model was proposed by Craig Reynolds in 1987 to simulate the motion of a flock of birds. In this relatively simple model the motion of the flock is the result of the motion of individual bird-like objects each with their own independent dynamics. Each bird-like object (a "bird-oid" or "boid") is modeled as a point particle with position \(\vec{x}_i\) and velocity \(\vec{v}_i\) subject to some forces that depend on its local environment (as well physical forces such as gravity but this will be ignored here).

In each step of the simulation the position \(\vec{x}_i\) of each boid is updated according to

where we usually set \(\Delta t = 1\).

Similarly, the velocity \(\vv_i\) of boid \(i\) is updated in each step. In Reynolds' model the change in velocity is a weighted sum of three contributions¹:

• Separation ("static collision avoidance" in Reynolds' model):

  \begin{align} \Delta \vv^{(i)}_{\mathrm{sep}} = \sum_{|\vx_i - \vx_j| \leq r_{\mathrm{sep}}} \frac{\vx_i - \vx_j}{|\vx_i - \vx_j|}. \end{align}

  The effect of this contribution is to steer boid \(i\) away from boid \(j\) to avoid collisions between boids that are close to each other. The sum runs over boids \(j\) that are within a radius \(r_{\mathrm{sep}}\) of boid \(i\).

• Cohesion ("flock centering"):

  \begin{align} \Delta \vv^{(i)}_{\mathrm{coh}} = \left(\frac{1}{N_{\mathrm{coh}}} \sum_{|\vx_i - \vx_j| \leq r_{\mathrm{coh}}} \vx_j \right) - \vx_i, \qquad N_{\mathrm{coh}} = \sum_{|\vx_i - \vx_j| \leq r_{\mathrm{coh}}} 1. \end{align}

  This contribution points towards the center of mass of all boids within radius \(r_{\mathrm{coh}}\) of boid \(i\) and thus represents the tendency of the boids to form clusters.

• Alignment ("velocity matching"):

  \begin{align} \Delta \vv^{(i)}_{\mathrm{ali}} = \left(\frac{1}{N_{\mathrm{ali}}} \sum_{|\vx_i - \vx_j| \leq r_{\mathrm{ali}}} \vv_j \right) - \vv_i, \qquad N_{\mathrm{ali}} = \sum_{|\vx_i - \vx_j| \leq r_{\mathrm{ali}}} 1. \end{align}

  Finally, the third contribution aligns the velocity of boid \(i\) with the average velocity of other boids in a neighborhood with radius \(r_{\mathrm{ali}}\). As Reynolds points out, this is also a form of collision avoidance: If all boids were to to have the same velocity, the distances between them would remain constant and no collisions would occur.

In the model here we are adding one extra contribution to the change in velocity which steers the boids towards a fixed set of points \(\{\vy_j \; | \; j = 1, \ldots, N_{\mathrm{s}}\}\):

We can think of these for example as some source of food that the birds would like to catch. Note that in the simulation above, the positions \(\vy_j\) are randomized every few seconds.

The total change in velocity of each boid is then a weighted sum of these four contributions,

where

Looking at this descriptions we can extract the following parameters for our simulation:

• The weights of the different forces: \(w_{\mathrm{sep}}, w_{\mathrm{coh}}, w_{\mathrm{ali}}\) and \(w_{\mathrm{s}}\).
• The radii of the different interactions: \(r_{\mathrm{sep}}, r_{\mathrm{coh}}\) and \(r_{\mathrm{ali}}\). One can think of these as a measure for how far into the distance a boid "senses" other boids.
• The maximum magnitude of the change in velocity: \(v_{\mathrm{max}}\).
• The number of sources for food \(N_{s}\) and the size of the box in which they spawn.

Each of these parameters can be adapted in the simulation above.

I found it quite difficult to find a set of weights and radii that gives reasonable-looking results. In the end I found some in this paper that I used as a starting point.

The simulation is written in (probably rather bad) Rust and compiled to WebAssembly with wasm-pack. Each boid is simply a struct

pub struct Boid {
    pub position: SVector<f64, D>,
    pub velocity: SVector<f64, D>,
}

with two vectors. For the numerical vectors I used the nalgebra crate. In the update step of the simulation we iterate through a Vec that contains all of the boids and update their positions and velocities.

For each boid we have to find all other boids within the different radii of the interactions. Initially I did this in the most naive way by iterating through all boids again but the \(\mathcal{O}(n^2)\) scaling of this approach meant that the number of boids had to be quite small. Eventually I used a k-d tree to find all points within \(\operatorname{max}\left(r_{\mathrm{sep}}, r_{\mathrm{coh}}, r_{\mathrm{ali}}\right)\) for each boid position \(\vx_i\). I did not implement the tree myself but used the kiddo crate for that.

While this all makes it reasonably fast, I am still not 100% satisfied by the performance. On my eight-year-old laptop I can go up to about 2000 boids comfortably but when all the boids cluster together somewhere the framerate drops below 30fps. It seems that most of the time is spent querying the tree (which makes sense to me), but I had the feeling that there was somee potential for parallelism that could not be exploited (maybe because of the wasm target). Maybe also an ECS approach would make more sense here and speed things up.

Finally, the visualization in the browser is done with three.js. I was a little bit lazy and simply used the water effect from the Water addon and the sky effect from the Sky addon.

The code can be found on sourcehut or on GitHub.

• Craig Reynolds: Flocks, herds and schools: A distributed behavioral model (1987)
• Norihiro Maruyama, Daichi Saito, Yasuhiro Hashimoto, Takashi Ikegami: Dynamic organization of flocking behaviors in a large‑scale boids model (2019)