JavaScript Path Finder Algorithms

Finding the optimal route for a unit to a target on an unknown map is one of the most difficult tasks in developing a game. Fortunately, there are a number of algorithms that solve this problem. There is also an excellent PathFinding.js library with support for 11 such algorithms.

The library is easy to integrate into any web game. They say that it is perfectly optimized for specific architectures, while productivity increases by an order of magnitude.

At http://qiao.github.com/PathFinding.js/visual there is an online demo with nice visualization of algorithm execution. Here, the speed is artificially low (for beauty).

Now 11 algorithms are supported:

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

For the algorithms, three distance calculation heuristics are implemented: Manhattan (the distance of city blocks), the Euclidean metric and the Chebyshev distance . Each of them uses heuristic analysis to determine the prospects of the possible direction of the future path, that is, what is the distance from neighboring squares to the target, in accordance with the definition of distance.