I love this blog. 10/10
One might even say it's an A+ resource
Improving Heuristics for A* Pathfinding
11–20 of 42 posts
Re: Improving Heuristics for A* Pathfinding
#12It uses df as an example, but it (unlike the others) has the problem that the set of valid paths between any two points can be constantly changing.
One of the big questions for an algorithm is - when do you recalculate the path? A real "human" doesn't recalculate until they receive information that the chosen bath is blocked/changed (they see the road closed sign, etc).
But many games recalculate distance to target (one ping only) over and over again each step, so moving a single block half a map away causes an entire army to repath immediately.
Re: Improving Heuristics for A* Pathfinding
#13Damn, isn't A* fun and intuitive?
I'd be interesting to dive into bounds and good properties for sets of landmarks.
I imagine that if, - Every node is at least X cost/distance away from a landmark - Landmarks are no closer than Y cost/distance from each other
You can start promising a lot about the size of your open set on any execution.
A* on h* (perfect heuristic) takes O(l) where l is the length of the solution (could expand exactly l nodes, but solving/guessing ties incorrectly might bump this to a multiple around the avg edges per vertex). I imagine that having good bounds mean you'll take no longer than a certain amount of expansions/depth before you lock-into the railway that h* provides (and you need some extra work to get off it too).
Re: Improving Heuristics for A* Pathfinding
#14It uses df as an example, but it (unlike the others) has the problem that the set of valid paths between any two points can be constantly changing.
The landmark data can be calculated in a background thread. For DF I imagine you'd have a background thread running all the time, updating one landmark every so often. But what happens if you look for a path before the landmark data is updated? I haven't tested this yet but I believe this is how it'd work:
1. If the cost of a tile decreases, the precalculated heuristic will be too high, so A* might find a non-shortest but ok path. In game, you can think of the dorf as following the path they already know about, because they don't yet know that there's a shorter way.
2. If the cost of a tile increases, the precalculated heuristic will be too low, so A* will find the optimal path but it will take a little bit longer (still not as long as if we weren't using this heuristic). In game, you can think of the dorf as following the path they already know about, but running into a wall, so then they find a path around it.
Re: Improving Heuristics for A* Pathfinding
#15Usually I would not point out a typo, but this one makes it difficult to grasp the magnitude of potential improvements: > the number of nodes A* has to explore decreases from 12693 to 12693
Good catch. I was thinking people would read that after they have moved the green L but I should handle both before and after moving L.
Re: Improving Heuristics for A* Pathfinding
#16From the title I was expecting something about jump point search but this is even more interesting. Bravo!
Re: Improving Heuristics for A* Pathfinding
#17i've always been impressed by NBA*: https://github.com/anvaka/ngraph.path
Re: Improving Heuristics for A* Pathfinding
#18Incredible write-up, as usual. I still fondly remember discovering Red Blob Games' Hexagonal Grids [1] guide while building an implementation of the Tzaar board game [2]. The illustrations are enormously helpful!
Re: Improving Heuristics for A* Pathfinding
#19> I learned about this technique in 2007, then tried writing it up in 2015. I realized that I didn’t understand it enough to be able to explain it. I studied it off and on in 2016, 2018, 2019, 2022, 2024, and 2026. I abandoned and restarted this page many times. And by 2026 I think I understand it well enough to write this page. Outstanding.
Teach Yourself A* in Ten Years
Re: Improving Heuristics for A* Pathfinding
#20Man I opened this website after so so long, so nostalgic.