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ブログにて更新していく予定なので、ご興味ある方はたまに覗いてみてください。

 

Hello, and Nice to meet you. I am Goto and I work as a developer at Uniel.

Have you seen the flocking behaviour a group of birds or fish? Today, I am going to write down what I have learnt about the boids – an artificial life program that stimulates the said behaviour of birds.

What is Boids?

The boids is an artificial life program that Craig Reynolds developed in 1987. The boids framework is often used in CG, computer graphics and websites providing realistic-looking representations of flocks of birds and other creatures.

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


The rules applied in the boids are as follows:

  • cohesion:
    a behavior that causes agents to steer towards the centre of mass
  • separation:
    a behavior that causes an agent to steer away from all of its neighbour
  • alignment:
    a behavior that causes a particular agent to line up with agents close by

The boids are made by setting those 3 rules. Now let’s look into the details.

3 rules applied in the boids

Cohesion >> the behavior that causes agents to steer towards the centre of mass

The centre of mass means the place where flockmates are. So you control and navigate the flockmates to move towards the centre of the crowd. Each agent calculates the centre of mass by determining the average position of all nearby boids (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 >> the behaviour that causes to an agent to steer away from its neighbours when they come too close

Whilst in a flock, each boid needs to avoid running into each other. They try to remain separate by calculating a specified amount of space in between themselves and move away from others when get too close.

 
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 >> a behavior that causes an agent to line up with other agents close by

You can make an agent to find the ones within its neighbour radius by adding this function.

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

Putting It All Together

Here is the demo used the 3 rules.

It sort of looks like flockbirds you see in the sky or in the ocean, does it? It probably still needs some improvements to make the movements look more realistic, but you get the gist of it.


Reference

I’ll leave you the links to some websites that might be useful. You can read about boids in Japanese on the website below.

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

This website below does not show coding, but it explains boids very nicely with illustrations.

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

It does not only explain algorithm but also explains about canvas element to draw on screen via JavaScript.

It is possible to enhance this further by adding weights for each rule to tweak the behaviours and change the way the agents move, or even use it to express something else.

I am planning on writing more blogposts about boids in the future, so please come back and check out our blog if you are interested.

 

 JAN.13.2017
SOCIAL NETWORK SHARE :