AI : 経路探索 Jump Point Search アルゴリズムの JavaScript のデモ

経路探索 Jump Point Search の JavaScript のデモ

  • グリッドに区切った空間の経路探索でよく使われるのは A* アルゴリズムです.
  • それよりも効率的にグリッドの空間を探索する Jump Point Search アルゴリズムの JavaScript のデモがあったので, リンクを貼っておきます.
  • 以下はこのデモの説明です.
  • 下図の緑の位置がスタート地点で, 赤い位置がゴール地点を表していて, 黒い領域が障害物を表しています.

  • 下図が A* で経路探索した結果で, 灰色が探索時に訪れたノードを示しています.

  • 一方で下図が Jump Point Search(JPS)で経路探索した結果です. A* よりも探索時に訪れているのノードがかなり少ないです.

  • 探索空間の開き方を見ていると, JPS の方は障害物の付近まで直線状に移動することを繰り返しているような感じです.
  • こうなる理由や 長所・短所については技術的な詳細についてはまだきちんと調べていないので, 説明できる段階じゃないです.
  • ちょっと気になっているので, 調べてみるかもしれないです.