Repository files navigation

Boids is a program developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds. He publishedthis model in 1987 in the seminal paper"Flocks, Herds, and Schools: A Distributed Behavioral Model".

The motion of a flock of birds is an example of emergent behavior -- each bird is only making individualdecisions, yet the motion of the entire flock is fluid and synchronized. Somehow, organized group behavior is ableto emerge as the aggregate of the local actions of each individual animal.

Boids simulates this individual decision making with three rules:

1. Separation: individuals try to avoid crowding their nearby flockmates
2. Alignment: individuals steer towards the average heading of nearby flockmates
3. Cohesion: individuals try to move towards the center of mass of nearby flockmates

This repository contains an implementation of the boids model in C++.

This implementation uses ak-d tree to increase efficiency. A k-d treepartitions the boids in space so that when each boid is updated, we only consider the nearby boids rather thaniterating over all boids and incurring an O(n²) cost.

The implementation also uses OpenMP for some simple parallelization that leads to further speedups (and therefore theability to simulate a larger number of boids).

This project depends onSFML, which must be installed first. On MacOS, this can be done withbrew install sfml.

After installing SFML, the executable for the program can be built and installed by running the scriptbuild_and_install.sh. This program can then be run with:

./bin/simulate

Almost all aspects of the simulation and the boids' behavior can be customized from the command line. Pass the--help flag to see available options.

The simulation is also interactive. Left-clicking on the screen will add a new boid, and right-clicking will add a newpredator boid (normal boids will try to avoid these). PressingC on the keyboard will clear all the Boids on thescreen, and pressingQ will end the simulation and quit the program.