A* アルゴリズムにおけるランドマークヒューリスティック

1. ヒューリスティクスの役割と課題

A* アルゴリズムは、ゴールへ向かう方向を案内するための**ヒューリスティック（推定値）**を使用します。これを「正しい方向へと風を吹かせるもの」と考えることができます。

• 正しい方向の場合: ヒューリスティックが最短経路と同じ方向（例：東）を示すと、*A は高速に動作**します。
• 誤った方向の場合: ヒューリスティックが最短経路とは異なる方向（例：西のゴールに対して東へ誘導）を示すと、無駄な計算リソースと時間を消費してしまいます。

一般的な距離に基づくヒューリスティックは、「壁」などの障害物情報を無視しているため、誤った方向への誘導を引き起こします。

2. 完璧なヒューリスティックの概念

理想的には、壁や障害物の配置を完全に理解し、決して誤った方向を示唆しない「完璧なヒューリスティック」を使用したいものです。

• 計算の可能性: 「完璧なヒューリスティック」を計算することは可能です。
• 動的変化: このヒューリスティックはゴールの位置や壁の配置に依存します。ゴールが変更されれば、ヒューリスティックも再計算する必要があります。
• 実装上の問題: 各ゴールごとに新しいヒューリスティックを毎回計算するのは現実的ではなく、事前に大量データを保存するサイズも非現実的です。

解決策: 一度計算したヒューリスティック（ランドマーク）を、異なるゴールを持つ複数の A* 実行で再利用することを目指します。

3. 完璧なヒューリスティックの再利用とランドマーク

特定の地点 L（ランドマーク）までの「完璧なヒューリスティック」を計算し、それを別のゴールへの経路推定に適用します。

基本原理：経路の分解

スタート地点 B からランドマーク L への最短経路が既知であれば、その途中にある任意の地点 X への最短経路も同時に得られます。

• 経路関係: $B \to X \to L$
  • 「B から L への経路」は「B から X への経路」と「X から L への経路」を足したものです。
  • 友人が「エッフェル塔（L）へ向かい、途中でダニエル家（X）を経由」と指示する場合、目的地は L ですが、X 経由の方が効率的な道筋を示唆します。

三角形の不等式による下限導出

A* アルゴリズムでは、ヒューリスティック $h(B, X)$ を**経路コストの下限（下界）**として使用します。三角形の不等式 $cost(B, L) \le cost(B, X) + cost(X, L)$ を変形すると、$cost(B, X) \ge cost(B, L) - cost(X, L)$ となります。

• 核心アイデア: すべての地点へのコストを事前計算するのは不可能でも、特定の地点 L へのコストを事前に計算しておけば、他の地点のコストを見積もるのに利用できます。
• 別名: 「三角形の不等式に基づくヒューリスティック」や「差分ヒューリスティック（Differential Heuristic）」とも呼ばれます。

4. 複数のランドマークによる改善

単一のランドマークの有効性は、その地点が経路 $B \to \text{ゴール}$ にある相対的な位置によります。

複数ランドマークの組み合わせ

単一のランドマークではカバーできないすべてのケースに対処するには、複数のランドマーク $L_1, L_2, \dots, L_n$ を使用します。各地点へのコスト見積もりは以下の不等式の最大値（max）を取ります。

$$ cost(B, X) \ge \max(0, \text{cost}(B, L_i) - \text{cost}(X, L_i)) $$

• シャドウエリア: ランドマークが存在する領域で、ヒューリスティックが実際の最短距離より小さくなる（つまり、A* を加速する）ゴールの位置です。
• 動的な影響: スタート地点 B やゴール的位置を変えることで、シャドウエリアの形状や有効性が変化します。

5. ランドマークの配置戦略

ランドマークを効果的に配置するためには、「ゴールの後」にあるという原則を守りつつ、マップ全体のカバレッジを考慮する必要があります。

設計上の考慮点

• 経路の多様性: メイン基地への出入り経路は重要ですが、森や鉱山の間の僻地経路は軽視できる場合があります。
• 優先度の設定: 計算コストが高い長い経路（フレームレート制限の原因になるもの）を最適化するのが優先です。
• マップの性質:
  • 静的マップ: デザインツールの時間を活用して事前に最適な配置を計算できます。
  • 動的マップ: 直近のゴール位置に合わせて、ランダムに新しいランドマークを追加・再配置する必要があります。

ダイナミックな変化への対応

• エッジのコスト減少（例：壁破壊）: ヒューリスティックが高すぎると、最適な経路よりも短い距離を報告し誤った結果になる可能性があります。コストテーブルの更新が必要です。
• エッジのコスト増加（例：壁追加）: ヒューリスティックが低すぎて探索範囲を広げるため、計算時間が長くなりますが、最終的には正しい最短経路を見つけます。

推奨事項: 多くのユニットが通る共通エリアに近い場所に新しいランドマークを追加し、使用頻度の低いランドマークを除外すると効果的です。

6. 自動化された配置手法

