iGeo Tutorials

チュートリアル

スウォーム・アルゴリズム

スウォーム・アルゴリズムの３つの規則

一般的にスウォーム動作(群行動)はマルチ・エージェント・アルゴリズムの枠組みでシミュレーションでき、最も有名なアルゴリズムはクレイグ・レイノルズによって1986年に開発された Boidアルゴリズムです。このアルゴリズムは3つの規則から成り立ちます。

結束規則 : まわりのエージェントの中心点に向かおうとする
分離規則 : 近すぎるまわりのエージェントから離れようとする
整列規則 : まわりのエージェントと同じ方向を向こうとする

まわりのエージェントをチェックする範囲は、それぞれの規則で異なるものを設定します。通常は、結束規則の範囲を一番大きく取り、次に整列規則の範囲、そして分離規則の範囲を一番小さくとります。しかし、これに限らずこれらの範囲を調整することによって、様々なスウォーム動作が現れます。

Boidアルゴリズムの詳細はクレイグ・レイノルズのページを参照下さい。

規則その１: 結束規則

結束規則は、エージェントがお互いに集まるための規則です。各々のエージェントにアトラクタ―の力があるとも捉えられます。

結束規則のために調べる距離範囲をcohesionDistとします。範囲内にあるエージェントの中心点を求めるために、まずそれに該当するエージェントの数countとの位置の総和を計算し、総和をcountで割ることで中心点を求めます。その次に、エージェント自身の位置から中心点への差ベクトルを生成し、係数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){
            center.add(b.pos());
            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;
  }
}

規則その２: 分離規則

分離規則はエージェントが近づきすぎないための規則です。各々が斥力を持っているようにも捉えられます。

結束規則と同様に、分離規則をチェックする範囲を separationDistで与え、この距離より近ければ近すぎると判断します。その場合、相手のエージェントの位置から自分の位置への差ベクトルを生成して力のベクトルとします。その力の大きさは、以下の式で設定され、
force.len( separationDist - dist )
近ければ近いほど大きくなるようにします。この力のベクトルを、範囲内にあるすべてのエージェントに対して総和をとったのちその数で割って平均をとり、そして係数separationRatioをかたものを自身に対する力のベクトルとして適用します。

一つ注意が必要なのは、If条件分岐の中にある dist != 0 の部分で、dist==0の状況は他のエージェントが全く同じ場所に存在する場合に起こり、そうすると位置の差ベクトルがゼロ・ベクトルとなってどちらの方向に力を与えるべきか計算ができなくなるため、 If条件分岐で除外されています。

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
            separationForce.add(force);
            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;
  }
}

規則その３: 整列規則

整列規則は、群れが同じ方向へ移動するための規則です。

整列規則を適用する範囲はalignmentDistで与えられます。その範囲内にあるエージェントの数を数え、平均の速度ベクトルを求めます。そして平均速度ベクトルと、自身の速度ベクトルの差ベクトルを求め、それに係数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){
            averageVelocity.add(b.vel());
            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;
  }
}

３つの規則を適用したスウォーム・クラスの実装

以上の３つの規則を組み合わせてスウォーム・エージェント・クラスを実装します。それぞれの規則は別々のメソッドに分けられ、結束規則はcohere()メソッド、分離規則はseparate()メソッド、整列規則はalign()メソッドに実装されます。そしてその３つがinteractメソッドから呼び出され実行されます。

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){
          center.add(b.pos());
          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 ){
          separationForce.add(pos().dif(b.pos()).len(separationDist - dist));
          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){
          averageVelocity.add(b.vel());
          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;
  }
}

スウォーム・クラスの短縮版

可変長配列ではなく、一つのインスタンスだけを引数にとる短縮版のinteractメソッドを用いると、ひとつ前のコードは、正確には同一の動作ではないものの、おおよその動作を短く書くことができます。平均の計算が省かれているため、動作が多少異なるだけでなく、各規則の係数も変わってきます。

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;
  }
}

IBoidクラスの利用

iGeoライブラリには以上のようなBoidアルゴリズムを実装したIBoidクラスが用意されています。 Boidアルゴリズムを利用するには、距離や係数のパラメータの調整すればすぐに利用可能ですし、 Boidアルゴリズムに独自の動作を追加したエージェントの作成は、IBoidクラスを継承した子クラスの作成により可能になります。

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;
  }
}

スウォーム・パラメータの調整

Boidアルゴリズムは距離や係数のスウォームのパラメータの値やスウォーム・エージェントの初期位置に応じて、様々な振る舞いをします。以下にそのいくつかの例を示します。

一つめの例では、結束、分離、整列の距離パラメータを全て小さく設定してあります。その結果、スウォーム・エージェント集合して移動するクラスタが小さいグループで分断しています。

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;
  }
}

二つめの例では整列規則の力の係数を小さくしてあります。その結果、同じ方向へ進もうとする力が弱くなる一方、集まろうとする力と離れようとする力が相対的に大きくなるので集合状態と離散状態の振動が発生しながら、やがて少しづつ同じ方向へ向き始めます。

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;
  }
}

三つめの例では分離規則の距離パラメータを大きくし、結束規則の距離を小さく設定しています。その結果、分離規則が強く働きスウォーム・エージェントは分散して行きますが、整列規則により小さなクラスターを作りながらそれぞれ同じ方向へ進んでいきます。

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;
  }
}

(トピック一覧へ戻る)

HOME

FOR PROCESSING

DOWNLOAD

DOCUMENTS

TUTORIALS (Java / Python)

GALLERY

SOURCE CODE(GitHub)

ABOUT/CONTACT