Flocking Algorithms

Flocking

A Flocking Behavior is a simple set of rules that can emerge into a set complex global behaviors. There are many uses in game and simulator development for flocking. Whether you want you units to move around the map or you want to simulate a flock of seagulls or fish you can even emulate crowds, flocking provides a base for you to work of off.

There are three basic rules to flocking, separation, cohesion and alignment. I have represented these rules below in the image.

Lets talk about how you can actually implement a basic flocking behavior.

Separation:

The function code below is how you calculate the separation vector for each boid.  This code loops through every boid and checks if the position between the object being updated and the object that the loop is processing is within the minimum allowed distance by your code.

In my implementation, not shown in the code below, I actually only pass each boid the boids that are close to  it already.

Pseudo code:

FUNCTION separate(boid bj)       
         Vector c = 0;  
         FOR EACH BOID b  
             IF b != bj THEN  
                 IF |b.position - bj.position| < 100 THEN  
                     c = c - (b.position - bj.position)  
                 END IF  
             END IF  
         END  
         RETURN c  
 END FUNCTION 

Cohesion:

Cohesion is what makes the boids stick together in the local groups. Without it flocking really cannot exist. It works by calculating the center of the mass of the local flock (average position).

In my implementation, not shown in the code below, I actually only pass each boid the boids that are close to  it already.

Pseudo code:

 FUNCTION cohere(boid bj)  
  Vector pcj  
  FOR EACH BOID b  
   IF b != bj THEN  
    pcj = pcj + b.position  
   END IF  
  END  
  pcj = pcj / N-1  
  RETURN (pcj - bj.position) / 100  
 END FUNCTION  

Alignment:

Alignment works by averaging the velocities of all the boids in the local area to get the boids moving in the same general direction.

In my implementation, not shown in the code below, I actually only pass each boid the boids that are close to  it already.

Pseudo code:

 FUNCTION align(boid bj)  
  Vector pvj  
  FOR EACH BOID b  
   IF b != bj THEN  
    pvj = pvj + b.velocity  
   END IF  
  END  
  pvj = pvj / N-1  
  RETURN (pvj - bj.velocity) / 8  
 END FUNCTION  

Moving the Boids:

This is the function that gives your there acceleration and velocity then adjusts there position. It simply calls the above functions and then sums their result.

In my implementation I do more processing on the vectors values, I normalize each vector and then multiply by a weight factor that I can tweak for each vector. After this I also normalize the end result to get a smoother motion.

Pseudo code:

 FUNCTION flock()  
  Vector separateVector, cohereVector, alignVector  
  Boid b  
  FOR EACH BOID b  
   separateVector = separate(b)  
   cohereVector = cohere(b)  
   alignVector = align(b)  
   b.velocity = b.velocity + separateVector + cohereVector + alignVector  
   b.position = b.position + b.velocity  
  END  
 END FUNCTION  

Conclusion:

In the above code and descriptions I have outlined the basic structure that I have used to create a simple flocking behavior, this code is just as valid whether you are dealing with a 2D or 3D space. There are improvement to the code, some of which I have added and others which I have not.

You can rotate the object so it is always facing the direction it is traveling in. You can also add rules that handle collision with other objects, and steering behaviors to create an even smoother appearance to the object moving.