A* （エー・スター）
- グラフの最短経路を見つけるための最良優先探索アルゴリズム
- 始点からのコストを、終点からのコストをとし、その和を評価関数とする
- コストは、より小さな値を見つけるたびに更新される
- コストは、厳密に決められないので、ヒューリスティックな（推定の）関数を使う
- 始点から隣接ノードへ徐々に手を伸ばし、が小さくなるように更新しながらのノードを見つけることで、始点へ最小コストで戻る逆順の経路を見つけることができる
- 空間をグラフで表現することで、目的地までの経路探索に利用できる
- 障害物に相当するノードを取り除いたり
- ユークリッド距離（８方向）にしたりマンハッタン距離（４方向）にしたり
- エッジに重みを加えて、歩きやすいエリアを設定したり
貪欲法
- 始点を訪問済みとし、その後、キューに入れる
- 最も良い評価値を持つノードをキューから取り出して現在地とする
- 現在地が見つからなければ、探索は失敗となる
- 現在地が終点であれば、探索は成功となる
- 訪問済みでなく、現在地から探索可能なノードごとに：
- 現在地を経由したときの評価値のほうがより良い場合、対象ノードの評価値を上書きする
- 対象のノードを訪問済みとし、その後、キューに入れる
- 2に戻る
JPS (Jump Point Search)
- どの道を通っても結果として同じことになる経路を剪定してA*を最適化する手法
- 進行方向に対して後方のノードは、親からの経路のほうが最適なので、無視できる
- 進行方向に対して斜め前のノードは、横に障害物がなければ親からの経路と同じものになるので、無視できる
- 進行方向に対して前のノードは、現在地を経由するほうが最適なので、無視できない
- 一様なコスト分布を持つ二次元の矩形グリッド上で可能
- 無視できないノードのみを考えることで処理するノード数を削減できる
- ジャンプ先を事前に計算しておくこともできる
アルゴリズム
- A*における隣接ノードの代わりにjump point successorを使う
- 上下左右では：
- 進行方向に対して(左|右)に障害物があり、かつ、対応する(左|右)斜め前に障害物がないか調べる
- そうであれば、そのノードをjump point successorとする
- そうでなければ、一歩進んで同様の処理を繰り返す
- 斜めでは：
- 進行方向に対して(左|右)斜め前方向に、上下左右の場合と同様の条件のノードがあるか探す
- それがあれば、その開始地点のノードをjump point successorとする
- それがなければ、一歩前へ進んで同様の処理を繰り返す
- 上下左右では：
Subgoal Graph
Goal Bounding
参考文献
- https://www.youtube.com/watch?v=-L-WgKMFuhE&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
- https://ja.wikipedia.org/wiki/A%2A
- https://ja.wikipedia.org/wiki/%E6%9C%80%E8%89%AF%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
- https://harablog.wordpress.com/2011/09/07/jump-point-search/
- https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search/
- https://gdcvault.com/play/1022094/JPS-Over-100x-Faster-than