@flare-engine/pathfinding
Grid pathfinding — A* (findPath), Jump-Point Search (findPathJPS) for uniform-cost grids (a weighted grid delegates to A*, see below), and a polygon navmesh fallback (findNavMeshPath). Pure data, no classes. Heuristics (manhattanDistance, octileDistance, chebyshevDistance, euclideanDistance) are exported as named functions for tree-shake.
Status: beta — no production consumer yet. Every other
@flare-engine/*package is exercised by a shipping game; this one is not. The API is covered by tests and the algorithms are correct for the cases below, but it has not been through the shakedown that real use provides. Treat signatures as stable and behaviour as less battle-tested than the rest of the scope.
findPath and findPathJPS disagree about corner cutting
They are not drop-in replacements for each other. Given a diagonal step whose two shared cardinal neighbours are both blocked:
. X . start (0,0), goal (1,1)
X . . findPath → null (refuses to squeeze the corner)
. . . findPathJPS → [{x:0,y:0},{x:1,y:1}] (takes the diagonal)
findPath requires both cardinal neighbours of a diagonal to be walkable; findPathJPS does not.
Swapping one for the other to gain speed therefore changes movement semantics, and on a map with
tight diagonal gaps it changes which routes exist at all. Pinned by tests in
tests/jps.test.ts. If your game's collision shape is a circle or box wider than a point, you
almost certainly want findPath's rule.
findPathJPS on weighted grids
JPS pruning is only correct when every walkable tile costs 1. If any tile's cost is above 1,
findPathJPS detects it with one linear scan of grid.data and delegates the call to findPath
with diagonal: true, forwarding maxIterations and heuristic. The result is a cost-correct
weighted A* path — with A*'s corner-cutting rule above, not JPS's — never a JPS path that ignored
the costs. A grid whose tiles all share a cost above 1 (createGrid({ defaultCost: 2 })) delegates
on every call too: same path as JPS, cost doubled to the true weighted total, and no JPS speed-up.
Keep every cost at 1 to get the JPS speed-up.
Install
bun add @flare-engine/pathfinding
Usage
import { createGrid, setWalkable, findPathJPS, octileDistance } from '@flare-engine/pathfinding';
const grid = createGrid({ width: 32, height: 32 });
setWalkable(grid, 5, 5, false);
const result = findPathJPS(grid, 0, 0, 30, 30, {
heuristic: octileDistance,
});
if (result !== null) console.log(result.path);
See API spec.
License
Apache-2.0