Heuristic Optimization

A tutorial on how to use heuristic optimization to gain significant speedups.

Normally when a pathfinding search is made, a heuristic is used. The heuristic is something which gives a rough estimate of how far it is at least to the target. Usually the real-world Euclidean distance to the target is used directly since this is fast and usually gives relatively good results. The problem is that in worlds which are not just open space with a few small obstacles scattered around, this estimate isn't very good. The result is that the search goes through a lot more nodes than it would have needed to if the heuristic had been better.

Results

This technique can drastically reduce the number of nodes that have to be searched through to find the target. This can, in turn, improve the performance significantly.

Consider the two images below. In the first image, this optimization is disabled while in the second one it is enabled. In the second image, the search is more informed and can avoid many directions that will not lead it to the target.

Heuristic optimization disabled

Heuristic optimization enabled

Background

If your world is static, or updates very rarely, there is a technique that can be used to precalculate distances between nodes and get heuristics which are a lot better. This can improve pathfinding performance by an order of magnitude (10x) in many cases.

The optimal heuristic is, of course, when we know the distance between every node to every other node in the graph; however, this is a bit impractical since it would take a very long time to calculate and would use a lot of space.

So what can be done is that we select a few nodes (henceforth called "pivot points") and calculate the distances from those nodes to every other node in the graph. This can then be used to calculate pretty good heuristics.

Regardless of what heuristic is used, the A* algorithm will always search through all nodes which could lie on the shortest path(s), so this technique will, for example, not give any performance increase on large open grid graphs because a path search rarely searches much more than the nodes on the shortest paths anyway.

The image below shows a completely empty grid graph and 3 different optimal paths. The algorithm will have to search through all the nodes in the green region because they are all equally good (i.e., they have the same length). All those nodes lie on an optimal path because in a grid there are many optimal paths.

The A* Pathfinding Project has algorithms for automatically selecting pretty good pivot points because it can be quite hard to select them in a good way manually. When I profile, I sometimes find that my manual placements of pivot points are worse than just randomly selected points.

Placing Pivot Points Manually

When placing these pivot points, the key thing about them is that they should be at dead ends in the world. They perform best when many paths can be extended to the pivot point and still be a shortest path.

In the image below, you can see pivot points in purple. The agent in the bottom left corner has requested a path to the green circle.

There can also be game-specific knowledge you can apply. For example, in a TD game, almost all units will move towards a single goal. So if you just place a single pivot point at the goal, all paths will be much faster to calculate because the optimal distance to that point from every other one is already known.

Placing Pivot Points Automatically

Two modes exist. Either all points are chosen randomly, or an algorithm is applied which selects nodes as far away from each other as possible. The second one gives much higher quality heuristics, but it is much slower to calculate as it requires that the initial distance calculation is done in serial and multithreading is therefore of no use.

In the image below, a comparison is shown between 5 randomly selected points and 5 points far away from each other. The ones which are far away from each other tend to be placed in dead ends or in the corners of the map, which will give very good results.

The number of pivot points that you should use varies. The best solution is just to try different values and see what is best for your game. When reaching over a hundred pivot points, the overhead from them is often greater than the gain from a reduced number of nodes to search. I would recommend between 1 and 100; try different values and see what works best.

You might notice that there is a delay at the start of the game until the pathfinding starts working. This is because it is busy preprocessing the heuristic lookups. If you find this delay so large that it becomes a problem, switch to using the "Random" mode instead of the "Random Spread Out" (if you were using that) or decrease the number of pivot points.