qiao/pathfinding.js

PathFinding.js is a JavaScript library for finding paths on grid-based maps. If you are building a 2D game or simulation where a character or object needs to navigate from one point to another while avoiding obstacles, this library handles the hard part: figuring out which route to take. The core concept is simple. You define a grid by specifying its width and height, then mark certain cells as blocked (walls, obstacles, water, whatever you want to treat as impassable). You then create a finder, give it a start coordinate and an end coordinate, and it returns a list of grid coordinates representing the path to follow. The library includes eleven different pathfinding algorithms. The most commonly known one is A Star, which finds the shortest path efficiently. Others include Dijkstra, Breadth First, Best First, and Jump Point, plus bidirectional versions of several of these. Not all algorithms are guaranteed to find the shortest possible route, the README marks which ones are. For most game use cases, A Star is the standard choice. There are also options to tune behavior: you can allow diagonal movement (by default only up, down, left, and right are allowed), prevent paths from cutting through corners of blocked cells, and swap between different distance calculation methods (Manhattan, Euclidean, Chebyshev, or Octile) depending on your game's movement rules. After finding a path, utility functions let you smooth it (removing unnecessary zigzags) or compress it down to just the key turning points. The library works both in Node.js and directly in the browser. It comes with an online visual demo showing each algorithm stepping through a grid in slow motion, which makes it easy to see the differences between algorithms at a glance. The project is MIT-licensed.