Tutorials (back to the list of tutorials)

## Swarm Algorithm (requires iGeo version 7.5.3 or higher)

### Three Rules of Swarm Algorithm

Swarm behavior can be simulated by a type of multi-agent algorithm. The most popular algorithm is the algorithm of boids developed by Craig Reynolds in 1986. The boids algorithm consists of three simple rules to interact with other boid agents.
• Cohesion : going to the center of the surrounding agents.
• Separation : going away from other agents.
• Alignment : heading towards the same direction of other agents.

Each of those three rules has different distance range. Typically cohesion has the largest range, alignment has the second largest and the separation has the smallest, but depending on the intended behaviors of swarm agents, this order can be changed.

For more description about the algorithm of boids, please see Craig Reynolds's boids page .

### Swarm Rule 1: Cohesion

The first rule of this swarm algorithm is cohesion. This is a rule for an agent to get closer to the center of neighbor agents. This rule can be seen as a type of attraction rule.

Other agents are counted as neighbor agents if the distance to the agent is less than the threshold distance of cohesion (cohesionDist). The center of neighbors is calculated by adding all position of them and then divided by the number of the neighbors (count). The force is calculated by taking difference vector between the current agent and the center. The amount of the force is adjusted by the coefficient cohesionRatio.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(30);
for(int i=0; i < 100; i++){
new MyBoid(IRand.pt(100,100,0),
IRand.pt(-10,-10,0,10,10,0)).clr(IRand.clr());
}
}

class MyBoid extends IParticle{
double cohesionDist = 50;
double cohesionRatio = 5;

IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void interact(ArrayList< IDynamics > agents){
IVec center = new IVec(); //zero vector
int count = 0;
for(int i=0; i < agents.size(); i++){
if(agents.get(i) instanceof MyBoid){
MyBoid b = (MyBoid)agents.get(i);
if(b != this){
if(b.pos().dist(pos()) < cohesionDist){
count++;
}
}
}
}
if(count > 0){
center.div(count); //center of neighbors
IVec force = center.sub(pos()); //difference of position
push(force.mul(cohesionRatio));
}
}

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

### Swarm Rule 2: Separation

The second rule of the swarm algorithm is separation. This is a rule for an agent to get away from close agents. This rule can be seen as a type of repulsion rule.

In the same way with cohesion rule, the threshold distance of separation (separationDist) is used to determine if the other agent is close enough to get away from. The force is calculated by a summantion of each force from close agents. The amount individual force is reset by this formula
force.len( separationDist - dist )
to make the closer agent's force larger and farther force smaller (and the agent at the distance of separationDist, the force is zero). The total force for the current agent to move away (separationForce) is adjusted by the coefficient separationRatio.

There is one additional note about this conditional statement dist != 0 in the in the if-condition. It is to avoid the case when the two agents' positions are identical and the direction to push out the agent cannot be defined from the difference. To be more precise, the agent should be pushed out in some default direction when they are in a same position but in the following example, this case is just excluded to keep it simple.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(60);
for(int i=0; i < 100; i++){
new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0)).clr(IRand.clr());
}
}

class MyBoid extends IParticle{
double separationDist = 30;
double separationRatio = 5;

IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void interact(ArrayList< IDynamics > agents){
IVec separationForce = new IVec(); //zero vector
int count = 0;
for(int i=0; i < agents.size(); i++){
if(agents.get(i) instanceof MyBoid){
MyBoid b = (MyBoid)agents.get(i);
if(b != this){
double dist = b.pos().dist(pos());
if(dist < separationDist && dist!=0 ){
IVec force = pos().dif(b.pos());
force.len(separationDist - dist); //the closer the larger
count++;
}
}
}
}
if(count > 0){
separationForce.div(count); //average force
separationForce.mul(separationRatio);
push(separationForce);
}
}

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

### Swarm Rule 3: Alignment

The third rule of the swarm algorithm is alignment. This is a rule for an agent to steer towards the same direction with other agents.

Other agents within the range of the threshold distance of alignment (alignmentDist) are counted as neighbors and the average of their velocities is calculated. Then the difference between the average velocity and the current agent's are measured and the force is added to the direction of the vector difference of these two velocities. The amount of force is adjusted by the coefficient alignmentRatio.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(100);
for(int i=0; i < 100; i++){
new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0)).clr(IRand.clr());
}
}

class MyBoid extends IParticle{
double alignmentDist = 40;
double alignmentRatio = 5;

IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void interact(ArrayList< IDynamics > agents){
IVec averageVelocity = new IVec(); //zero vector
int count = 0;
for(int i=0; i < agents.size(); i++){
if(agents.get(i) instanceof MyBoid){
MyBoid b = (MyBoid)agents.get(i);
if(b != this){
if(b.pos().dist(pos()) < alignmentDist){
count++;
}
}
}
}
if(count > 0){
averageVelocity.div(count);
IVec force = averageVelocity.sub(vel()); //difference of velocity
push(force.mul(alignmentRatio));
}
}

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

### Combining 3 Rules into Swarm Class

Those three rules are combined into one agent class as the following. Each rule is independently forming a method and the three methods of cohere(), separate() and align() are executed inside interact method.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(150);
for(int i=0; i < 100; i++){
new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0)).clr(IRand.clr());
}
}

