Simulating Boids

The program simulates flocking behaviour for a group of text characters on a notebook page. The characters use Craig Reynold's Boids principles to navigate through obstacles.

Representation

Each Boid is represted by its position and velocity vectors.

Steering Principles

1. The boids try to keep the flock cohesive. In order to do this, they steer towards
the center of their immediate neighbourhood.

2. The boids try to avoid colliding with each other. To do this, the boids move away from each other if they are at less than a minimum distance from their neighbours.

3. The boids try to match their velocity with their neighbours.

Additional Principles to avoid Obstacles and Boundaries

Boundaries are considered to be planes which cannot be crossed by the boids. Obstacles are represented by their sphere of influence. In this case, obstacles are circular regions.

Obstacles can be avoid either using the Force Field or Steer to Avoid principles.

In the Force field concept, the obstacles are modelled by a repelling force field which moves an approaching object away from it. This method is know to have problems when the object is approaching obstacle in the direction of the field.

I use the Steer to Avoid method. Here, a boid is aware that it is approaching an obstacle or a boundary and before it collides with it, it tries to steer away from it. This can help in smooth deflection of the flock. It also avoids collisions which are not natural to flock behaviour.

To implement this, I do the following when a boid is within a minimum distance of an obstacle or boundary

determine if the boid is moving towards or away
if moving towards, change the boid direction away from the obstacle by a certain angle

Boundaries

Dot product of the velocity vector of the boid and perpendicular to the boundary is computed. If the dot product is positive, the boid is moving towards it and vice versa.

For approaching boids, the angle between the velocity vector and the boundary is computed. The boid is steered (rotated) by a small fraction of this angle. This ensures that the boid will smoothly move away from the boundary. It is important to determine the direction in which the boid should be steered away. To determine if the boid should be steered away in positive angle or negative angle, I use the cross product of the velocity vector and the boundary.

The Corner Problem

I observe that when a boid approaches a corner at an angle close to 45 degrees, each of the boundaries tries to steer it away by a similar angle in opposite directions. These conflicting angles cancel each other and the boid may move out of the boundary or oscillate in that position.

Obstacles

The obstacles are modelled by their circle of influence. To avoid an obstacle, I first determine if the boid will collide with it if it continues to move in its current direction. To do this, I compute two angles. Angle a, which is the angle between the velocity and the vector joining the boid to the center of the obstacles. Angle b is the angle between the tangent to the circle from the boid and the vector joining the boid to the obstacles center.

If ( angle a < angle b ), the boid will collide with the obstacle. So I steer the boid away from the obstacle by some angle to avoid the collision.

Implementation

The program has been implemented using OpenGL with Qt GUI in C++. The characters are rendered using FTGL font rendering library.

For convenience, I also implemented a Vector3d library.

The code requires openGL, Qt, FTGL and freetype libraries to compile.

Controls

After launching the application, the spacebar can be used to start or pause the simulation. 'i' and 'o' keys can be used to zoom in and zoom out respectively. The sliders on the right can be used to rotate the scene.

The text to be displayed on the paper is loaded from "sample.txt" file. The initial velocity of the boids and the obstructions (position and radius) can be specified in the "config.txt" file.

download code

Questions

No questions!