ダイクストラのアルゴリズムは、開始位置から到達可能なグラフ内のすべてのノードへの最短経路を計算します。あなたの平均的な現代のゲームにとって、それは不必要であり、信じられないほど高価です.
2D と 3D は区別されますが、グラフベースのアルゴリズムでは、検索空間の次元数は違いがないことに注意してください。リンク先の Web ページでは、ウェイポイント グラフとナビゲーション メッシュについて説明しています。どちらもグラフベースであり、原則として任意の数の次元で機能します。「移動先となる明確な正方形のスペース」はありませんが、AI が移動できるスペースには個別の「スロット」があり、ゲーム デザイナーによって慎重に配置されています。
結論として、A* は実際には 2D ゲームと同じくらい 3D ゲームで使用するアルゴリズムです。A* がどのように機能するか見てみましょう:
- 最初に、現在位置と目標位置の座標を知っています。目的地までの距離を楽観的に見積もることができます。たとえば、開始位置とターゲットの間の直線の長さなどです。
- グラフ内の隣接するノードを検討してください。それらの 1 つがターゲット (またはナビゲーション メッシュの場合はターゲットを含む) である場合、完了です。
- 隣接する各ノード (ナビゲーション メッシュの場合、これはポリゴンの幾何学的中心またはその他の種類の中点である可能性があります) について、2 つの測定値の合計としてそこに沿って移動する関連コストを見積もります: パスの長さあなたはこれまでに移動しただろうし、まだカバーしなければならない距離の別の楽観的な見積もり.
- 前のステップからのオプションを、以前に検討したすべてのオプションと一緒に推定コストで並べ替え、推定コストが最も低いオプションを選択します。手順 2 から繰り返します。
ここで説明していない詳細がいくつかありますが、A* が基本的に空間の次元数とは無関係であることを理解するにはこれで十分です。これが連続空間で機能する理由もわかるはずです。
標準の A* 検索で特定の問題を処理する、密接に関連するアルゴリズムがいくつかあります。たとえば、再帰的ベスト ファースト検索 (RBFS) と簡素化されたメモリ制限付き A* (SMA*) は必要なメモリが少なくて済みますが、リアルタイム A* (LRTA*) を学習すると、フル パスが計算される前にエージェントを移動できます。これらのアルゴリズムが現在のゲームで実際に使用されているかどうかはわかりません。
角の丸みに関しては、距離線 (角が円弧に置き換えられる) またはフルパス スムージング用の任意の種類のスプライン関数を使用して行うことができます。
さらに、グラフではなく、検索空間 (空間内の各点が値に関連付けられている) の勾配に依存するアルゴリズムが可能です。これらは、多くの時間とメモリを必要とするため、おそらくほとんどのゲームには適用されませんが、とにかく知っておくと興味深いかもしれません。例には、さまざまな山登りアルゴリズム(既定ではリアルタイム) と潜在的なフィールドメソッドが含まれます。
連続空間から手続き的にグラフを取得する方法も存在します。たとえば、セル分解、ボロノイ スケルトン化、確率論的ロードマップ スケルトン化などです。前者はナビゲーション メッシュと互換性のあるものを生成しますが (手作りのナビゲーション メッシュと同等に効率的にするのは難しいかもしれませんが)、後者の 2 つはウェイポイント グラフに似た結果を生成します。これらはすべて、可能性のあるフィールド メソッドや A* 検索と同様に、ロボット工学に関連しています。
ソース: