フロッキングアルゴリズムとは
フロッキングアルゴリズム(flocking argorithm)とは、
動物の群行動を模式化したアルゴリズムです。
(flockingとは群がりの意味です）。
詳細はFlocking(behavior)に記載があります。
この手法では、3つの単純なルールで行動を表します。
- 分離（Separation)
- とくに近くにいる個体から離れようとする
- 整列（Alignment）
- 近くにいる個体の、平均的な向きへ進もうとする
- 結合（Cohesion）
- 近くにいる個体の、平均的な位置へ進もうとする
とりあえず試してみる
ということで、どんな挙動となるか見てみましょう。
今回実装したものは、こちらから試せます。
パラメータについては、下記の通りです。
- 視界の視野角度
- 鳥の目から見える範囲です
- 視界の距離
- 鳥がどのくらい先まで見えるのかを表します
- 分離距離
- 分離ルールで使われる、離れようとする距離です
クリックで鳥を追加可能です。
サンプルgif
※ 鳥の画像はあまなつブログさんよりお借りしました。
実装
ソースコードはgithubにあげています。
実際にフロッキングアルゴリズムが実装されているのは、src/bird.jsのflocking_move()です。
分離／整列／結合を見てみます。
※ ベクトル計算にVictor.jsを使用しています
※ 描画にCreateJSを使用しています
分離
分離は
- 分離ルールでの合計ベクトル
- 分離ルール対象のユニットの数
を計算します。
// 分離ルール
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つはほぼ一緒です。
- 整列ルールでの合計速度
- 結合ルールでの合計座標
- 整列／結合ルール対象のユニット数
を計算します。
// 平均位置 : 結合ルール
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に足し合わせたベクトルをもとに、整列／結合を行います。
最終速度計算
分離／整列／結合で求めたベクトルをもとに最終的な速度を求めます。
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が求まったら、
ユニットの速度に加算します。
// 最終操舵力を適用
// とりあえず減らす
this.velocity.add(vec_steering_force.divide(new Victor(40, 40)));
40で割っているのは、FPS(フレームレート)を60fpsに設定しているためです（そのままだと変化が急すぎる）。
40という値は適当な調整の結果です
終わりに
今回の実装では、境界面の処理（上下左右の画面境界）をキッチリしていないので、端っこの方では近隣ユニットを見失ってしまいます。
また、分離距離を狭めたりしてユニットを近づけたあと、分離距離を広げ直すとすぐに広がってくれなかったします。これは最小の速度を設定しているためです（離れようとした速度偏位が、正規化により無効化されてしまう）。
これについては、実際のアプリケーションに応じて調整かなぁと思いました。
ということで、3つの分離／整列／結合というルールの組み合わせて、生き物の群れ行動を擬似することができました。
楽しいですね！