A*探索におけるヒューリスティック関数の改善

2026年7月、しかし2015年以来何度も試みられてきました。A*の最適化では、通常、優先度付きキューやマップ表現に注目します。しばしば見過ごされるのは、ヒューリスティック関数の改善です。これは、Dragon Age OriginsのDenerimの町からの例です。開始地点Bとゴールを移動させて、A*の動作を確認してみてください。次に、緑色のLを紫色のゴールに近づけてみてください。ヒューリスティック値が真の距離に近づくにつれて、A*が探索する必要のあるノードの数は、からに減少します。青い領域が節約分です。この記事では、ヒューリスティックを改善してA*を高速化する方法を示します。記事の最後には、実際のゲームのマップを使ったこのテクニックを示します。 1 A*におけるヒューリスティックの使用 A*は、ゴールに向かうためのガイドとしてヒューリスティックを使用します。これは、私たちを正しい方向に押す風のようなものだと考えることができます。ここでは、ヒューリスティックが私たちを東に押し、最短経路は東に向かっています。しかし、時にはそれは私たちを間違った方向に押します。ここでは、最短経路は西ですが、ヒューリスティックは私たちを東に押します。ヒューリスティックが私たちを正しい方向に導くとき、A*はより速く実行されます。ヒューリスティックが私たちを間違った方向に導くとき、それは時間を無駄にします。しかし、なぜ間違った方向なのでしょうか？それは、通常の距離ベースのヒューリスティックが壁を知らないためです。 2 完璧なヒューリスティック 理想的には、壁を知っていて決して間違った方向に指さないヒューリスティックを見つけたいと思います。この「完璧な」ヒューリスティックを計算できますか？はい！しかし、完璧なヒューリスティックは、ゴールと壁の構成ごとに異なります。ゴールを移動すると、ヒューリスティックが変わるのがわかります。開始地点Bを移動すると、それは変わらないことがわかります。ゴールと壁が同じままであれば、フローフィールドパスファインディングを使用できます。しかし、通常、ゴールは同じではないため、各ゴールに対して新しい完璧なヒューリスティックを構築する必要があります。これは、A*を実行するたびに計算するには非現実的に遅く、事前に計算しておきたい場合は保存するには非現実的に大きすぎます。一度ヒューリスティックを計算して、さまざまなゴールを持つ複数のA*実行で再利用できれば便利です。 3 完璧なヒューリスティックの再利用 緑色のL、これを「ランドマーク」と呼びますが、そこへの完璧なヒューリスティックを計算しましょう。別のゴールに再利用できますか？はい、時々！開始地点BとランドマークLを移動させて、どの紫色のゴールが助けられるかを確認してください。アイデアは、B→Lからのパスが既にある場合、途中にある任意のゴールへの最短パスも得られるということです。 B L BからLへのパスはXを含みます BからXへのパス XからLへのパス ランドマークを遠くの何かのように考えてください。友人が「あなたの家Bから、エッフェル塔Lに向かって歩き、ダニエルさんの家Xに着くまで」と言ったとします。ゴールはランドマークに到達することではありません。ランドマークは進むべき方向を示します。ゴールであるダニエルさんの家は途中にあります。ほとんどのゴールはB→Lのパス上にありませんが、時々そのパスの近くにあります。 BからLへのパス BからXへのパス XからLへのパス しかし、「近い」とはどういう意味でしょうか？パスの長さ、コスト(B, L)を使用できます。パスがほぼ同じ場合、コスト(B, L)はコスト(B, X) + コスト(X, L)に近くなります。A*では、ヒューリスティック関数をパス長の低位境界として使用します。コスト(B, X) ≥ コスト(B, L) - コスト(X, L)。これは、三角形の不等式[1]が、三角形の2辺の合計は、3辺よりも長くなるか等しくなるというものです。有向グラフに適用すると、コスト(B, X) + コスト(X, L) ≥ コスト(B, L)と言えます。低位境界を計算するために、この不等式をコスト(B, X) ≥ コスト(B, L) - コスト(X, L)と書き換えます。これはここでの鍵となる考え方です。すべての場所へのすべてのコストを事前に計算することは非現実的ですが、特定の場所Lへのコストを事前に計算しておけば、それを別の場所Xへの推定コストに使用できます。学術論文の中には、これを三角形の不等式に基づくヒューリスティックと呼ぶものもあります。他の論文では、これは「差分ヒューリスティック」と呼んでいます。なぜなら、すでに計算された距離の差を取るからです。 4 複数のランドマーク この三角形の不等式はどのくらいの頻度で役立つのでしょうか？ コスト(B, X) コスト(X, L) コスト(B, L) ≤ コスト(B, X) + コスト(X, L) これは、LがパスB→のどこにあるかによって異なります。 相対位置 ランドマークが役立つか Lの前 Bのみ（無向グラフの場合） 中間 B L いいえ 後 B L はい 開始地点Bとゴールを移動させて、ランドマークが役立つ場所を確認してください。ランドマークLを緑色の塗りつぶし領域の外に移動させて、ヒューリスティックとパスが常に一致するわけではないことを確認してください。ランドマークはゴールより「後」にある必要があるため、単一のランドマークではすべてのパスに役立つわけではありません。複数のランドマークL₁, L₂, L₃などが必要です。それぞれがヒューリスティックの低位境界を提供します。 コスト(B, X) ≥ コスト(B, L₁) - コスト(X, L₁) コスト(B, X) ≥ コスト(B, L₂) - コスト(X, L₂) コスト(B, X) ≥ コスト(B, L₃) - コスト(X, L₃) ... コスト(B, X) ≥ コスト(B, Lₙ) - コスト(X, Lₙ) これらの最大値を取ることで、最も高い境界を選択できます。この図では、ゴールを紫色の塗りつぶし領域のいずれかに移動させて、それらの領域がランドマークによってどのように改善されるかを確認してください。次に、塗りつぶされていない領域のいずれかに移動させて、A*がそこでは速くならないことを確認してください。開始地点Bを移動させて、塗りつぶされた領域も開始地点によってどのように依存するかを確認してください。 5 ランドマークの配置 最適なランドマークの位置は、開始地点Bとゴールに依存します。ランドマークはゴールの「後」にあるべきですが、「後」がどこにあるかは、開始地点Bとゴールがどこにあるかによって異なります。ランドマークを使用して、可能な限り多くの(開始地点、ゴール)ペアを改善したいと考えています。単一のランドマークから始めましょう。このマップで開始地点B、ゴール、ランドマークLを移動させてみてください。紫色の塗りつぶし領域は、ランドマークが役立つゴールの位置を示しています。ランドマークは主要な通路をカバーできますが、側室はカバーできないようです。さらに多くのランドマークが必要です。マップの大部分が紫色で覆われました。ランドマークの数と配置の選択は、プロジェクト固有です。考慮事項：すべてのパスは等しく可能性が高いですか？例えば、Dwarf Fortressのようなコロニービルダーゲームでは、メインベースとの間のパスを非常に重視するかもしれませんが、森と鉱山の間のパスは重視しないかもしれません。すべてのパスは最適化する価値が等しいですか？例えば、パスファインディングがフレームレートを制限している場合、計算に時間がかかる長いパスに焦点を当てたいかもしれませんが、短いパスはそうではありません。マップは静的ですか、それとも時間とともに変化しますか？静的なら、最適なランドマークを事前に計算するために、マップデザイナーツールに多くの時間を費やすかもしれません。しかし、動的なら、最後のいくつかのゴール位置を使用して新しいランドマーク位置を決定したいかもしれません。変更がエッジコストを削減すると、ヒューリスティックは時々過大評価され、コストテーブルを更新するまでA*は最短パスを返しません。パスファインディングは最適化されていますが、最適ではありません。例：プレイヤーが壁を壊しましたが、ユニットはすぐに短いパスを探しません。変更がエッジコストを増加させると、ヒューリスティックは望ましいよりも低くなり、コストテーブルを更新するまでA*の実行に少し時間がかかります。パスファインディングは最適ですが、最適化されていません。例：プレイヤーが壁を追加したため、ユニットはその領域を安全に歩けると考えてしまうかもしれませんが、その周りにパスを見つける必要があります。多くのユニットが共通の領域（Dwarf Fortressの食堂など）へのパスを見つける場合、最も使用されていないランドマークをドロップし、共通の領域の近くに新しいランドマークを追加することを検討してください。マップはオープンワールドですか、それとも制約がありますか？リアルタイムストラテジーゲームは、部屋+廊下のダンジョンクローラーとは異なるニーズを持つ可能性があります。Thomas Nobesは、ランドマークポイントの配置に関する追加のヒントを含むビデオ解説[2]を公開しています。幸いなことに、ランドマークが最適でなくても、いくらか役立つ可能性があり、通常のA*ヒューリスティックを使用した場合よりも悪くなることはありません。 6 自動配置 最適なランドマークの位置はプロジェクト固有ですが、プロジェクトに依存しない方法でランドマークを配置するアルゴリズムの1つは、ランダムに選択された多くのパスにとって良い場所を追跡することです。ここでランドマーク位置を見つけるために試してみてください：（アニメーション開始）これは通常、常にではありませんが、左上隅の場所を選択します。これは、ランドマークがマップの外縁に配置されるべきであるという直感と一致します。2番目のランドマークは、最初のランドマークから離れているべきです。3番目のランドマークは、最初と2番目のランドマークから離れているべきです。