A*経路探索のヒューリスティックを改善して、探索ノード数を劇的に削減する方法
Improving Heuristics for A* Pathfinding
A*アルゴリズムの性能は、ヒューリスティック関数の質に大きく依存します。通常の距離ベースのヒューリスティックは壁を考慮しないため、誤った方向に誘導されることがあります。この記事では、事前に計算したランドマークまでの距離を使って、三角形の不等式に基づくより正確なヒューリスティックを構築する「差分ヒューリスティック」を紹介します。複数のランドマークを戦略的に配置することで、A*の探索ノード数を大幅に削減でき、Dragon Age OriginsやCogmindなどの実ゲームのマップで効果を確認できます。実装は簡単で、既存のA*コードを変更する必要はありません。
A*のヒューリスティックは、風が正しい方向に押してくれるようなものだ。しかし、時には間違った方向に押してしまうこともある。
HNでの議論
39- simonw
このテクニックについて知ったのは2007年。その後2015年に記事にしようと試みたが、自分が説明できるほど理解していないことに気づいた。2016年、2018年、2019年、2022年、2024年、2026年と断続的に勉強し続け、このページを何度も諦めては再開した。そして2026年になって、ようやくこのページを書けるほど理解できたと思う。素晴らしい。
- mpmisko
Red Blob GamesにはS級の記事がかなりある。もしこれが少しでも興味深いと思ったなら、さらに探索してみることを強くお勧めする。
- Groxx
くそっ、A*って楽しくて直感的だよな？
ランドマークの集合に対する境界や良い性質を掘り下げるのは面白そうだ。
もし、
- すべてのノードがランドマークから少なくともコスト/距離X離れている
- ランドマーク同士が互いにコスト/距離Y以上離れている
なら、任意の実行でオープンセットのサイズについて多くのことを約束でき始めると思う。
完全なヒューリスティックh*を使ったA*はO(l)で、lは解の長さ（ちょうどlノード展開するかもしれないが、タイの解き方や推測を誤ると、頂点あたりの平均エッジ数倍程度に膨らむ可能性がある）。
良い境界があれば、h*が提供するレールに乗るまでに、展開数/深さが一定量を超えることはないだろう（そして、そこから外れるにも追加の作業が必要になるだろう）。