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

フロッキングアルゴリズムとは

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

詳細はFlocking(behavior)に記載があります。

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

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

とりあえず試してみる

ということで、どんな挙動となるか見てみましょう。
今回実装したものは、こちらから試せます。

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

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

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

サンプルgif

※ 鳥の画像はあまなつブログさんよりお借りしました。

実装

ソースコードはgithubにあげています。

実際にフロッキングアルゴリズムが実装されているのは、src/bird.jsのflocking_move()です。

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

※ ベクトル計算にVictor.jsを使用しています
※ 描画にCreateJSを使用しています

分離

分離は

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

を計算します。

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つはほぼ一緒です。

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

を計算します。

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に足し合わせたベクトルをもとに、整列／結合を行います。

最終速度計算

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

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が求まったら、
ユニットの速度に加算します。

flocking_move()

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

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

終わりに

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

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

楽しいですね！