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.
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). 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 for numbers. Jump Point Search’s main advantage is that it works without preprocessing, which is useful for maps that change frequently.