L1 Shortest Paths

from Red Blob Games

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[1] pathfinding library, l1-path-finder[2].


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 from Dragon Age: Origins (source: movingai.com[3]). 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.

Email me , or tweet @redblobgames, or comment: