Problem statement: Simulation of a large number of particles (boids) to mimic flocking behaviour as seen in a school of fish or a flock of birds in C++ using OpenGL.
I came across boids and their behaviour while reading a fantastic book titled “Out of Control” by Kevin Kelly (you can read this entire book here for free!). Craig Reynolds, a computer graphics expert, had created the boids simulation in 1986. Since complex flocking behaviour emerges from a set of simple rules, it is also considered as an example of artificial life simulation. The three simple rules for the flocking beaviour to emerge are alignment, cohesion and separation. A detailed explanation of the rules and other relevant publications can be found in Craig Reynolds website. You can find the pseudocode here or watch a youtube video here for more details.
Unfortunately, my Ubuntu doesn’t support CUDA, and hence the current simulation is a naive version of the simulation. Since all the individual boids are compared with each other at each iteration, this algorithm has O(n^2) complexity. The primary objective of this tutorial was to familiarise me with OpenGL. The simulation is aimed at visual appeal; there are several parameters to tweak like the neighbourhood distance, simulation step size etc. to obtain the best visual stimulation.
There are various implementations for updating the position of the boids at each iteration. In this tutorial, I update the velocities, which in turn reflect in the positions of the boids. Sometimes, the simulation might reach an equilibrium state, or the boids stop exploring if the parameters mentioned above are not set correctly. To avoid such cases, I have added a small random part to the velocity, which encourages the boids to keep moving. There is a weird shooting motion for alone boids (having any neighbours) which need to be fixed.
Finally, this repository has all the codes for a CUDA based implementation. The spatial discretisation allows for faster computation and hence can have a lot more boids at a time.
My complete ready code is available in this GitHub repository.