階層型経路探索
マップを粗い領域に分け、まず領域間の大まかな経路を探し、次に各領域内で詰める手法。
広いマップは、抽象化すると探索が安くなる。マップをクラスタに分割し、クラスタの出入口とそれらの間のリンクだけを抽象グラフに引き上げる。A* はまずこの小さなグラフを解いて(経路がどの領域を通るか)、次に各区間を局所的に詰める。最もよく引用される変種は Botea、Müller、Schaeffer による HPA*(2004年)だ。
入り組んだ広いレベルでは効果が大きく、抽象探索が触るノードはごく一部で済む。代償は、経路が最短とは限らず「準最適」になること。ゲームではほぼ常にそれで十分である。クラスタ内ではジャンプポイントサーチ、細かい形状にはナビメッシュと相性がよい。