If you’re running pathfinding on a grid with uniform movement costs and non-diagonal grid (L1) movement, you can make it *much* faster by preprocessing. Here’s a demo of Mikola Lysenko’s pathfinding library, l1-path-finder.

Loading…

Path is tiles long (L1 movement), using pathfinding nodes.

Most grid nodes aren’t needed for pathfinding. The × grid has tiles. The l1-path-finding library reduces the graph from the original walkable tiles to pathfinding graph nodes, and uses landmarks. **Drag the red circles** to calculate a new path. The precalculation took milliseconds and the last path calculation took milliseconds.

It’s a big map. **Every pixel** here is a map tile. The green circles are “landmarks”, a precalculation technique for improving the heuristic. I started writing up notes but haven’t gotten very far; see this for my partial notes.