JavaScriptパスファインダーアルゴリズム

未知のマップ上のターゲットへのユニットの最適なルートを見つけることは、ゲーム開発の最も難しいタスクの1つです。 幸いなことに、この問題を解決する多くのアルゴリズムがあります。 11個のこのようなアルゴリズムをサポートする優れたPathFinding.jsライブラリもあります。



このライブラリは、あらゆるWebゲームに簡単に統合できます。 彼らは、特定のアーキテクチャ向けに完全に最適化されている一方で、生産性は一桁向上すると言っています。



http://qiao.github.com/PathFinding.js/visualには、アルゴリズムの実行をわかりやすく視覚化したオンラインデモがあります。 ここでは、速度は人為的に低速です（美のため）。



現在、11のアルゴリズムがサポートされています。

• AStarFinder
  
  
  
  *
• BreadthFirstFinder
  
  
  
  *
• BestFirstFinder
  
  
  
  
  
  
• DijkstraFinder
  
  
  
  *
• BiAStarFinder
  
  
  
  
  
  
• BiBestFirstFinder
  
  
  
  
  
  
• BiDijkstraFinder
  
  
  
  *
• BiBreadthFirstFinder
  
  
  
  *
• JumpPointFinder
  
  
  
  *
• OrthogonalJumpPointFinder
  
  
  
  *
• Trace
  
  
  
  

アルゴリズムには、 マンハッタン （都市ブロックの距離）、 ユークリッドメトリック、 チェビシェフ距離の 3つの距離計算ヒューリスティックが実装されています。 それぞれは、ヒューリスティック分析を使用して、距離の定義に従って、将来のパスの可能な方向の見通し、つまり、隣接する正方形からターゲットまでの距離を決定します。