Bird Flocking Simulation
Bird flocking is an extremely interesting natural phenomenon that have been widely studied as witnessed by the number of papers in literature). I will present here a work on aggregate motion of large number of boids in a virtual environment with the presence of predators using CUDA as computational framework.
Collective motion or flocking appears at different fields and scales in nature and several mathematical tools have been developed for analyzing such motions
- organism are threaten as particles in Brownian motion combined with attraction/repulsion forces
- Differential equation models
- Agent based models.
The model presented here is based on a work of Reynolds (1987) which is based on three key behavioral rules:
- Cohesion: to attempt to stay close to nearby flock-mates;
- Collision avoidance: to evade objects that are too close;
- Velocity/Heading Matching: to head in the same direction of nearby flock-mates
and extends it adding predator avoidance and multiple species and bird groups interaction
Bird Flocking Model
The environment is parameterized using the following a set of parameters that describe the size of the virtual environment and the duration of a timestep. What is really interesting is the set of bird's parameter that describe how a bird behave and react to event in its surrounding. Some notable parameters include the Fyeld Of View (FOV), peak velocity $v_p$, thrust $a$ and others (see figure).
The environment is partially observable and the portion of space that is visible to each bird is defined by its FOV. FOV is defined as follows:
Let the position vector of the object in the 's frame of reference, then is 's neighbor if and only if the followings hold:
where is the maximum horizontal range of view, $s_v$ is the maximum vertical range of view and
In formal terms , the bird 's centroid at time , is given by:
which is basically a weighted average of neighbors position.
A bird try to keep certain distance between itself and
its neighbors. Bird 's separation vector at time is given
where determines how strong is the repulsion against to the neighbor .
Bird's alignment is computed as follows
It is a weighted average of the neighbors's heading direction.
Other species and predator avoidance
Other species avoidance is a behavior pretty much similar to the separation. The only difference is that only birds that belong to other species contribute to the result.
Predator avoidance is also a "flee or separation" behavior, but what happens here is that we do not take into account the current predator position, but instead, birds try to "separate" from predators's next position (the prediction is made from current position and velocity and acceleration of the predator).
The predator avoidance vector is defined as follows:
- is the 's set of predators
is the predator avoidance coefficient, where is the minimum distance bird avoid predator.
The model has been implemented in CUDA to speedup the simulation. The following is a short video which I used during my presentation at PDP16 conference. The model and the implementation described in this article are much more greatly described in the following slides (download here).