For optimizing A* we usually look at the priority queue or the map representation. Often overlooked isimproving the heuristic function. Here’s an example from the town ofDenerimin Dragon Age Origins.Try moving the startBand goalto see A*in action:
Nowtry moving the greenLto be near the purple. As the heuristic valuegets closer to thetruedistance, the number of nodes A* has to explore decreases fromto. The blue area is the savings.
On this page I’ll show a way to improve the heuristic to speed up A*. At theend of the pageI show this technique with maps from real games.
A* uses aheuristicto guide it towards the goal. We can think of it like wind pushing us in the right direction. Here, the heuristic pushes us east, and the shortest path goes east:
But sometimes it pushes us in thewrongdirection. Here, the shortest path is to the west but the heuristic pushes us east:
A* runs faster when the heuristic guides us in the right direction. It wastes time when the heuristic guides us in the wrong direction. Butwhyis it in the wrong direction? It’s because the usual distance-based heuristic doesn’t know about the walls.
Ideally, we’d find a heuristic that knows about walls and never points in the wrong direction:
Can we calculate this “perfect” heuristic?Yes!
But the perfect heuristic is different for every goal and wall configuration. Move the goaland you’ll see the heuristic changes. Move the startBand you’ll see it doesn’t.
If the goal and walls stay the same, then we can useflow field pathfinding. But usually the goal isn’t the same, so we need to construct a brand new perfect heuristic for each goal. That is impractically slow to calculate every time we run A*, and it’s also impractically too large to store if we want to compute it ahead of time.
It’d be nice if we could calculate the heuristiconceand thenreuseit for multiple A* runs with different goals.
Let’s calculate a perfect heuristic to the greenL, which we call a “landmark”. Can we reuse it for another goal?Yes, sometimes!Move the start pointBand the landmarkLaroundto see which purple goals are helped: