javascriptでフロッキングアルゴリズムで鳥を飛ばす


# フロッキングアルゴリズムとは
フロッキングアルゴリズム(flocking argorithm)とは、
動物の群行動を模式化したアルゴリズムです。
(flockingとは群がりの意味です）。

詳細は[Flocking(behavior)](https://en.wikipedia.org/wiki/Flocking_(behavior))に記載があります。

この手法では、3つの単純なルールで行動を表します。

* 分離（Separation)
	* とくに近くにいる個体から離れようとする
* 整列（Alignment）
	* 近くにいる個体の、平均的な向きへ進もうとする
* 結合（Cohesion）
	* 近くにいる個体の、平均的な位置へ進もうとする


# とりあえず試してみる

ということで、どんな挙動となるか見てみましょう。
今回実装したものは、[こちら](https://alf-ytakada.github.io/flocking_js/dist/)から試せます。

パラメータについては、下記の通りです。

* 視界の視野角度
	* 鳥の目から見える範囲です
* 視界の距離
	* 鳥がどのくらい先まで見えるのかを表します
* 分離距離
	* 分離ルールで使われる、離れようとする距離です

クリックで鳥を追加可能です。

サンプルgif

![flocking_gif.gif](https://qiita-image-store.s3.amazonaws.com/0/129201/dbdfe174-72f3-4e76-6d94-083f815aae73.gif "flocking_gif.gif")



※ 鳥の画像は[あまなつブログ](http://amntudi.blog.fc2.com/blog-entry-121.html)さんよりお借りしました。


# 実装
ソースコードは[github](https://github.com/alf-ytakada/flocking_js)にあげています。

実際にフロッキングアルゴリズムが実装されているのは、[src/bird.js](https://github.com/alf-ytakada/flocking_js/blob/master/src/bird.js)のflocking_move()です。

分離／整列／結合を見てみます。

※ ベクトル計算に[Victor.js](http://victorjs.org/)を使用しています
※ 描画に[CreateJS](http://www.createjs.com/)を使用しています

## 分離

分離は

* 分離ルールでの合計ベクトル
* 分離ルール対象のユニットの数

を計算します。


```javascript:flocking_move()

// 分離ルール
let vec_sep_vel = Victor(0, 0);
 ...

// 分離対象のユニット数
let sep_obj_count   = 0;
 ...
 
    //////////////
    // 分離ルール
    // 決まった距離よりも近いユニットから離れる
    if (distance <= this.separation_length) {
        // 離れる方向のベクトル
        let vec_separation  = new Victor(this_g_pos.x - obj_g_pos.x, this_g_pos.y - obj_g_pos.y);
        // 近いほど強く離す
        const separation_rate = 3 - (vec_separation.length() / this.separation_length);
        vec_separation.multiply(
            new Victor(separation_rate, separation_rate)
        );
        vec_sep_vel.add(vec_separation);
        sep_obj_count++;
    }

``` 

**obj_g_pos**は、近くのユニットの座標を表します。
**this_g_pos**は、自ユニットの座標を表します。

**vec_sep_vel**に近隣ユニットから離れる方向のベクトルを足し合わせます。


## 整列／結合

この2つはほぼ一緒です。

* 整列ルールでの合計速度
* 結合ルールでの合計座標
* 整列／結合ルール対象のユニット数

を計算します。



```javascript:flocking_move()

// 平均位置 : 結合ルール
let vec_ave_pos = Victor(0, 0);
// 平均速度 : 整列ルール
let vec_ave_vel = Victor(0, 0);
 ...

// 近いユニット数
let near_obj_count  = 0;
 ... 


    if (distance <= this.view_length) {
        // 位置加算 : 結合ルール
        vec_ave_pos.add(Victor(obj_g_pos.x, obj_g_pos.y));
        // 速度加算 : 整列ルール
        vec_ave_vel.add(obj.velocity);
        // 近いユニット数加算
        near_obj_count++;
         ...
```

**vec_ave_pos**と、
**vec_ave_vel**に足し合わせたベクトルをもとに、整列／結合を行います。


## 最終速度計算

分離／整列／結合で求めたベクトルをもとに最終的な速度を求めます。

```javascript:flocking_move()

if (near_obj_count > 0) {
    {
        //////////////
        // 結合ルール
        // 向きを平均的な位置へ、速度を平均な速度へ変更
        let vec_this_pos    = Victor(this_g_pos.x, this_g_pos.y);
        let vec_target_pos  = vec_ave_pos.clone().divide(Victor(near_obj_count, near_obj_count));
        // 自分から平均位置への移動量ベクトル
        let vec_mod_pos     = vec_target_pos.clone().subtract(vec_this_pos);
        // 最終操舵力に加算
        vec_steering_force.add(vec_mod_pos.normalize());
        //////////////
    }
    {
        //////////////
        // 整列ルール
        // 移動方向を平均的な移動方向に近づける
        let vec_target_vel  = vec_ave_vel.clone().divide(Victor(near_obj_count, near_obj_count));
        // 自分の移動方向から平均移動方向へのベクトル
        let vec_mod_vel     = vec_target_vel.clone().subtract(this.velocity);
        // 最終操舵力に加算
        vec_steering_force.add(vec_mod_vel.normalize());
        //////////////
    }
    {
        //////////////
        // 分離ルール
        // 移動方向を近くのユニットから離れる方向へ変更
        // 最終操舵力に加算
        if (sep_obj_count > 0) {
            vec_steering_force.add(vec_sep_vel.normalize().multiply(Victor(2, 2)));
        }
        //////////////
    }
}

```

**vec_steering_force**に、最終的な速度が算出されます。

## 速度への反映

vec_steering_forceが求まったら、
ユニットの速度に加算します。


```javascript:flocking_move()

    // 最終操舵力を適用
    // とりあえず減らす
    this.velocity.add(vec_steering_force.divide(new Victor(40, 40)));
```

40で割っているのは、FPS(フレームレート)を60fpsに設定しているためです（そのままだと変化が急すぎる）。
40という値は適当な調整の結果です:grin: 



# 終わりに
今回の実装では、境界面の処理（上下左右の画面境界）をキッチリしていないので、端っこの方では近隣ユニットを見失ってしまいます。
また、分離距離を狭めたりしてユニットを近づけたあと、分離距離を広げ直すとすぐに広がってくれなかったします。これは最小の速度を設定しているためです（離れようとした速度偏位が、正規化により無効化されてしまう）。
これについては、実際のアプリケーションに応じて調整かなぁと思いました。


ということで、3つの分離／整列／結合というルールの組み合わせて、生き物の群れ行動を擬似することができました。

楽しいですね！