A*探索におけるヒューリスティック関数の改善
Improving Heuristics for A* Pathfinding (redblobgames.com)
要約
この記事では、A*探索アルゴリズムの性能を向上させるために、ヒューリスティック関数を改善する方法を解説しています。従来の距離ベースのヒューリスティックは障害物を考慮しないため非効率的ですが、ランドマークを利用した「差分ヒューリスティック」を用いることで、計算コストを抑えつつ、より効率的な経路探索が可能になることを示しています。
全文翻訳
A*探索のためのヒューリスティックの改善
目次
- 1. A*におけるヒューリスティックの使用
- 2. 完全なヒューリスティック
- 3. 完全なヒューリスティックの再利用
- 4. 複数のランドマーク
- 5. ランドマークの配置
- 6. 自動配置
- 7. 実装
- 8. デモ
- 9. さらに読む
2026年7月、しかし2015年以来何度も試行された
私のA*入門ページでは、最短経路を見つけるためのAグラフ探索アルゴリズムの基本を解説しています。ここでは、Dragon Age OriginsのDenerimという町の例を示します。**開始地点Bとゴール地点を移動させて、Aの動作を確認してみてください**:
このページでは、「ランドマークノード」を追加することでA*を高速化する方法を示します。ランドマークLをゴールに近づけてみてください。
ページの最後には、この技術が実際のゲームのマップでどのように役立つかのデモがあります。このページでは可視化にグリッドを使用していますが、ランドマークはグリッドだけでなく、あらゆる種類のグラフで機能します。最も良い点は、コードがそれほど多くなく、時には20行程度で済むことです。他のほとんどの最適化と組み合わせることができます。
1 A*におけるヒューリスティックの使用#
Aは、ゴールに向かうための指針としてヒューリスティック*を使用します。これは、正しい方向に私たちを押し出す風のようなものだと考えることができます。ここでは、ヒューリスティックが私たちを東に押し、最短経路も東に向かっています:
しかし、時には間違った方向に私たちを押し出すこともあります。ここでは、最短経路はBよりも西に向かっていますが、ヒューリスティックは私たちを東に押し出します:
ヒューリスティックが正しい方向に私たちを導くとき、A*はより速く実行されます。ヒューリスティックが間違った方向に私たちを導くとき、時間を浪費します。しかし、なぜ間違った方向に向かうのでしょうか?それは、一般的に使用される距離ベースのヒューリスティックがマップの構造を知らないからです。
2 完全なヒューリスティック#
理想的には、マップの構造を知っていて、決して間違った方向に指し示さないヒューリスティックを見つけたいものです:
この「完全な」ヒューリスティックを計算できるでしょうか?はい!
しかし、完全なヒューリスティックはゴールごとに異なります。ゴールを移動させると、ヒューリスティックが変わるのがわかります。開始地点Bを移動させても、変わらないのがわかります。
同じゴールで多くの経路を計算する場合、フローフィールド経路探索を使用できます。しかし、通常、次の経路は異なるゴールを持つため、A*を実行するたびに新しい完全なヒューリスティックを構築する必要があります。これは、毎回計算するには非現実的に遅く、事前に計算して保存しておきたい場合には大きすぎます。
一度ヒューリスティックを計算し、その後、異なるゴールを持つ複数のA実行でそれを再利用*できれば素晴らしいでしょう。
3 完全なヒューリスティックの再利用#
緑色のLへの完全なヒューリスティックを計算してみましょう。これを「ランドマーク」と呼びます。他のゴールへの経路を再利用できますか?はい、時々できます! 開始地点BとランドマークLを移動させて、どの紫色のゴールが助けられるかを確認してください:
アイデアは、B→L間の経路が既にある場合、途中の任意のゴールへの最短経路も同時に得られるということです:
B L BからLへの経路はXを含む BからXへの経路 XからLへの経路
ランドマークを遠くの何かだと考えてください。友人が「あなたの家Bから、エッフェル塔Lに向かって歩き、ダニエルの家に着くまで」と言ったとします。ゴールはランドマークに到達することではありません。ランドマークは方向を示します。ゴールであるダニエルの家は途中にあります。
ほとんどのゴールはB→Lの経路上にありませんが、時にはその経路に近いこともあります:
B→Lへの経路 BからXへの経路 XからLへの経路
しかし、「近い」とはどういう意味でしょうか?経路長 cost(B, L) を使用できます。経路がほぼ同じ場合、cost(B, L) は cost(B, X) + cost(X, L) に近くなります。
Aでは、経路長 cost(B, X) の下限としてヒューリスティック関数*を使用します。三角形不等式¹によれば、三角形の2辺の合計は3辺目よりも長くなるか等しくなります。有向グラフに適用すると、cost(B, X) + cost(X, L) ≥ cost(B, L) と言えます。下限を計算するために、この不等式を cost(B, X) ≥ cost(B, L) - cost(X, L) と書き換えます。
これがここでの重要なアイデアです。すべての場所へのすべてのコストを事前に計算することは非現実的ですが、特定の場所Lへのコストを事前に計算しておけば、それを別の場所Xへのコストの見積もりとして使用できます。
学術論文の中には、これを三角形不等式に基づくヒューリスティックと呼ぶものもあります。他の論文ではこれを「差分ヒューリスティック」と呼んでいます。なぜなら、既に計算された距離の差を取るからです。
4 複数のランドマーク#
この三角形不等式はどのくらいの頻度で役立つのでしょうか?
cost(B, X) cost(X, L) cost(B, L) ≤ cost(B, X) + cost(X, L)
これは、LがB→Xの経路に対してどこにあるかによって異なります:
| 相対位置 | ランドマークは役立つか? | |
|---|---|---|
| 前 | L B | (無向グラフのみ) |
| 中間 | B L | いいえ |
| 後 | B L | はい |
開始地点Bとゴール地点を移動させて、ランドマークがどこで役立つかを確認してください:
ランドマークLを緑色の塗りつぶし領域の外に移動させて、ヒューリスティックと経路が常に一致しないことを確認してください。
ランドマークはゴールXよりも「後」にある必要があるため、単一のランドマークではすべての経路に役立つわけではありません。複数のランドマークL₁, L₂, L₃などが必要です。それぞれがヒューリスティックの下限を提供します:
cost(B, X) ≥ cost(B, L₁) - cost(X, L₁)
cost(B, X) ≥ cost(B, L₂) - cost(X, L₂)
cost(B, X) ≥ cost(B, L₃) - cost(X, L₃)
…
cost(B, X) ≥ cost(B, Lₙ) - cost(X, Lₙ)
これらの最大値を取ることで、最も高い下限を選択できます。この図では、ゴールを紫色の塗りつぶし領域のいずれかに移動させて、それらの領域がランドマークによってどのように改善されるかを確認してください。次に、塗りつぶされていない領域のいずれかに移動させて、A*がそこでは速くならないことを確認してください。開始地点Bを移動させて、塗りつぶされた領域も開始地点によってどのように依存するかを確認してください。
5 ランドマークの配置#
最適なランドマークの位置は、開始地点BとゴールXの両方に依存します。ゴールXよりも「後」にランドマークを配置したいのですが、「後」がどこかは、開始地点BとゴールXの場所によって異なります。
できるだけ多くの(開始地点、ゴール地点)のペアを改善するためにランドマークを使用したいと考えています。
単一のランドマークから始めましょう。このマップで開始地点B、ゴールX、ランドマークLを移動させてみてください:
紫色の塗りつぶし領域は、ランドマークが役立つゴール位置を示しています。ランドマークは主要な通路をカバーできますが、側室はカバーできないようです。もっと多くのランドマークが必要です:
マップのより多くの部分が紫色で覆われました。ランドマークの数と配置を選択することは、プロジェクト固有です。以下を検討してください:
- すべての経路が等しく可能性が高いですか?例えば、コロニーシミュレーションゲームのDwarf Fortressでは、メインベースとの間の経路を非常に重視し、森と鉱山の間の経路は重視しないかもしれません。
- すべての経路の最適化は等しく価値がありますか?例えば、経路探索がフレームレートを制限している場合、計算に時間がかかる長い経路に焦点を当て、短い経路は無視したいかもしれません。
- マップは静的ですか、それとも時間とともに変化しますか?静的なら、マップデザイナーツールで最適なランドマークを事前計算するために多くの時間を費やすかもしれません。しかし、動的なら、最後のいくつかのゴール位置を使用して新しいランドマーク位置を決定したいかもしれません。
- 変更がエッジコストを減少させる場合、ヒューリスティックは時々過大評価され、コストテーブルを更新するまでA*は最短経路ではない経路を返す可能性があります。経路探索は最適化されますが、最適ではありません。例:プレイヤーが壁を壊しましたが、ユニットはすぐに短い経路を探しません。
- 変更がエッジコストを増加させる場合、ヒューリスティックは期待よりも低くなり、コストテーブルを更新するまでA*の実行に少し時間がかかるようになります。経路探索は最適ですが、最適化されていません。例:プレイヤーが壁を追加したため、ユニットはその領域を安全に歩けると考えますが、それを回避する経路を見つける必要があります。
- 多くのユニットが共通の場所(Dwarf Fortressの食堂など)への経路を見つける場合、使用頻度の低いランドマークを削除し、共通の場所の近くに新しいランドマークを追加することを検討してください。
- マップはオープンワールドですか、それとも制約がありますか?リアルタイムストラテジーゲームは、部屋と廊下で構成されるダンジョンクローラーとは異なるニーズを持つ可能性があります。
- Thomas Nobesは、ランドマークポイントの配置に関する追加のヒントを含むビデオ解説²を提供しています。
幸いなことに、ランドマークが最適でなくても、ある程度役立つ可能性があり、通常のA*ヒューリスティックを使用した場合よりも悪くなることはありません。
6 自動配置#
最適なランドマーク位置はプロジェクト固有ですが、プロジェクトに依存しない方法でランドマークを配置するアルゴリズムの1つは、ランダムに選択された多くの経路に対してどの位置が良いかを追跡することです。ここで試してみてください。ランドマーク位置を見つけることができます:
通常、マップの左上に位置を選びますが、常にそうとは限りません。これは、ランドマークをマップの外縁に配置するという直感と一致しています。
2番目のランドマークは、最初のランドマークから離れた場所にあるべきです。3番目のランドマークは、最初の2つから離れた場所にあるべきです。各後続のランドマークは、それが追加するものを基準に評価されるべきです。これは、2つの既存のランドマークがある場合の様子です:
最初の2つから離れた場所を選びますが、常に同じ場所とは限りません。
7 実装#
このページで説明されている変更は、Aに渡されるヒューリスティック関数に対するものです。A自体を変更する必要はありません。
ランドマークを選択する必要があります。マップが事前にわかっている場合、ランドマークはマップデザイナーツールで配置できます。マップが手続き的に生成される場合、このページの前半にあるランダム経路マップ分析を試してください。末尾の論文のいくつかは、より洗練された配置アルゴリズムを提供しています。
次に、マップを分析する必要があります。数値の2D配列、cost[nodeId][landmarkId] を割り当てます。
各ランドマークについて、ダイクストラ法を実行します。これは「単一始点最短経路」アルゴリズムですが、単一始点ではなく単一終点が必要です。有向グラフでは、すべてのエッジを反転させる必要があります。無向グラフでは、エッジをそのまま使用できます。cost[nodeId][landmarkId] をノードnodeIdからノードlandmarkIdまでの最短経路のコストに設定します。重みがすべて1の場合、ダイクストラ法の代わりに幅優先探索を使用できます。
これは、このページ(無向グラフ)のデモで実行していることの約半分です:
const L = [ /* ランドマーク位置の配列 */ ];
let L_cost = [ /* 配列[nodeId]の配列[landmarkId] */ ];
for (let landmarkId = 0; landmarkId < L.length; landmarkId++) {
let output = dijkstraSearch(L[landmarkId]);
for (let nodeId = 0; nodeId < graph.num_nodes; nodeId++) {
L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId];
}
}
注意:コードはそれほど多くありません。既存のアルゴリズム(ダイクストラ法、A*、またはBFS)を実行し、結果を配列に保存しています。バックグラウンドスレッドで実行することもできます。
次に、ヒューリスティック関数を変更する必要があります。以前のヒューリスティックは distance(B, X) でした。例えば:
function heuristicManhattan(a, z) {
return Math.abs(a.x - z.x) + Math.abs(a.y - z.y);
}
各ランドマークLiは、下限 cost(Lᵢ, X) - cost(Lᵢ, B) を提供します。これらの最大値を取りたいのです:
function heuristicLandmark(B, X) {
let h = heuristicManhattan(B, X); // または任意の基本ヒューリスティック
for (let i = 0; i < L.length; i++) {
let lowerBound = L_cost[B][i] - L_cost[X][i];
lowerBound = Math.abs(lowerBound); // 無向グラフの場合
if (lowerBound > h) { h = lowerBound; }
}
return h;
}
注意:コードはそれほど多くありません。既存のヒューリスティック(通常はマンハッタン、チェビシェフ、またはユークリッド距離)を実行し、ランドマークが良好な三角形を形成する場合にそれを増加させます。
Aコードで変更されること:何もありません*。
A*を高速化するための多くのテクニックがあります。私はこのテクニックが好きです。なぜなら、コードが非常に少ないからです。主な欠点は、より多くのメモリを使用することです(ランドマークの数 × グラフノードの数 × 数値のサイズ)。
8 デモ#
Dragon Age(movingai.comから提供)、迷路(同じくmovingai.comから提供)、およびCogmind(Josh Geから提供されたマップ)のマップで差分ヒューリスティックを試しました。これらのマップはすべて無向グラフ(エッジは双方向)であるため、差分ヒューリスティックのそのバージョンを使用しました。
- 青い領域は、差分ヒューリスティックを使用することで検索する必要がなくなった範囲です。オレンジ色の領域は、改善されたヒューリスティックを使用しても検索する範囲です。
- 開始地点Bとゴール地点を移動させて、さまざまな経路でのパフォーマンスを確認してください。
8.1 Dragon Age, The Circle Tower
初期のB→経路に対してランドマークが配置されています。移動させてみてください。
8.2 Cogmind, Factory 5
次のデモでは、ランドマークLは役に立たない場所にあります。改善するために移動させてください。
青い領域は、検索する必要がなくなったノードです。青い領域が多いほど良いです。
ランドマークLは、ゴール地点よりも開始地点Bに近い場合に、より役立ちます。ゴール地点よりも「後ろ」にある場合に役立ちます。開始地点Bとゴール地点を移動させて、どの経路を見つけたい場合でも、大きな改善があることを確認してください:
しかし、その改善を得るには多くのランドマークが必要でした。ランダム経路マップ分析を使用して、ランドマークの数を減らし、より賢い場所に配置することで、より良い結果を得ることができます:
8.3 Maze
距離ヒューリスティックを使用したAは迷路で特に悪い挙動を示しますが、この迷路では、わずか4つのランドマークで大きな違いが生まれます!次に、ランダム経路をクリックしてみてください。青い領域は、ランドマークを使用して検索する必要がなかった*領域です。双方向フラグを切り替えて、それがどれだけ違いを生むかを確認してください。
8.4 Dragon Age, Lothering
このマップは広い開けた領域があり、ランドマークとうまく機能するようです。
8.5 Cogmind, Research 2
これはCogmindの部屋と廊下で構成されたマップです。
8.6 Cogmind, Factory 4
これは、伝統的なローグライクダンジョンでよく見られる、部屋と廊下で構成された別のマップです。
9 さらに読む#
このページは、ゲームマップでデカルト座標を使用して、「ランドマーク」ノード(「ピボット」または「ビーコン」とも呼ばれる)に基づいたグラフベースのヒューリスティックを構築することについてです。いくつかの参考文献を収集しましたが、すべてを読んだわけではないため、一部間違っている可能性があります。
- 2004年 Computing the Shortest Path: A* Search Meets Graph Theory⁵(Goldberg, Harrison)[ミラー⁶]。この論文でこの技術を知りました。これは、道路ネットワークで使用される双方向A*探索とランドマークベースのヒューリスティックの組み合わせです。「ランドマーク」と「三角形不等式」という用語を使用しています。
- 1994年 Routing information organization to support scalable interdomain routing with heterogeneous path requirements(Hotz)。[引用⁷] オンラインでコピーを見つけることはできませんが、インターネットルーティングのためにランドマークを使用した三角形不等式の導入に関する研究のようです。
- 2005年 Approximate Distance Oracles(Thorup, Zwick)[ミラー⁸]。この理論論文は、距離オラクル⁹を使用して、グラフ内の任意のノードペア間の近似距離を計算するという、より一般的なトピックを扱っています。近似距離は、A*におけるヒューリスティックとして必要なものです。
逆に進むことも可能です。多くのグラフには自然なデカルト座標がなく、デカルト座標がある場合でも、距離ベースのヒューリスティックから良好な結果が得られない場合があります。
- 2002年 Predicting Internet Network Distance with Coordinates-Based Approaches¹⁰(Ng, Zhang)[ミラー¹¹]。この論文では、ランドマークベースのヒューリスティックを使用して、インターネットルーティングネットワーク内のノードにデカルト座標を割り当てています。その後、ヒューリスティックにユークリッド距離を使用しています。これは、このページで行っていることの逆で、既にデカルト座標を持っているが、代わりにランドマークベースのヒューリスティックを使用したい場合です。
- 2011年 Euclidean Heuristic Optimization¹²(Rayner, Bowling, Sturvetant)は、距離ヒューリスティックがうまく機能しないゲームマップ上のデカルト座標を、距離がうまく機能する新しいデカルト座標に変換します。
ランドマークデータの保存には、ノードあたり1つの数値が必要です。典型的なゲームマップでは、それらの数値はグリッドスペース間で非常に似ていることが多いです。画像圧縮が近くのピクセルが似た値を持つことを利用するのと同じように、近くのグラフノードが似た値を持つという事実を利用して、ランドマークデータを圧縮したい場合があります:
- 2011年 The Compressed Differential Heuristic¹³(Goldenberg, Sturvetant, Felner, Schaeffer)- 同じ量のスペースにより多くのランドマークを保存することで、ヒューリスティックを改善できます。この論文では、「ランドマーク」は「ピボット」と呼ばれ、「ランドマークベースのヒューリスティック」は「差分ヒューリスティック」と呼ばれます。
このページで使用されているランドマークLは、経路の終点の後に配置されているため、レイアウトはB→X→Lとなります。経路の途中にランドマークを配置するアルゴリズムもあります。B→L→L→L→X。ここではそのトピックは扱っていませんが、興味がある場合は以下を参照してください:
- 2008年 Approximating Shortest Paths using Landmarks¹⁴(Grant, Mould)。「ランドマーク」と呼んでいます。
- 2014年 Hub Labels: Theory and Practice¹⁵(Delling, Goldberg, Savchensko, Werneck)。「ハブ」と呼び、B→L→Xの経路で単一の中間点のみを使用します。
- 2009年 Abstraction-Based Heuristics with True Distance Computations¹⁶(Felner, Barer, Sturvetant, Schaeffer)。この論文は、「ランドマーク」アプローチの両方を統一しようとしていると信じています。B→X→Lは「差分ヒューリスティック」と呼ばれ、B→L→L→L→Xは「標準ヒューリスティック」と呼ばれ、これら両方が「真の距離ヒューリスティック」という傘の下にあります。
この技術を2007年に知りました。その後、2015年に執筆を試みました。それを説明するほど理解していないことに気づきました。2016年、2018年、2019年、2022年、2024年、2026年に断続的に研究しました。このページを何度も放棄し、再開しました。そして2026年までに、このページを書くのに十分なほど理解していると思います。しかし、まだ実際のプロジェクトで使用したことはありません。