Flocking Simulation

Background

Flocking is an emergent phenomenon where individual units (organisms), using limited environmental awareness and simple rules, organize themselves into an ordered motion. Flocking is seen in foraging birds, fish and even in humans. In this simulation, flocking is achieved by using artificial creatures called Boids.

Boids

Boids are synthetic vehicles that have some basic predefined perception. Boids were created by Craig Reynolds in 1986. There are many resources online talking in detail about boids including wikipedia. So, I wont going into much depth here.

Flocking is a results of individuals following a simple set of steering behaviors. These behaviors tell the individuals how to move and interact with their surroundings using their limited perception. This simulation follows only three simple steering rules.

1. Separation: Steer to avoid crowding local flock mates.
2. Alignment: Steer towards the average direction of the local flock mates and match their average speed.
3. Cohesion: Steer to move towards the center of mass of the local flock mates

The strength of these three behaviors can be controlled with their respective sliders above. Other than these rules, each boid is initialized at a random location with a random velocity and a predefined perception radius. Perception radius controls the maximum distance a boid can sense another boid. Perception radius can also be controlled with its labelled slider and can be visualized with the checkbox.

Additionally the boundary of the canvas here can be "Bounded", i.e., closed or "Unbounded". i.e., open. When bounded, the boids get sent back in the opposite direction when they reach the boundary. When unbounded, the boundaries behave as though they are a closed loop. Whatever goes out one side, reenters on the opposite side. The type of boundary can selected by choosing the desired radio button.

Complexity

Here, since each boid behaves autonomously, they have to find for themselves which local group they belong to. In a brute force implementation, each boid has to check itself against every other boid every frame. This is computationally expensive. The brute force implementation of a flocking simulation has a big O notation of \( O(n^2) \). That means, for \(n\) boids, \(n^2\) checks have to be made every frame.

Quadtrees

Quadtrees are tree data structures which discretize 2D space into 4 quadrants recursively based on proximity. Once discretized, it makes use of depth first search to walk through the tree and get spatial information. Read more about quadtrees here. In flocking simulation optimized with quadtrees, a boid can determine its local group in significantly less number of checks. This reduces computational requirements and thus, more boids can be simulated. With quadtrees, the big O notation of a flocking simulation is \(O(n\log(n)\)).

Even though quadtree has to be computed every frame, the complexity of the simulation remains low. For a thousand boids, with brute force, a boid has to make a million checks and in a quadtree optimized simulation for the same number of boids, a boid has to perform 3000 checks.

Quadtree controls

In this simulation, quadtree optimization is enabled by default and can be disabled by checking off the optimize checkbox. The quadtree structure and its computation can be dynamically visualized by checking the "showQtree" checkbox. While computing a new tree structure does not affect computation adversely, visualizing quadtrees every frame comes with a significant cost, keep that in mind. Another control parameter for the quadtrees is the cell capacity. The lower the cell capacity, the finer the spatial discretization is. So, at finer capacity, the number of check increase, and this is also worth keeping in mind.

More Information

This simulation was made using the P5.js library. Its an open source creative coding platform. The source code for this simulation can be found on my github. Here is the link - Flocking Simulation.

I also made a standalone webapp for this simulation. It fits in one page. There is less to read and more room to play. Here is the link - Live App

References

1. Boids Background and Update by Craig Reynolds.
2. Boids Wikipedia
3. Flocking Behavior
4. Flocking Simulation Tutorial
5. Complexity
6. Quadtree Optimization - Background
7. P5JS website.