L1 Shortest Paths
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].
Hasnain says:
Bookmarking for later reading.
"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."
Posted on 2024-07-29T03:25:12+0000