ジャンプポイントサーチ
一様コストのグリッド上でA*を高速化する手法。目立たないマスは一気に飛び越え、経路が実際に曲がり得る地点でのみ止まる。
何もない広いグリッドでは、A*は同じ長さの等価な経路が無数にあるせいで、何千ものマスを無駄に評価してしまう。ジャンプポイントサーチはこの対称性を刈り込む。あるマスから一方向に「ジャンプ」し続け、ゴール、端、あるいは障害物のせいで選択を迫られる「ジャンプポイント」に達したところで止まる。キューに入るのはジャンプポイントだけで、途中のマスは入らない。
この手法は2011年にダニエル・ハラボーとアルバン・グラスティエンが発表した。前処理は不要で、A*とまったく同じ最適経路を返し、開けた地形では一桁速いことも多い。ただし限界ははっきりしている。前提は一様コストのグリッドであり、ナビメッシュや重み付きグラフにはそのままでは使えない。