I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's based on a distance-estimating heuristic you provide to it. The heuristic you provide must be able to tell the program, for any given position: 'This position is at least this far away from the destination'. The most simple heuristic being to use Pythagoras's theorem to get the distance "as the crow flies" between said point and a destination.
Now, the thing that interested me is that A* efficiency is tied to the preciseness of your 'getMinDistance' function. If it returns a value too low, the algorithm takes longer. If it returns a value too high, A* may return a non-optimal path. If it always returns 0, you have Dijkstra's algorithm. (also the heuristic must be monotonic, read the wikipedia articles for more details)
The heuristic I thought about goes like this:
Using any method of your choosing, split the graph into regions. Designate a node of each region as the region's center (ideally, its centroid). The graph traversal distance between any node and its region's center should be trivially computable (or cached).
Store the exact graph traversal distance between the centers of every single region. If you have N regions, you should end up with N² distances.
For any two points A and B, and their respective region's centers Ra and Rb, the graph traversal distance AB is superior or equal to
RaRb - (RaA+RbB)
The smaller the regions are, the closer this heuristic gets to the actual traversal distance AB.
My questions are:
Is this algorithm actually admissible? I have no idea how to formally prove it.
How efficient is this heuristic? My guess would be "Very if you have a lot of small groups, because A* only examines nodes within the groups that include the optimal path", but again, I'm not sure it's true and I don't know how to prove it.
Was this idea ever published before? If so, what is it called and where can I read about it?
In the same vein, are there video games which are known to use this heuristic?