ランダムに選定した多数の経路に対して有効な地点を追跡することで、プロジェクト固有でない汎用的な配置アルゴリズムがあります。

• 初期位置: ランダム選択ではなく、**マップの外縁部（左上など）**を選ぶ直感が機能します。
• 追加条件: 次のランドマークは、既存のランドマークから十分離れた場所に選定されます。
  • 2 つ目のランドマーク：1 番目から遠く離れる。
  • 3 つ目のランドマーク：1 番目と 2 番目から同時に遠く離れる。
• 評価基準: 追加される各ランドマークは、それによってもたらす**付加価値（カバレッジの増加）**に基づいて評価・選定されます。

7. 実装ガイド

本手法は A* アルゴリズム自体の変更ではなく、ヒューリスティック関数の値を改良することに留まります。

ステップバイステップの実装

1. ランドマークの選択:

   • マップが既知であればツール内で配置します。
   • 手続き的生成マップの場合は、ランダム化された解析や論文に基づく高度なアルゴリズムを使用します。

2. マップの分析 (プリプロセッシング):

   • cost[nodeId][landmarkId]

     という二次元配列を作成します。
   • 各ランドマーク $L_i$ について、**ダイクストラ法（またはウェイト 1 の場合の幅優先探索）**を実行し、全ノードからそのランドマークまでの最短距離を計算・保存します。
     • 注: 有向グラフの場合にはエッジ方向を反転させて実行します。

   // ランドマーク位置の配列とコスト配列の初期化
   const L = [ /* ランドマークの位置の配列 */ ];
   let L_cost = [ /* array[nodeId] of arrays[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];
       }
   }
   

3. ヒューリスティック関数の修正:

   • 従来の単純距離（マンハッタン距離など）をベースに、ランドマークからの下限値を加算します。
   • $h(B, X) = \max(\text{basic_heuristic}, \text{cost}(B, L_i) - \text{cost}(X, L_i))$

   function heuristicLandmark(startNode, currentNode) {
       let h = heuristicManhattan(startNode, currentNode); // 基礎ヒューリスティック
   
       for (let i = 0; i < L.length; i++) {
           let lowerBound = L_cost[startNode][i] - L_cost[currentNode][i];
           
           // 非有向グラフの場合、差の絶対値を取る
           if (lowerBound < 0) lowerBound = Math.abs(lowerBound);
   
           // より大きな下限値（改善）を持つランドマークを探す
           if (lowerBound > h) { h = lowerBound; }
       }
       return h;
   }
   

この手法はコード量が少なく、既存の A* インフラに容易に統合できます。

8. デモ事例

差分ヒューリスティックを以下のマップで検証しています（いずれも非有向グラフ）。

• ドラゴンエイジ: ザ・サークル・タワー
• コグマインド ファクトリー 5
• ラビリンス
• ドラゴンエイジ: ロテリン
• コグマインド リサーチ 2
• コグマインド ファクトリー 4

結果の可視化

デモでの表示は以下の意味を持ちます：

• 青色領域: ランドマークヒューリスティックにより、検索する必要がなくなったノード（高速化）。
• オレンジ色領域: 依然として通常の検索が必要である部分。

デモごとの特性

1. 不適切な初期配置: ランドマークの位置を微調整することで大幅な性能向上が見られます。
2. ゴールへの接近性: ランドマークは「ゴールに近い側」にあるほど、または「ゴールを超えた後方」に存在するほど効果が大きくなります。
3. ラビリンスでの効果: 単純な距離ベースでは非効率な迷路において、僅か 4 つのランドマークですでに劇的な改善を生みます。
4. オープンワールド: 広大なマップでも同様の原理が適用可能です。

9. さらに読む（参考文献）

グラフ型ヒューリスティックの理論的背景

• "Computing the Shortest Path: A Search Meets Graph Theory" (2004)*
  • ダイクストラ法と双方向 A* を組み合わせ、道路ネットワークやランドマークを使用。
• "Routing information organization..." (1994)
  • インターネットルーティングにおけるランドマーク法の早期応用例。
• "Approximate Distance Oracles" (2005)
  • グラフ内の任意のノード対間の近似距離を計算する一般理論。

座標と距離に基づくアプローチ（逆方向）

• "Predicting Internet Network Distance with Coordinates-Based Approaches" (2002)
  • ランドマーク法を使わず、カルテシアン座標からのユークリッド距離をヒューリスティックとする手法。
• "Euclidean Heuristic Optimization" (2011)
  • ゲームマップの座標系を変換して、距離ベースのヒューリスティックが機能するようにする手法。

圧縮とデータ保存

• "The Compressed Differential Heuristic" (2011)
  • 隣接するノード間の値類似性を利用し、ランドマークデータを画像圧縮のように圧縮・保存する手法。

統合アプローチ

• Hub Labels & Abstraction-Based Heuristics: 「ハブ」または「差分ヒューリスティック」という用語を使い分けつつ、両方の概念を統合した研究が進んでいます。