A significant amount of work have been applied trying understand and emulate the behaviour of flocking animals such as schools of fish or swarms of mosquitoes. One of the most successful models of such behaviour is the boid algorithm presented by Craig Reynolds in the paper Flocks, Herds and Schools: A Distributed Behavioural Model at the top conference in Computer Graphics Siggraph in 1987. The paper is based on a very simple model, where the motion of each member of the flock is governed by a set of simple rules.

In this project you will implement the boid algorithm and create a real-time visualisation. The program is going to interact with the user via the mouse. We are going to make use of the Simple DirectMedia Layer (SDL) framework for visualisation and control.

The algorithm requires some basic knowledge of vector algebra, as a first step make sure you understand subtraction and addition of vectors and the concept of L2-norm and the euclidean distance between two vectors.

One of the key aspects of becoming a good programmer is to think things through and try to grasp the overall scope of the project before starting to write the code. Read through the boid algorithm and try to identify what type of flexibility your program will need, what functions do you need, how should the “flow” of the code be.

Boids is an algorithm for simulating the behaviour of each member in a flock. We will refer to each member of the flock as a particle. Each particle is described by two parameters, its current position X and its current velocity V. Our flock will move in a three dimensional space which means that X and V will have three components. The algorithm is iterating over time to produce the movement of the flock, we will refer to a single time step as a frame. Each frame we perform the following operation,

• Update the position of each particle
• Visualise (render) the particles

In order to update the position of a particle moving in time we simply add the velocity to its current position,

The movement of the particles is generated by computing the velocity parameter v. The velocity is calculated for each particle in turn and based on four simple rules:

• Each particle tries to stay close to the other particles (centering)
• Each particle tries to avoid colliding with the other particles (repulsion)
• Each particle tries to align its direction of travel to that of the flock (cohesion)
• Each particle aims to arrive at a specific target in space (target)

We will now step through each of the four rules in order to see how they effect the behaviour of a single particle.

Centering
In a flock each member aims to stay in close to each other. For a specific particle the remainder of the flock is described by the average position of all the other members. The particle is then trying to move towards this position in order to stay with the flock.

Repulsion
The centering rule will move all the particles towards the “perceived” centre of the flock, this means that as time proceeds each particle will strive towards the same position leading the flock to collaps into a single point. To avoid this we will add a second rule to update the velocity of a particle. When two particles are within a specific distance of each other we want them to move away from each other. This can be implemented by the following rule,

Cohesion
We want the flock to move together as a “one unit” we can simulate this behaviour by altering the velocity of each particle such that it tries to align to the perceived direction of the flock as a whole. We will use the average velocity as a measure of the direction of the flock.

Target
The last rule is that we want the flock to strive to a common goal, i.e. towards a target position.

Putting it all together
Having computed all the rules for a specific particle we update the velocity by adding the all the velocities together and then altering the current velocity by this value. In order to be able to tune the behaviour and strength of the different rules we create a weighted sum by multiplying each velocity component by a scalar coefficient.

• Make sure you understand each of the elements of the above algorithm.
• Identify the variables your program will need
• How should the variables be structured?
• Think through what functions you will need to implement

The algorithm defines the movement of each particle in the flock. In the next step we are going to look at how we are going to display the flock on the screen and interact with the program. In order to do so we are going to use the Simple DirectMedia Layer (SDL) library. You are given a source code that sets up a screen and creates a few functions for writing content and interacting with the program.

The SDL library needs to be installed in your system and the Makefile provided with the source code will try to find it by internally executing a command returning SDL configuration:

• sdl-config --libs - gives the location of the libraries and the gcc arguments for including the necessary libs
• sdl-config --cflags - gives the flags that the compiler will needs to compile an SDL program as well as path to SDL include files.

Run make and execute the example with ./main to be sure everything compiled and that the executable performs as expected. You should see a black window with a white dot close to the upper left corner. You should be able to close the program by pushing the ESC key.

The supplied code in main.c has a main function with two parts. In the first section SDL is started and a window is opened on the screen. The second part of the function contains the event-loop where the main functionality of the program takes places. The event loop polls the state using the command SDL_PollEvent() if an event has occurred it test the type of the event in a switch-case statement. The first case is invoked if the ESC key is pressed down in which case the even-loop ends. If the event is movement of the mouse the read_mouse() function is called. Finally the update_boids() and the render_screen() functions are called.

Before continuing make sure that you understand how the event-loop works.

You have been provided with a set of functions which you can build your implementation from which are described below:

• put_pixel(SDL_Surface* screen,int x,int y,pixel* p) plots pixel p cordinates x,y in screen screen.
• clear_screen(SDL_Surface* screen) clears the screen.
• update_boids(void) is an empty function which should compute the location of the particles
• read_mouse(SDL_Event* event) prints out the location of the mouse pointer
• render_screen(SDL_Surface* screen) empty function where the rendering should be placed
• clean_up(SDL_Surface* screen) function which closes SDL down and cleans up before returning the program.

You do not need to understand the specifics of the implementation of all the functions as long as you understand their purpose and the structure of the program. To make sure that you understand play around with the code and make sure you can plot something on the screen. If you are interested in understanding the specifics behind the SDL calls you can find them in the documentation.

You should implement the boid algorithm in the given SDL framework. The particles should move in three dimensions and the rendering should be perspective correct (look in the matlab project about cameras). However you do no need to move the camera which means you do not need to use a full camera matrix. It is enough to render each particle using a single pixel. The target for the particles should be altered by moving the mouse. It should be easy to change the number of particles. This means that the number of particles at the beginning of the simulation does not need to be equal to the number of particles at the end. Also the program should handle in the order of hundreds of particles.

• Think of a good and flexible structure for storing the particles.
• Think of a good and flexible structure for the swarm
• Identify the variables you need.
• What functions will you need?
• Where and in what functions do you need the different variables?
• You will probably need some functionality from the math.h for computations

When you have thought this through its time to start with the implementation

• Write the function declarations
• Write the structs to store the data and the variables
• Implement the four different rules of the algorithm.
• Implement the particle update function
• Implement the rendering function

When you have gotten this far its time to put everything together and make sure that things are working the way they are supposed to. However, first we need to think of how to start. The particles position in the next frame is based on the position in the current frame this means that to be able to update the position we need to know the current position. Therefore we need to start the particles in some position at time zero. One possibility is to start them with random position and random velocity, you can get random numbers i C through the function rand(). Test the code by altering the influence by the different rules, by turning them off you can examine them in turn, do they behave as you expect?

If you play around with the parameters you should be able to generate some quite impressive results as can be seen in the following video:

The parameters I used to generate my implementation where these,

Together with your implementation, you should submit a text file explaining how to properly run the program.