rystrauss/boids

Craig Reynolds' Boids model for simulating the flocking behavior of birds.

Boids

Boids is a program developed by Craig Reynolds in 1986, which simulates the flocking behaviour of birds. He published this 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 individual decisions, yet the motion of the entire flock is fluid and synchronized. Somehow, organized group behavior is able to 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++.

Implementation Details

This implementation uses a k-d tree to increase efficiency. A k-d tree partitions the boids in space so that when each boid is updated, we only consider the nearby boids rather than iterating 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 the ability to simulate a larger number of boids).

Usage

This project depends on SFML, which must be installed first. On MacOS, this can be done with brew install sfml.

After installing SFML, the executable for the program can be built and installed by running the script build_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 new predator boid (normal boids will try to avoid these). Pressing C on the keyboard will clear all the Boids on the screen, and pressing Q will end the simulation and quit the program.