Improving Heuristics (2015)

# Red Blob Games: Improving Heuristics Source: [https://www.redblobgames.com/pathfinding/heuristics/differential.html](https://www.redblobgames.com/pathfinding/heuristics/differential.html) 19 May 2015## Table of Contents - [1\. A\*’s use of the heuristic](https://www.redblobgames.com/pathfinding/heuristics/differential.html#a-s-use-of-the-heuristic) - [2\. Perfect heuristic](https://www.redblobgames.com/pathfinding/heuristics/differential.html#perfect-heuristic) - [3\. Reusing a perfect heuristic](https://www.redblobgames.com/pathfinding/heuristics/differential.html#reusing-a-perfect-heuristic) - [4\. Multiple landmarks](https://www.redblobgames.com/pathfinding/heuristics/differential.html#multiple-landmarks) - [5\. Placement of landmarks](https://www.redblobgames.com/pathfinding/heuristics/differential.html#placement) - [6\. Automated placement](https://www.redblobgames.com/pathfinding/heuristics/differential.html#automated-placement) - [7\. Implementation](https://www.redblobgames.com/pathfinding/heuristics/differential.html#implementation) - [8\. Demos](https://www.redblobgames.com/pathfinding/heuristics/differential.html#demos)- [8\.1\. Dragon Age, The Circle Tower](https://www.redblobgames.com/pathfinding/heuristics/differential.html#dragon-age-the-circle-tower) - [8\.2\. Cogmind, Factory 5](https://www.redblobgames.com/pathfinding/heuristics/differential.html#cogmind-factory-5) - [8\.3\. Maze](https://www.redblobgames.com/pathfinding/heuristics/differential.html#maze) - [8\.4\. Dragon Age, Lothering](https://www.redblobgames.com/pathfinding/heuristics/differential.html#dragon-age-lothering) - [8\.5\. Cogmind, Research 2](https://www.redblobgames.com/pathfinding/heuristics/differential.html#cogmind-research-2) - [8\.6\. Cogmind, Factory 4](https://www.redblobgames.com/pathfinding/heuristics/differential.html#cogmind-factory-4) - [9\. More reading](https://www.redblobgames.com/pathfinding/heuristics/differential.html#more-reading) For optimizing A\* we usually look at the priority queue or the map representation\. Often overlooked is**improving the heuristic function**\. Here’s an example from the town of*Denerim*in Dragon Age Origins\.**Try moving the startBand goalto see A\***in action: Now**try moving the greenL**to be near the purple\. As the heuristic valuegets closer to the*true*distance, 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 the[end of the page](https://www.redblobgames.com/pathfinding/heuristics/differential.html#demos)I show this technique with maps from real games\. ## 1[A\*’s use of the heuristic](https://www.redblobgames.com/pathfinding/heuristics/differential.html#a-s-use-of-the-heuristic)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#a-s-use-of-the-heuristic) A\* uses a*heuristic*to 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 the*wrong*direction\. 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\. But*why*is it in the wrong direction? It’s because the usual distance\-based heuristic doesn’t know about the walls\. ## 2[Perfect heuristic](https://www.redblobgames.com/pathfinding/heuristics/differential.html#perfect-heuristic)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#perfect-heuristic) 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 use[flow field pathfinding](https://www.redblobgames.com/pathfinding/tower-defense/)\. 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 heuristic*once*and then*reuse*it for multiple A\* runs with different goals\. ## 3[Reusing a perfect heuristic](https://www.redblobgames.com/pathfinding/heuristics/differential.html#reusing-a-perfect-heuristic)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#reusing-a-perfect-heuristic) Let’s calculate a perfect heuristic to the green landmarkL\. Can we reuse it for another goal?**Yes**, sometimes\!**Move the start pointBand the landmarkLaround**to see which purple goals are helped: The idea is that if we already have the path fromB→L, we*also*get the shortest path to anyalong the way: BLcost\(B, X\)cost\(X, L\)cost\(B, L\) = cost\(B, X\) \+ cost\(X, L\)And we*almost*have the path if the goalis*near*the pathB→L: cost\(B, X\)cost\(X, L\)cost\(B, L\) < cost\(B, X\) \+ cost\(X, L\)We can’t exactly calculate`cost\(B, X\)`in this situation\. But the[triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality)\[1\]says that the sum of two sides of a triangle is at least as long as the third side\. Adapted for directed graphs, we can say`cost\(B, X\) \+ cost\(X, L\) ≥ cost\(B, L\)`\. For a heuristic we want a lower bound on`cost\(B, X\)`so we rewrite this inequality as`cost\(B, X\) ≥ cost\(B, L\) \- cost\(X, L\)`\. **That’s the key idea here**\. It’s impractical to precalculate all costs to all locations, but if we’ve precalculated the costs to a specific locationL, we can use that to estimate the cost to a different location\. ## 4[Multiple landmarks](https://www.redblobgames.com/pathfinding/heuristics/differential.html#multiple-landmarks)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#multiple-landmarks) How often is this triangle inequality useful? cost\(B, X\)cost\(X, L\)cost\(B, L\)It depends on where landmarkLis in relation to start pointBand goal\. We needLto be “behind”when coming fromB\.**Move the startBand goalaround**to see where a landmark would help: Try moving the landmarkLoutside the green shaded region, and see that the heuristic and path don’t always match\. Since a landmark needs to be “behind” the goal, a landmark won’t be useful for all goals\. We need*multiple*landmarks L₁, L₂, L₃, etc\. Each one gives us some lower bound for the heuristic: ``` cost(B, X) ≥ cost(B, L₁) - cost(X, L₁) cost(B, X) ≥ cost(B, L₂) - cost(X, L₂) cost(B, X) ≥ cost(B, L₃) - cost(X, L₃) … cost(B, X) ≥ cost(B, Lₙ) - cost(X, Lₙ) ``` We can take the*max\(\)*of these to pick the highest bound\. In this diagram, try**moving the goalto one of the purple shaded areas**to see how those areas are improved by the landmarks\. Then try moving it to one of the unshaded areas to see how A\* isn’t any faster there\. Also try moving the start pointBto see how the shaded area also depends on where the start is\. ## 5[Placement of landmarks](https://www.redblobgames.com/pathfinding/heuristics/differential.html#placement)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#placement) The best landmark position depends on the start pointB*and*goal\. We want the landmark to be “behind” goal, but what’s “behind” depends on both where the start pointBis and where the goalare\. We want to use landmarks to improve as many \(start, goal\) pairs as possible\. Let’s start with a single landmark\. Try moving the start point, goal, and landmark around in this map: It looks like the landmark can cover the main corridors but not the side rooms\. We need many more landmarks: Picking the number and placement of landmarks is*project specific*\. Consider: - Are all paths equally likely? For example in a colony builder game like Dwarf Fortress, we may care a lot more about paths to/from the main base, and not paths between a forest and a mine\. - All all paths equally valuable to optimize? For example if pathfinding is limiting the frame rate, we might want to focus on long paths that are slower to compute and not on short paths\. - Is the map static or does it change over time? If static, we might want to spend a lot of time in the map designer tool to precalculate optimal landmarks\. But if dynamic, we might want to use the last few goal locations to decide new landmark positions\. The new landmarks can be computed in a background thread\.- If the change reduces an edge cost, the heuristic will overestimate sometimes, and A\* will return a non\-shortest path until we update the cost table\. Pathfinding is optimized but nonoptimal\. Example: the player broke a wall but the unit won’t look for the shorter path right away\. - If the change increases an edge cost, the heuristic will be lower than desired, and A\* will take a little longer to run until we update the cost table\. Pathfinding is optimal but not optimized\. Example: the player added a wall so the unit might think that area’s safe to walk through but will have to find a path around it\. - If many units find paths to common areas \(such as the Dwarf Fortress dining room\), consider dropping the least used landmark and adding one near the common area\. - Are the maps open world or constrained? A real time strategy game may have different needs than a room\+corridor dungeon crawler\. - Thomas Nobes[has a video explanation](https://www.youtube.com/watch?v=lQI9-GiWjJQ)\[2\]including more tips on where to place the landmark points\. Fortunately, even if a landmark isn’t optimal, it might still help somewhat, and it’s still no worse than if we use the regular A\* heuristic\. ## 6[Automated placement](https://www.redblobgames.com/pathfinding/heuristics/differential.html#automated-placement)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#automated-placement) One algorithm to place landmarks is to randomly generate paths and keep track of which locations are good for many different paths\. It usually but not always picks a spot in the upper left\. It matches our intuition that landmarks should go on the outer edges of the map\. The second landmark should be away from the first landmark\. The third landmark should be away from the first and second landmark\. Each subsequent landmark should be evaluated based on what it adds\. This is what it looks like with two existing landmarks: It picks a third away from the first two, but not always in the same place\. ## 7[Implementation](https://www.redblobgames.com/pathfinding/heuristics/differential.html#implementation)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#implementation) As the name “differential heuristics” suggests, this is a change to the*heuristic*given to A\*\. We don’t need to change A\* itself\. We need to**pick landmarks**\. If the maps are known ahead of time, landmarks can be placed in a map designer tool\. If the maps are procedurally generated, try the randomized map analysis earlier on this page\. Some of the papers linked at the end have more sophisticated placement algorithms\. Then we need to**analyze the map**\. Allocate a 2D array of numbers,cost\[nodeId\]\[landmarkId\]\. For each landmark, we run[Dijkstra’s Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\. It’s a “single source shortest path” algorithm but we want a single goal instead of a single source\. In a directed graph, we need to reverse all the edges\. In an undirected graph, we can use the edges as is\. We setcost\[nodeId\]\[landmarkId\]to the cost of the shortest path from nodenodeIdto nodelandmarkId\. If the weights are all 1, we can use Breadth First Search instead of Dijkstra’s Algorithm\. This is essentially what I’m running for the demos on this page \(undirected graphs\): ``` const L = [ /* array of landmark locations */ ]; let L_cost = [ /* array[nodeId] of arrays[landmarkId] */ ]; for (let landmarkId = 0; landmarkId < L.length; landmarkId++) { let output = dijkstraSearch(L[landmarkId]); for (let nodeId = 0; nodeId < graph.num_nodes; nodeId++) { L_cost[nodeId][landmarkId] = output.cost_so_far[nodeId]; } } ``` Note that*it’s not much code*\. It’s running our existing algorithm \(Dijkstra’s, A\*, or BFS\) and storing the results in an array\. It could run in a background thread\. Then we need to**modify the heuristic function**\. Previously the heuristic wasdistance\(B, X\)\. For example: ``` function heuristicManhattanDistance(a, z) { return Math.abs(a.x - z.x) + Math.abs(a.y - z.y); } ``` Each landmark Ligives us a lower bound`cost\(Lᵢ, X\) \- cost\(Lᵢ, B\)`\. We want to take the*highest*of these: ``` function heuristicLandmark(B, X) { let h = heuristicManhattanDistance(B, X); // or any other distance heuristic for (let landmarkId = 0; landmarkId < L.length; landmarkId++) { let lowerBound = L_cost[B][landmarkId] - L_cost[X][landmarkId]; // if the graph is undirected, use lowerBound = Math.abs(lowerBound) if (lowerBound > h) { h = lowerBound; } } return h; } ``` Note that*it’s not much code*\. It’s running the existing heuristic \(typically Manhattan, Chebyshev, or Euclidean distance\) and sometimes increasing it if the landmarks form a good triangle\. What changes with the A\* code?**Nothing**\. There are lots of techniques for making A\* run faster\. I like this one because it’s very little code\. ## 8[Demos](https://www.redblobgames.com/pathfinding/heuristics/differential.html#demos)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#demos) I tried the differential heuristic on some maps from Dragon Age \([provided by movingai\.com](https://www.movingai.com/benchmarks/grids.html)\[3\]\), a maze \(also provided by movingai\.com\), and[Cogmind](https://www.gridsagegames.com/cogmind/)\[4\]\(maps provided by Josh Ge\)\. All of these maps have bidirectional edges so I’ve used that version of the differential heuristic\. - Blue areas are what**we no longer have to search**by using the differential heuristic\. Orange areas are what we search even with the improved heuristic\. - Try moving the startBand goalto see the performance on different paths\. ### 8\.1Dragon Age, The Circle Tower The landmark is badly placed for the initialB→path\. Try moving it\. ### 8\.2Cogmind, Factory 5 In the next demo the landmarksLare in places that don’t help\. Move them around to improve search\. The blue area are the nodes we no longer have to search\. More blue is better\. The landmarkLpoints help more when closer to the start pointBthan the goal\. They help more when they’re “past” the goal point\. Move the startBand goalaround and see that there’s a big improvement no matter which path you want to find: However, it took a lot of landmarks to get that improvement\. We can do better by using the random path map analysis to pick fewer landmarks but in smarter locations: ### 8\.3Maze A\* with a distance heuristic behaves particularly badly with mazes, but in this one, just four landmarks make a big difference\! Then**Try dragging the startBand goalto see how much the landmarks help**\. The blue areas are the areas we*didn’t have to search*by using the landmarks\. Also toggle the bidirectional flag to see how much of a difference that makes\. ### 8\.4Dragon Age, Lothering This map has large open areas, and it seems to work well with the landmarks\. ### 8\.5Cogmind, Research 2 This is a room\-and\-corridor map from ### 8\.6Cogmind, Factory 4 ## 9[More reading](https://www.redblobgames.com/pathfinding/heuristics/differential.html#more-reading)[\#](https://www.redblobgames.com/pathfinding/heuristics/differential.html#more-reading) This page is about using Cartesian coordinates in a game map to construct a graph\-based heuristic based on “landmark” nodes \(sometimes called “pivots” or “beacons”\)\.**I’ve collected some references but haven’t read all of them**so I may have some of this wrong\. - 2004[Computing the Shortest Path: A\* Search Meets Graph Theory](https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/%20)\[5\]\(Goldberg, Harrison\) \[[mirrors](https://scholar.google.com/scholar?cluster=1603393061586443589&hl=en&as_sdt=0,48)\[6\]\]\. I learned about the technique in this paper\. It’s a combination of*bidirectional*A\* search and the landmark\-based heuristic, used for road networks\. - 1994*Routing information organization to support scalable interdomain routing with heterogeneous path requirements*\(Hotz\)\. \[[citations](https://scholar.google.com/scholar?cites=8767730387060832841&as_sdt=5,48&sciodt=0,48&hl=en)\[7\]\] I can’t find a copy of this online, but it appears to be work that introduced using the triangle inequality with landmarks, for Internet routing\. - 2005*Approximate Distance Oracles*\(Thorup, Zwick\) \[[mirrors](https://scholar.google.com/scholar?cluster=10826648391015165886&hl=en&as_sdt=0,48)\[8\]\]\. This theory paper covers the more general topic of calculating the approximate distance between any pair of nodes in a graph, using a “[distance oracle](https://en.wikipedia.org/wiki/Distance_oracle)\[9\]”\. An approximate distance is what we need as the heuristic in A\*\. It’s also possible to go in reverse\. Many graphs do not have natural Cartesian coordinates, and even the ones that do may not have good results from a distance\-based heuristic\. - 2002[Predicting Internet Network Distance with Coordinates\-Based Approaches](https://www.cs.rice.edu/~eugeneng/papers/INFOCOM02.pdf)\[10\]\(Ng, Zhang\) \[[mirrors](https://scholar.google.com/scholar?cluster=16253098808227849232&hl=en&as_sdt=0,48)\[11\]\] This paper uses the landmark\-based heuristics to assign Cartesian coordinates for nodes in an Internet routing network\. Then it uses Euclidean distance for the heuristic\. This is the inverse of what we’re doing on this page, where we already have Cartesian coordinates, but want to use the landmark\-based heuristic instead\. - 2011[Euclidean Heuristic Optimization](https://webdocs.cs.ualberta.ca/~bowling/papers/11aaai-heuristicopt.pdf)\[12\]\(Rayner, Bowling, Sturvetant\) transforms the Cartesian coordinates on a game map where distance heuristics don’t work well into new Cartesian coordinates where distance does work well\. Storing the landmark data requires one number per node\. In a typical game map, those numbers may be very similar from one grid space to the next\. Just as image compression takes advantage of nearby pixels having similar values, we might want to compress the landmark data because nearby graph nodes have similar values: - 2011[The Compressed Differential Heuristic](https://webdocs.cs.ualberta.ca/~nathanst/papers/tdh_comp.pdf)\[13\]\(Goldenberg, Sturvetant, Felner, Schaeffer\) \- by storing more landmarks in the same amount of space, the heuristic can be better\. In this paper, “landmarks” are called “pivots”, and the “landmark based heuristic” is called the “differential heuristic”\. The landmarks L used on this page are placed*beyond*the end of the path B→X, so the layout is B→X→L\. There are also algorithms that place landmarks*along*the path, B→L→L→L→X\. I am not covering that topic here, but if you’re interested, see: - 2008[Approximating Shortest Paths using Landmarks](https://www.semanticscholar.org/paper/LPI-%3A-Approximating-Shortest-Paths-using-Landmarks-Grant-Mould/f9185ed02848c1cd3e0ccdda16fa7a32f7428a8a?p2df)\[14\]\(Grant, Mould\)\. Calls them “landmarks”\. - 2014[Hub Labels: Theory and Practice](https://www.researchgate.net/profile/Ruslan-Savchenko/publication/300450292_Hub_Labels_Theory_and_Practice/links/5815cb8c08aeb720f6852f68/Hub-Labels-Theory-and-Practice.pdf)\[15\]\(Delling, Goldberg, Savchensko, Werneck\)\. Calls them “hubs”, and uses only a single intermediary on the path B→L→X\. - 2009[Abstraction\-Based Heuristics with True Distance Computations](https://webdocs.cs.ualberta.ca/~nathanst/papers/CPDBsara.pdf)\[16\]\(Felner, Barer, Sturvetant, Schaeffer\)\. I believe this paper tries to unify both “landmark” approaches\. B→X→L is called “differential heuristic” and B→L→L→L→X is called “canonical heuristic”, and both of these are under the umbrella “true distance heuristics”\.