class MyBoid extends IParticle{
double cohesionDist = 50;
double cohesionRatio = 5;
double separationDist = 30;
double separationRatio = 5;
double alignmentDist = 40;
double alignmentRatio = 5;

IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void cohere(ArrayList< IDynamics > agents){
IVec center = new IVec(); //zero vector
int count = 0;
for(int i=0; i < agents.size(); i++){
if(agents.get(i) instanceof MyBoid && agents.get(i)!=this){
MyBoid b = (MyBoid)agents.get(i);
if(b.pos().dist(pos()) < cohesionDist){
count++;
}
}
}
if(count > 0){
push(center.div(count).sub(pos()).mul(cohesionRatio));
}
}

void separate(ArrayList< IDynamics > agents){
IVec separationForce = new IVec(); //zero vector
int count = 0;
for(int i=0; i < agents.size(); i++){
if(agents.get(i) instanceof MyBoid && agents.get(i)!=this){
MyBoid b = (MyBoid)agents.get(i);
double dist = b.pos().dist(pos());
if(dist < separationDist && dist!=0 ){
count++;
}
}
}
if(count > 0){
push(separationForce.mul(separationRatio/count));
}
}

void align(ArrayList< IDynamics > agents){
IVec averageVelocity = new IVec(); //zero vector
int count = 0;
for(int i=0; i < agents.size(); i++){
if(agents.get(i) instanceof MyBoid && agents.get(i) != this){
MyBoid b = (MyBoid)agents.get(i);
if(b.pos().dist(pos()) < alignmentDist){
count++;
}
}
}
if(count > 0){
push(averageVelocity.div(count).sub(vel()).mul(alignmentRatio));
}
}

void interact(ArrayList< IDynamics > agents){
cohere(agents);
separate(agents);
align(agents);
}

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

### Shorter Code of Swarm Class

The code above could be roughly simplified to the following with the shorter definition of interact method, but algorithmically it is not accurate because it doesn't have the variable count and ignores the number of neighbors within each range. Because of this, the way to adjust the parameters of ratio of each rule is different from the previous code.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(150);
for(int i=0; i < 100; i++){
new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0)).clr(IRand.clr());
}
}

class MyBoid extends IParticle{
double cohDist = 50;
double cohRatio = 0.05;
double sepDist = 30;
double sepRatio = 0.05;
double aliDist = 40;
double aliRatio = 0.05;

IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void interact(IDynamics agent){
if(agent instanceof MyBoid){
MyBoid b = (MyBoid)agent;
if(dist(b) < cohDist) push( b.dif(this).mul(cohRatio) );
if(dist(b) < sepDist) push( dif(b).len((sepDist-dist(b))*sepRatio) );
if(dist(b) < aliDist) push( b.vel().dif(vel()).mul(aliRatio) );
}
}

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

### Using IBoid Class

iGeo library includes a class which defines the swarm behavior with those three rules. If you don't need to modify those three rules directly inside the interact method, you can define your agent class as a child class of IBoid class and tune parameters of the threshold distances and the force ratios of cohesion, separation and alignment.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(150);
for(int i=0; i < 100; i++){
MyBoid b = new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0));
b.clr(IRand.clr());
b.cohesionDist(50);
b.cohesionRatio(5);
b.separationDist(30);
b.separationRatio(5);
b.alignmentDist(40);
b.alignmentRatio(5);
}
}

class MyBoid extends IBoid{
IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

### Tuning Swarm Parameters

The following codes show examples of parameter settings of the swarm class. There are six parameters to control the behavior of the swarm agent. Three threshold distance parameters and three force ratio parameters to control the strength of force of cohesion, separation and alignment.

The first setting below have setting of smaller threshold distance for each rule. As result it creates smaller clusters of swarms.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(100);
for(int i=0; i < 100; i++){
MyBoid b = new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0));
b.clr(IRand.clr());
b.cohesionDist(21);
b.cohesionRatio(5);
b.separationDist(10);
b.separationRatio(5);
b.alignmentDist(15);
b.alignmentRatio(5);
}
}

class MyBoid extends IBoid{
IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

The next setting below has a smaller force ratio in the alignment rule. Because the force to align the velocities of agents are weak, it oscillates around the center with the attraction and repulsion forces from the cohesion and separation rule, not converging into the same velocity for a while.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(300);
for(int i=0; i < 100; i++){
MyBoid b = new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0));
b.clr(IRand.clr());
b.cohesionDist(50);
b.cohesionRatio(5);
b.separationDist(30);
b.separationRatio(5);
b.alignmentDist(40);
b.alignmentRatio(0.5);
}
}

class MyBoid extends IBoid{
IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

The setting below has a larger threshold distance for the separation rule and a smaller threshold distance for the cohesion rule. Because of this inverted order of cohesion and separation, agents try to go away but still creating smaller clusters with the alignment rule.

```import processing.opengl.*;
import igeo.*;

void setup(){
size(480, 360, IG.GL);
IG.duration(800);
for(int i=0; i < 100; i++){
MyBoid b = new MyBoid(IRand.pt(100,100,0),
IRand.pt(-5,-5,0,20,20,0));
b.clr(IRand.clr());
b.cohesionDist(30);
b.cohesionRatio(5);
b.separationDist(50);
b.separationRatio(5);
b.alignmentDist(40);
b.alignmentRatio(5);
}
}

class MyBoid extends IBoid{
IVec prevPos;

MyBoid(IVec p, IVec v){ super(p,v); }

void update(){ //drawing line
IVec curPos = pos().cp();
if(prevPos!=null){ IG.crv(prevPos, curPos).clr(clr()); }
prevPos = curPos;
}
}
```

(back to the list of tutorials)