When building a 3D grid-based dungeon crawler, I ran into a bottleneck around pathfinding. In order to fix this, I instituted two solutions:
This worked well enough that the bottleneck was eliminated, but I kept thinking the same thing: shouldn't my knowledge of a static portion of the map layout allow me to do better than O(N^2) in many cases? In particular, my first urge was to use all-pairs shortest paths, but this turned out to be a dead end, as the characters could block each other's way and using all-pairs would likely cause "queues" of characters heading down particular optimal paths, continually be blocked by each other.
It turns out that you can use the information you know about the map to help
you, and I'll explain how that's relevant in the most general case I can frame
it in. Lets say we have a weighted, directed graph G with all positive
weights. If we have a graph H which has an edge-set which is a subset of
G's, and where each weight of an edge in H is greater-than or equal to the
corresponding weight to that same edge in G, then I claim that the
shortest-path distances in G serve as an admissible heuristic for the A* algorithm
in H.
Why is this true? The heuristic is admissible if it never overestimates the
cost of reaching the goal. As H has the same edges or less, and the edges
which are present have equal or greater value, the shortest-path lengths in G
can only possibly underestimate those in H.
I've implemented this idea for the 2D grid context on Github.