Clever Geek Handbook

Boids-ユニットグループを移動するためのシンプルなアルゴリズム

あるおもちゃのクローンの開発中に、ユニットのグループをある惑星から別の惑星に移動する必要がありました。 最初に頭に浮かんだのは、ユニットを1つずつスポーンし、それらを直線的に移動させることでした。 しかし、それは非常に面白くはありませんでした-どうにかして惑星を一周する必要がありました。 グループ移動アルゴリズムをざっと見てから、ボイドを試すことにしました。 結果は次のとおりです。







コード例のアルゴリズムの猫の説明の下。





説明


ボイドアルゴリズムは、1986年にクレイグレイノルズによって鳥の群れを動かすモデルとして作成されました。 次の3つのルールに基づいています。



それらへの追加として、私はさらに2つ使用しました。



実装について


ユニットごとに、座標と速度を保存する必要があります。 また、ターゲットと障害物の座標を知る必要があります。 ゲームワールドの再カウント中（たとえば、1秒あたり20回の再カウントが可能）、すべてのユニットの新しい座標と速度を決定する必要があります。 これを行うには、新しいユニットの速度を決定して移動する必要があります。



上記の各ルールでは、速度の一部を取得できます。 ユニットの一般的な速度-ルールを適用した後に取得した速度と、ユニット自体の以前の速度の合計。 

v1 = Rule1(); v2 = Rule2(); v3 = Rule3(); unit.v = v1 + v2 + v3 + unit.v; unit.pos = unit.pos + unit.v;


ユニットがオーバークロックしないように-速度を制限することをお勧めします。 短い間隔で1つのポイントから順番に飛行するユニットをスポーンするのが最適です。



ルールは次のように実装されます。

  1. 凝集度-重心（すべてのユニットの座標の算術平均）を見つけ、現在のユニットから重心に向かうベクトルを決定する必要があります。
  2. 分離-すべての最も近いユニットから平均方向を決定する必要があります。
  3. 速度の均等化-すべてのユニットの平均速度を見つける必要があります。
  4. 目標への移動-ユニットから目標に向かって誘導されるベクトル。
  5. 障害物の回避-2番目の障害物と一致しますが、最も近い障害物から方向を探す必要があります。


実際には、各ルールによって発行される速度は、（何らかの要因で除算することにより）低減または制限する必要があります。 最適な結果を得るために、制限と係数が実験的に選択されます。



コード


そして今、小さなコード。 すべてのユニットを移動するためのメインコード（船-私たちは宇宙船について話している）： pastebin.com/jeHCWr8u上記に加えて、ユニットと惑星や世界外の飛行との衝突もここでチェックされます。 制限速度-制限係数を掛けた正規化ベクトル（方向を表す）： pastebin.com/a57hh76V



ルールの実装： pastebin.com/YDSTDh3t実装機能-一部のルールは、現在のグループのユニットにのみ適用されます（1人のプレイヤーに属し、同じ目標を持っている）。 距離-幾何学的な意味での距離。



船の産卵は次のように実装されます。 各惑星には、産卵を待つ船の列があります。 プレイヤーがコマンドを与えると、複数の船が作成され（エネルギーの量に応じて1〜20）、惑星のキューに追加されます： pastebin.com/FprtwTy4そして、50ミリ秒ごとに1つの船が生成されます： pastebin.com/Tq4cvNbB



長所と短所


このアルゴリズムは、「生きている」ユニットのシミュレーションに適しています。 グループの「群れ」動作が許容される場合に適用するのは良いことです。 ユニットのより厳密な動きを整理する必要がある場合、ほとんどの場合、別のアルゴリズム（またはいくつかの変更）を使用する必要があります。 また、垂直移動中にユニットのグループを別のグループに通過させることもできませんでした-あるグループが他のグループを弾道から押し始め（最終的には側面からそれを迂回しました）-あるグループのユニットは2番目からユニットを通過し始めました（ほとんど回らずに） 。 近づいてくるコースでは、状況は良くなっています。時には、1つのグループが2つ目を2つに分けて中央を通過し、時にはその隣を通過しました。 一般的に、パラメーターを繰り返し実験することにより、Boidsはさまざまな状況に適した見栄えの良い結果を達成します。



参照資料


en.wikipedia.org/wiki/Boids-ウィキペディアのアルゴリズムの説明

www.kfish.org/boids/pseudocode.html-疑似コードboids-ヒューリスティックの説明付き

habrahabr.ru/post/105639-ボイドとそのさまざまなバリエーションの説明（より理論的）

github.com/bakwc/ozifi/tree/master/projects/space_capture-ソース（サーバー/ world.cppでのboidの実装）


More articles:


All Articles