StarCraftとStarCraft 2のルート検索アルゴリズムの比較
Starcraft 2のベータ版をプレイした人は、ユニットの移動経路を見つけるためのアルゴリズムがどのように変更されたかに気づいたでしょう。 この記事で述べられていることの多くは、個人的な評価に基づいています。 私はBroodWarもStarCraft 2もプログラムしませんでした。いくつかの結論は私の推測に基づいています。 また、私の言葉を100％信じないで、あなた自身の結論を下してください。 この記事には、事実と推測の両方が含まれます。
スタークラフト2経路探索の力学の翻訳
StarCraft 2は、「群れ」または「群れAI」（群れ行動、およそ）と呼ばれる経路発見アルゴリズムを使用し、魚群または鳥の群れの動きのタイプに応じてユニットの動きを調整しようとします。 StarCraft 2は、最小数のコントロールポイントを検出し、ユニットが障害物または他のユニットをバイパスするためのスムーズなルートを独立して配置できる高度なアルゴリズムを使用する可能性が非常に高いです。
結果に関しては、Blizzardはアルゴリズムで素晴らしい仕事をしました。 もちろん、これは閉じた領域であり、詳細な情報はありません。 しかし、地図上で200ユニットが完璧に移動するという事実は、アルゴリズムが効率的に機能することを示唆しています。 ゲームコミュニティではこうした技術に多大な努力が注がれているため、Blizzardはこの問題を無視できませんでした。 BroodWarをプレイし始めたとき、私はそれがどのように機能するかを理解しようとして多くの時間を費やしました。
BroodWarでパスを見つける方法は少し異なります。 等尺性マップでは、ユニットは8方向にしか移動できないため、アルゴリズムに多くのプロセッサ時間を費やすべきではありません。 したがって、この状況でのルート検索アルゴリズムは、A *アルゴリズム（A-Star- waveアルゴリズム ）に基づくことができ、ユニットの動きを見ると、この仮定は真実に非常に近いと思います。
broodWarでのA-Starアルゴリズムの適用
この状況でプレーヤーは何を見ますか
マップは、タイルなどの多数のノードで覆われています。 ノードに到達すると、ユニットはどこに移動するか（各ノードに可能な移動方向がある）を認識し、目的地に到達するまで続きます。 ユニットが通過したノードが参照ポイントになります。 ただし、StarCraft 2は小さな半径のルートに沿って他のユニットをバイパスすることで衝突を回避し、BroodWarユニットではノードを競います。 これが、BroodWarよりもStarCraft 2でより良い環境を得る主な理由ですが、逆の効果もあります：ユニットがお互いに向かって移動すると逃げてしまいます。
ミュータリスクは180度回転すると異なる基準点を選択します
多数のキーポイントを設定して、BroodWarアルゴリズムをシミュレートしよう
違いは、BroodWarでは、ユニットはA *アルゴリズムに従って同じキーポイントを使用し、段階的に移動することです。 また、StarCraft 2では、ユニットごとに個別のルートが計算され、最小数のノードが使用されます。
BroodWarでは、衝突保護もより原始的です。 ユニットは、停止して別のユニットを通過したり、新しい移動ルートを計算したりするため、衝突を回避します。 BroodWarでは、労働者による偵察時に、1人のプレイヤーが自分のユニットで偵察を止め、他のプレイヤーが障害物を回避しようとするか、両方のプレイヤーがこの方法でお互いを拘束しようとする状況をよく見ることができます。
StarCraft 2では、ルートを変更することで、ユニットが衝突を避け、障害物を避けます。 各ユニットには衝突センサーがあり、適切なタイミングで障害物を迂回するよう信号を送ると想定するのは論理的です。 また、完全に新しい経路や運動量の損失を計算することなく、ユニットを結合したり、逆にユニットを結合したりすることができます。 最悪の場合、ユニットは衝突の半径を無視できるため、よりスムーズな動きと全体的な動きの効率が向上します。
OpenSteer ：障害を回避するためのオープンソースライブラリ
BroodWarのZergは、誰が最初に走るかを決定します。 StarCraft 2では、zergは事前に展開を開始します。
多くのBroodWarファンは新しいアルゴリズムを好まないため、理由があります。 ゲーム開始時の最も効果的な戦術の1つは、バイパスと環境です。 しかし、敵ユニットが互いに近くに移動する場合、環境はそれほど効果的ではありません。 マリーナが遠くから攻撃するのに対して、ツェルリングはそうではないため、ヒープ内にいないときにマリーナに大きなダメージを与えます。 軍隊の「表面積」を減らす（たとえば、円の形に配置する）と、ユニットのダメージははるかに少なくなります。 したがって、軍隊が大きいほど、そのような戦術の効果は大きくなります。
Flash vs Effort（OSL 3番目の最終ゲーム）。 Flashのマリーナは十分に離れています。 したがって、脇腹から走っているザーグリングは彼らを殺しました。 フラッシュに勝利を要した
別の質問は、理想的には、ユニットの移動に費やされる労力は、その有効性と直接相関する必要があるということです。 つまり ユニットをコントロールしていないプレイヤーはこれに対して罰せられなければなりません。 しかし、Starcraft 2では、アルゴリズムはプレイヤーよりもユニットをうまく制御できるようです。つまり、アクションとは逆の効果が得られます。
ユニットの「間違った動き」は新参者の計画を混乱させる可能性があり、Blizzardにとっては、ゲームが不完全であることを示すことほど悪いことはないと思います。 また、ユニットが不注意に制御されている場合、ユニットは逃げるべきだと考えています。 ゲームのバランスをとるために、人々に「インターフェースとの闘い」を強要するべきではありません。
私自身から、数学的な観点から、Blizzardが非常に優れたアルゴリズムを開発したことを付け加えます。 彼らはそれを公開していたでしょう。
注：この記事は、SC2の公式リリースの前に作成されました。
スタークラフト2経路探索の力学の翻訳
ルート検索
StarCraft 2は、「群れ」または「群れAI」（群れ行動、およそ）と呼ばれる経路発見アルゴリズムを使用し、魚群または鳥の群れの動きのタイプに応じてユニットの動きを調整しようとします。 StarCraft 2は、最小数のコントロールポイントを検出し、ユニットが障害物または他のユニットをバイパスするためのスムーズなルートを独立して配置できる高度なアルゴリズムを使用する可能性が非常に高いです。
結果に関しては、Blizzardはアルゴリズムで素晴らしい仕事をしました。 もちろん、これは閉じた領域であり、詳細な情報はありません。 しかし、地図上で200ユニットが完璧に移動するという事実は、アルゴリズムが効率的に機能することを示唆しています。 ゲームコミュニティではこうした技術に多大な努力が注がれているため、Blizzardはこの問題を無視できませんでした。 BroodWarをプレイし始めたとき、私はそれがどのように機能するかを理解しようとして多くの時間を費やしました。
BroodWarでパスを見つける方法は少し異なります。 等尺性マップでは、ユニットは8方向にしか移動できないため、アルゴリズムに多くのプロセッサ時間を費やすべきではありません。 したがって、この状況でのルート検索アルゴリズムは、A *アルゴリズム（A-Star- waveアルゴリズム ）に基づくことができ、ユニットの動きを見ると、この仮定は真実に非常に近いと思います。
broodWarでのA-Starアルゴリズムの適用
この状況でプレーヤーは何を見ますか
マップは、タイルなどの多数のノードで覆われています。 ノードに到達すると、ユニットはどこに移動するか（各ノードに可能な移動方向がある）を認識し、目的地に到達するまで続きます。 ユニットが通過したノードが参照ポイントになります。 ただし、StarCraft 2は小さな半径のルートに沿って他のユニットをバイパスすることで衝突を回避し、BroodWarユニットではノードを競います。 これが、BroodWarよりもStarCraft 2でより良い環境を得る主な理由ですが、逆の効果もあります：ユニットがお互いに向かって移動すると逃げてしまいます。
ミュータリスクは180度回転すると異なる基準点を選択します
多数のキーポイントを設定して、BroodWarアルゴリズムをシミュレートしよう
違いは、BroodWarでは、ユニットはA *アルゴリズムに従って同じキーポイントを使用し、段階的に移動することです。 また、StarCraft 2では、ユニットごとに個別のルートが計算され、最小数のノードが使用されます。
衝突保護
BroodWarでは、衝突保護もより原始的です。 ユニットは、停止して別のユニットを通過したり、新しい移動ルートを計算したりするため、衝突を回避します。 BroodWarでは、労働者による偵察時に、1人のプレイヤーが自分のユニットで偵察を止め、他のプレイヤーが障害物を回避しようとするか、両方のプレイヤーがこの方法でお互いを拘束しようとする状況をよく見ることができます。
StarCraft 2では、ルートを変更することで、ユニットが衝突を避け、障害物を避けます。 各ユニットには衝突センサーがあり、適切なタイミングで障害物を迂回するよう信号を送ると想定するのは論理的です。 また、完全に新しい経路や運動量の損失を計算することなく、ユニットを結合したり、逆にユニットを結合したりすることができます。 最悪の場合、ユニットは衝突の半径を無視できるため、よりスムーズな動きと全体的な動きの効率が向上します。
OpenSteer ：障害を回避するためのオープンソースライブラリ
BroodWarのZergは、誰が最初に走るかを決定します。 StarCraft 2では、zergは事前に展開を開始します。
多くのBroodWarファンは新しいアルゴリズムを好まないため、理由があります。 ゲーム開始時の最も効果的な戦術の1つは、バイパスと環境です。 しかし、敵ユニットが互いに近くに移動する場合、環境はそれほど効果的ではありません。 マリーナが遠くから攻撃するのに対して、ツェルリングはそうではないため、ヒープ内にいないときにマリーナに大きなダメージを与えます。 軍隊の「表面積」を減らす（たとえば、円の形に配置する）と、ユニットのダメージははるかに少なくなります。 したがって、軍隊が大きいほど、そのような戦術の効果は大きくなります。
Flash vs Effort（OSL 3番目の最終ゲーム）。 Flashのマリーナは十分に離れています。 したがって、脇腹から走っているザーグリングは彼らを殺しました。 フラッシュに勝利を要した
結論
別の質問は、理想的には、ユニットの移動に費やされる労力は、その有効性と直接相関する必要があるということです。 つまり ユニットをコントロールしていないプレイヤーはこれに対して罰せられなければなりません。 しかし、Starcraft 2では、アルゴリズムはプレイヤーよりもユニットをうまく制御できるようです。つまり、アクションとは逆の効果が得られます。
ユニットの「間違った動き」は新参者の計画を混乱させる可能性があり、Blizzardにとっては、ゲームが不完全であることを示すことほど悪いことはないと思います。 また、ユニットが不注意に制御されている場合、ユニットは逃げるべきだと考えています。 ゲームのバランスをとるために、人々に「インターフェースとの闘い」を強要するべきではありません。
私自身から、数学的な観点から、Blizzardが非常に優れたアルゴリズムを開発したことを付け加えます。 彼らはそれを公開していたでしょう。
注：この記事は、SC2の公式リリースの前に作成されました。
All Articles