JAN.13.2017
SOCIAL NETWORK SHARE :

Boidsを調べる See about the boids

はじめまして、developerの後藤です。

鳥や魚が群れをなして飛んでいく光景、テレビなどでも見たことあるでしょうか。

今回は群れの動きをシミュレーションできるアルゴリズムBoidsについてまとめておきたいと思います。

Boidsとは

Boidsは3つルールを設定するだけで群れの動きをシミュレーションできるアルゴリズムのことで、1987年のCraig Reynoldsさんが発表しました。Boidsのアルゴリズムは、CG、ゲーム、WEBなど様々なジャンルの表現に使われています。

Craig Reynolds Boids : http://www.red3d.com/cwr/boids/

 

群れの動きをシミュレーションするためのルールは

  • 結合(cohesion)
    鳥たちが多くいる方へ向かって飛ぶこと
  • 引き離し(separation)
    近くの鳥に近づきすぎたら、ぶつからないように離れる
  • 整列(alignment)
    近くの鳥たちと飛ぶスピードや方向を合わせようとする

この3つルールを定義することで再現できるそうです。3つのルールについてコードを交えてみていきます。

Boidsを実装するための3つのルール

 

結合(cohesion) → 「鳥たちが多くいる方へ向かって飛ぶこと」

「鳥たちが多くいる方」とは群れの中心のことです。
対象となる要素が群れの中心方向に飛んでいくようにしてあげるということですね。群れの中心を計算するには、各要素の位置(x,y)を加算して、平均を求めることで群れの中心となる位置を計算することができます。

cohesion(index) {
    let c = {
        x: 0,
        y: 0
    };
    for (let i = 0; i < this.boids.length; i++) {
        if (i !== index) {
            c.x += this.boids[i].x;
            c.y += this.boids[i].y;
        }
    }
    c.x = c.x / (this.NUM_BOIDS - 1);
    c.y = c.y / (this.NUM_BOIDS - 1);
    this.boids[index].vx += (c.x - this.boids[index].x);
    this.boids[index].vy += (c.y - this.boids[index].y);
}


引き離し(separation) → 「近くの鳥に近づきすぎたら、ぶつからないように離れる」

各要素の距離とその他の要素が、一定距離より近づいた場合は離れるというルールです。
要素同士間のベクトルを比較して、対象となる2点の距離を計算し、一定距離近ければ離れるという判定を追加します。

 
separation(index) {
    for (let i = 0; i < this.boids.length; i++) {
        let s = this.getDistance(this.boids[i], this.boids[index]);
        if (s < this.BOID_SIDE) {
            this.boids[index].vx -= this.boids[i].x - this.boids[index].x;
            this.boids[index].vy -= this.boids[i].y - this.boids[index].y;
        }
    }
}
getDistance(p1, p2) {
    let dx = p1.x - p2.x;
    let dy = p1.y - p2.y;
    return Math.sqrt(dx * dx + dy * dy);
}


整列(alignment) → 「近くの鳥たちと飛ぶスピードや方向を合わせようとする」

速度や方向が他の要素と離れすぎないように、平均となるベクトルに徐々に近づいていく処理を追加します。

 
alignment(index) {
    let al = {
        x: 0,
        y: 0
    };
    for (let i = 0; i < this.boids.length; i++) {
        if (i !== index) {
            al.x += this.boids[i].vx;
            al.y += this.boids[i].vy;
        }
    }
    al.x = al.x / this.NUM_BOIDS - 1;
    al.y = al.y / this.NUM_BOIDS - 1;
    this.boids[index].vx += (al.x - this.boids[index].vx) / 8;
    this.boids[index].vy += (al.y - this.boids[index].vy) / 8;
}

実行結果

この3つのルールを各要素が計算した実行結果です。

群れといえば群れですが、鳥や魚の動きを再現するにはまだ工夫が必要そうですね。

参考

下記記事が日本語でBoidsについてわかりやすくまとめられています。

マッチ箱の脳 <群れの知能>

コードはありませんが、文章とイラストでBoidsのアルゴリズムについて丁寧に説明されています。

JavaScript,HTML5で『群れ』をシミュレーションするレシピ(ボイド)

アルゴリズムだけはなく、canvasの描画など実装までできるようなJavaScriptのコードでまとめられています。

Boidsは結合、引き離し、整列に対して処理を加えることで、リアルな鳥や魚の動きに近づけたり、応用して他の表現にも利用できる拡張性のあるアルゴリズムです。

Boidsについては引き続きUNIELブログにて更新していく予定なので、ご興味ある方はたまに覗いてみてください。

 JAN.13.2017
SOCIAL NETWORK SHARE :