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.