ビデオゲームの経路探索のためのA*アルゴリズムの巧妙なテクニック
(timmastny.com)- 8ビットのトップダウン型Zelda風ゲームでモンスター追跡を実装するには、単純な直線移動だけでは不十分なため、Dijkstra法とA*を比較しながら、ゲーム向け経路探索の折衷点を探る
- 直線移動は壁に阻まれると止まるが、wall-slidingを加えると壁に沿って動けるようになり、操作感は良くなる一方で、モンスターを地形に閉じ込める戦略要素も生まれる
- Dijkstraアルゴリズムは最短経路を保証するが、開始ノード周辺を広く探索するため、目的地が毎フレーム変わるゲームでは、必要な次の方向以上の計算をしてしまう
- A*は目的地までの距離で探索の優先順位を決め、目的地方向を先に調べ、壁に当たると周辺ノードを調査しつつ、既に見たノードは再訪しないため、迂回経路を見つけられる
- ゲームマップでは、隣接リストをあらかじめ作らない暗黙グラフや、タイル単位探索、反復深さ制限といった幾何ベースのヒューリスティックで、速度と実装難易度を調整できる
ゲームの文脈と基本要件
- PPU466ベースの8ビット・トップダウン型Zelda風ゲームで、モンスターがプレイヤーを追跡する必要があった
- PPU466はPICO-8のようなファンタジーコンソールに近く、8ビットグラフィック、タイルごとに4色、固定背景、少数のスプライトという制約を持つ
- 目標は、モンスターがプレイヤーを追いかけつつも、単に壁にぶつかって止まったり、望ましくない形で閉じ込められたりしないようにすることだった
直線移動とwall-sliding
- 最も単純な方法は、モンスターとプレイヤーの間に直線を引き、その方向へ動かすこと
- この方法だけだと、モンスターは壁に触れた瞬間に停止する
- wall-slidingを適用すると、壁にぶつかったときも止まらず、壁に沿って移動する
- プレイヤー移動では、壁や角の近くでの操作をより反応よくする技法として、ほぼすべてのゲームで使われている
- Pac-Man以降使われており、Pac-Man Championship Edition DX+では、プレイヤーがwall-slideするときにスパーク効果が加えられている
- 直線移動にwall-slidingを加えると、モンスターを特定の地形に閉じ込められるようになる
- 一部のゲームではこれを戦略要素として利用しており、Runescapeのsafespottingがその例
- このゲームでは望ましい挙動ではなかったため、実際の経路探索アルゴリズムを検討した
Dijkstraアルゴリズムの限界
- Dijkstraアルゴリズムは実装が直感的で、最短経路を保証する
- 問題は、必要以上に多くのことをしてしまう点にある
- 開始ノードからグラフ内のすべての他ノードまでの最短経路を求める
- 目的地ノードを見つけた時点で止めることはできるが、特定の目的地方向へ探索を誘導する方法はない
- ビデオゲームではプレイヤーが動き続けるため、モンスターの目的地は毎フレーム変化する
- モンスターに必要なのは完全な経路よりも、今どの方向へ動くべきかという情報に近い
- マップ上のすべてのピクセルやタイルに対する最短経路を事前計算することもできるが、メモリを大量に使う
- レガシープラットフォームやリソース制約の厳しい環境では、Dijkstraは適していない
A*がゲームの経路探索に向いている理由
- A* Search Algorithmは、開始ノードから目的地までの距離情報を使って探索の優先順位を決める
- 最初の段階では、目的地へ一直線に向かう方向を優先して試す
- Dijkstraと異なり、不要であれば反対方向の探索に多くの時間を使わない
- 壁が経路をふさぐと、周辺ノードを調べて壁を回り込もうとする
- Dijkstraと同様に、既に見たノードは再訪しないため、大きく引き返す必要があっても最終的に迂回経路を見つけられる
- 例では、A*を使うモンスターは壁の裏に閉じ込められない
暗黙グラフというデータ構造
- 教科書的なグラフはノード一覧と隣接行列または隣接リストで表現されるが、ゲームでは隣接ノードをもっと柔軟に作れる
- たとえば256×240ピクセルの画面では、各ピクセル座標を1つのノードとみなせる
- 隣接ピクセルは上、下、左、右に加え、対角線方向を含む8方向となる
- 上下左右の移動コストは1、対角移動のコストは√2、つまり約1.4
- 巨大な隣接リストを事前に作らず、実際に訪れるノードに対してだけその場で生成できる
- 壁の上にある、あるいは他のスプライトが占有しているピクセルは有効なモンスター位置ではないため、動的に隣接リストから除外する
- この方式なら、マップエディタで隣接不可ノードを手作業で除外する必要がない
マップの幾何を反映したヒューリスティック
- A*のいくつかの要素は、マップの幾何構造に合わせて直接調整できる
-
ステップサイズ
- ピクセルをノードとして使う代わりに、2Dタイルベースゲームではタイルをノードとして使える
- タイル単位の探索は、プレイヤーまでの経路を見つけるための反復回数を大きく減らし、探索を高速化する
- この場合の経路は、正確な1フレーム単位の移動一覧というより、モンスターが進むべき方向のシーケンスに近い
- モンスターは通常1フレームで1タイル進むわけではないため、タイルベースの経路でも実際に必要なのは、プレイヤーへ到達できる方向の情報である
- ピクセルベースの経路も同様の性質を持ち、モンスターが1フレームに1ピクセル、あるいは整数ピクセル単位で動くとは限らない
-
反復深さ
- A*では、ノードが優先度キューから取り出された時点で、そのノードはそれまでに見つかっている最良経路の最終段階にある
- 固定回数の反復でアルゴリズムを止めると、目的地までの最短経路に対する現時点での最良推定経路が得られる
- アルゴリズムを最後まで実行しなくても、妥当な進行方向は得られる
- 最大反復深さは、レベルの幾何構造に合わせて調整する必要がある
- 深さが小さすぎると、モンスターは依然として壁の裏に閉じ込められる可能性がある
- 例では、固定深さ30タイルだと、プレイヤー位置によってはモンスターが閉じ込められて先へ進めない
- A*を毎フレーム再計算するため、ループが生じることがある
- 壁に到達した最初のフレームでは、下へ進むべきだと計算する
- 次のフレームでは、上へ進むべきだと計算する
- この繰り返しでモンスターがループにはまり込む
- プレイヤーがモンスターの探索範囲内に入れば、正しい経路を見つけられる
- 固定深さ
1ではこの現象がさらに極端になり、モンスターはプレイヤーとのユークリッド距離が最も短いピクセルへ戻り続ける
事前計算という折衷案
- さらに洗練させるなら、マップ上のどの位置からでもA*が経路を見つけるのに必要な最大深さを事前に計算できる
- Dijkstra式の全経路事前計算と違い、保存すべきなのはその最大値1つだけ
- その最大深さが分かっていれば、A*はリアルタイムで有効な経路を見つけられる
1件のコメント
Hacker News の意見
本番環境の MMO で A* に使っていたコツ: 1) 都市単位、建物内の部屋間、部屋の内部のように 階層グラフを用意しておくと、ある都市のある建物、ある部屋の中の点から別の点まででも、ミリ秒未満で探索できる
2) 現在の A* 探索のメタデータをグラフノード自体に保存すれば、別途連想配列を維持しなくて済む
3) 結果の経路をそのままたどるのではなく、可能なときは次の経路ノードへ角を切って進もうとするステアリング挙動の入力として使うほうがよい。別キャラクターへ向かう経路なら、対象キャラクターに「パンくず」を落とさせ、新しい位置が経路の最後のノードから直線移動できないときに経路へ追加するようにする
2b) これを 16 ビットのビットマスクに圧縮する。2 ビット片が 8 個、つまり 8 方向で、ハッシュテーブルに保存する
2c) 各ビット片は 4 つの状態を持つ: FULL_BLOCK（壁）、HARD_BLOCK（どの方向からでもタイルを通過できなくする大きな物体）、SOFT_BLOCK（片側の角の通過を妨げる小さな物体）、NO_BLOCK（空のタイル、またはごく小さな物体があるタイル）
こうすると、建物内のユニットが経路を探すとき、すべてのタイルごとに障害物を検査する必要がない。物体が巨大でなく、回転方向の都合で入口と出口の角を塞いでいなければ、物体のあるタイルも通過できる。最後に、プレイヤーがドアの配置を忘れたときのようにシミュレーションが破綻しないよう、エージェントが壁も通過できるようにする
https://store.steampowered.com/app/2287430/Metropolis_1998/
キャラクターがこのような「泡」の中にいる間は、ワールドとの衝突判定を丸ごとスキップできる
大学時代は RTS で A* がなぜそんなに難しいのか理解していなかったが、ユニット同士がすり抜けないようにするには、動くものすべてが他の全ユニットを常に避けながら経路を再探索しなければならない、という説明を見て Command & Conquer を改めて尊敬した
かなり強い理由がなければ、自分なら避ける
Scala で作った Quoridor AI を高速化するために 高速な経路探索をかなり考え、学んだコツは次の通り
MPAA（Multi-Path Adaptive A*）は、障害物が追加される状況で同じ領域を何度も再探索する必要がある場合に向いている。以前の探索結果を投入して経路探索を高速化できる
JPS（Jump Point Search）は考慮すべき「ノード」数を大きく減らせるため理論上は魅力的だが、ジャンプポイントを探すオーバーヘッドが大きくなり、実際の速度向上はなかった。MPAA と JPS のアイデアを組み合わせる方法はあるかもしれないが、アルゴリズムを創造的にいじっていると、些細な概念上のディテールで簡単に足をすくわれる。たとえば
>=が必要なところで>を使うと、特定の状況で本当の最短経路を保証できないことがあるオープンノードを保存するとき、まともなヒープの代わりに、最大優先度値が比較的小さい整数なら バケット優先度キューも検討に値する。内部配列を優先度でインデックスするため、挿入と取り出しがかなり速くなる
Quoridor は 9x9 グリッドで行われ、プレイヤーがゴールにどれだけ近いか、ゴール到達が可能かを判断するには反復的な経路探索が必須になる。ある位置で可能な手を判断するには、すべての手がゴール到達を不可能にしないことを検査しなければならない。数か月以内に公開する予定で、少なくとも 3 つの意思決定「エンジン」を含めるつもりだ: mtdf（ミニマックスの変種）、MCTS（いくつかのコツを入れた並列版）、catboost を混ぜたハイブリッド
これを通常の直線距離の代わりにヒューリスティック関数用のルックアップテーブルとして使える点がよい。たとえば各ターン開始時に、すでに置かれた壁を反映して Floyd-Warshall アルゴリズムでこのテーブルを初期化できる。似た問題でこの手法により A* をかなり大きく高速化でき、とても単純だった。ただし MPAA や JPS なしの純粋な A* だった
何年も前に PathFinding.js の JPS 実装へ、ジャンプノードを探す再帰探索を可視化する機能を追加した。オンラインデモはこちら: https://qiao.github.io/PathFinding.js/visual/
敵が 2 体以上いるなら、プレイヤー視点で単に Dijkstra を 1 回走らせ、各モンスターがプレイヤーまでの最適経路を参照するようにしたほうが有利になることがある
モンスター数が変わるときの計算コストがより予測しやすくなる
最後のアニメーションの深さが浅すぎる問題は、興味深い挙動に見える。モンスターが「君がどちらへ行くのか見ようと待っている」ように見える
片方へ行くふりをしてから方向転換すれば、だませるのでは？ 幸い人間はこういうことにはかなり寛容で、何でも知能があるかのようにモデル化するようだ
基本的には、敵が毎フレームではなく短い遅延の後にだけ経路を更新するようにすればよいです。そうすれば「慣性」によって既存の経路をたどり、プレイヤーがだませるようになります
ゲームの文脈でのA*の興味深い活用として、2000年代初頭のゲームのコンピュータ対戦相手を作らなければならなかったプログラマーがいた
そのゲームでAIが持つ選択肢を抽象化し、そのグラフ上で最も近い距離をA*で探させた。ワールド上の経路探索という伝統的な用途ではなく、コンピュータが取り得る選択の表現の上で経路を探索し、最短経路が可能な最善戦略を表すようにした点が見事だった
0 - https://www.gamedeveloper.com/design/building-the-ai-of-f-e-...
1 - https://web.archive.org/web/20230804100329/https://alumni.me...
参考資料もある（私のものではない）：https://github.com/agoose77/goap-resources
人間は、自分や他の人間が、経路計画、リスク／リターン評価、6か月後のイベント計画のようにまったく異なる活動にも、似た思考パターンと似た深さの思考を使っていると考えるようだ。さまざまな「探索空間」を共通アルゴリズムに合うグラフとしてエンコードできれば、プレイ中の没入状態ではAIが思慮深く、ほとんど人格を持つかのように見えるもっともらしさが生まれる
大学でA*を学んでいた頃、同時に共有のMinecraftサーバーでその奇妙な問題に遭遇した
サーバーがひどくカクついたのでトレースを取ってみると、ゾンビたちが大きな柵で完全に塞がれた村に入ろうとして、経路探索のループにはまっていた。当時の実装が素朴で、決して諦めなかったということだ
これをどう直すかがかなり詳しく書かれたバグレポートがあったと記憶している
特に複数の動物が全員、通行不能な出入口を通ろうとしている場合、fpsに非常に目に見える影響を与えることがある。もちろん、閉じたドアを通りたいと非常にしつこく要求する猫の行動と見れば、ものすごく現実的だとも言える。ドアを開けてやった途端に猫が即座に気を変え、通ることへの興味を失うなら、さらに現実的だろうけれど！
未知の地形でA*を使うマルチエージェントシステムの論文に興味があるかもしれない：https://www.researchgate.net/publication/333917261_Implement...
この記事とHNスレッドには良いコツがある。まだA*をたくさん使う機会はなかったが、良さそうなHaskellライブラリがあることは知っている：https://hackage.haskell.org/package/astar-monad-0.3.0.0#read...