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]}.

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 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.

The main idea here is that A* can be fast if you give it (a) a good graph, (b) a good heuristic. You might be used to using the grid as the input graph, and a distance function as the heuristic. Both of these are *easy* (and what I use in my tutorials) but not the *fastest*. The L1 library analyzes the grid map and constructs a smaller graph. It then analyzes the new graph and constructs a better heuristic. The combination of these two makes A* *much* faster than if you use a grid with a distance heuristic. Jump Point Search is well known for being faster than A* with a grid input and distance heuristic, but ordinary A* with an optimized input and optimized heuristic is even faster than Jump Point Search. See the comparison chart on the project page^{[4]} for numbers. Jump Point Search’s main advantage is that it works without preprocessing, which is useful for maps that change frequently.