ランドマーク距離でA*経路探索を高速化

出来事の日付：2026年7月28日

Red Blob Gamesの技術ガイドは、ランドマークノードによって地図の実際の構造に関する情報をヒューリスティックに与え、A*経路探索を改善する方法を説明している。差分ヒューリスティックと呼ばれることが多いこの手法は、選択した地点までの距離を事前計算し、その後の探索で下界として再利用する。

A*は、あるノードからゴールまでの残りコストを推定するためにヒューリスティックを利用する。一般的な距離の公式は開けた空間ではうまく機能するが、壁や通路、その他の制約を理解しない。そのため、利用可能な最短経路が当初は別の方向へ進む場合でも、幾何学的にはゴールへ向かうよう探索を導くことがある。アルゴリズムはそれでも経路を見つけるが、必要以上に多くのノードを調べる可能性がある。

完全なヒューリスティックなら、あらゆる地点から特定のゴールまでの真の最短コストを保存できる。それにより探索は効率化するが、考え得るすべてのゴールについてそのような情報を再計算または保存するのは通常、現実的ではない。ランドマークは、再利用可能な妥協策となる。システムは地図上の各ノードから事前に選んだ1地点までの正確な距離を計算し、その値から別のスタートとゴールの組み合わせに関する情報を導き出す。

数学的な根拠は三角不等式である。ノードBからランドマークLまでのコストと、ノードXからLまでのコストがすでに分かっていれば、その差からBからXまでのコストの下界を得られる。A*は正しさを損なうことなく、その下界を利用できる。ガイドは、この手法がインタラクティブな実演で使われているグリッドだけでなく、グラフ全般に適用できると指摘している。

1つのランドマークが地図全体で一様に役立つわけではない。その価値は、スタート、ゴール、利用可能な経路との相対的な位置によって決まる。そのためガイドは、複数のランドマークを用意し、それらが算出する下界の最大値を採用するよう推奨している。外縁付近や主要な通路の先にある地点が有用な場合もあるが、最適な数と配置は各プロジェクトに固有である。新しいランドマークは、既存の集合に加えて何をもたらすかという観点から評価すべきである。

データの準備には、ランドマークごとに1回の最短経路探索が必要となる。有向グラフについては、保存される値が各ノードからランドマークまでのコストを表すよう、辺を反転させるべきだとガイドは述べている。重み付きグラフにはダイクストラ法を使用し、すべての辺の重みが同じ場合は幅優先探索で十分である。得られた値は、ノードおよびランドマークごとに保存できる。

この最適化で変更するのはAに与えるヒューリスティックであり、A自体ではなく、ほかの改善策と組み合わせることもできる。その代償は、追加の前処理とメモリーである。固定されたゲームマップでは、設計者が制作時にランドマークを配置できる。一方、手続き的に生成されるマップでは、自動サンプリングを使い、多数の代表的な経路を改善する地点を特定できる。完全ではないランドマークでも、事前計算した距離によってより厳密な下界が得られる探索を改善しつつ、通常のヒューリスティックを代替手段として維持できる。