> 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.
bellowsgulch 3 hours ago [-]
I have an appreciation for people who keep going. Sometimes it doesn't really matter how long it takes you to learn something. I've found it's more valuable to see what you'd do with that knowledge.
dietr1ch 41 minutes ago [-]
Damn, 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).
Groxx 3 hours ago [-]
Red Blob Games has quite a few S-tier posts, highly recommend exploring further if this is at all interesting to you
LPisGood 3 hours ago [-]
Usually 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
Dr_Emann 3 hours ago [-]
It's a little unclear, but it's a live updating number, if you follow the directions, you'll see the second number decrease.
lokar 2 hours ago [-]
It 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.
bombcar 56 minutes ago [-]
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.
bellowsgulch 3 hours ago [-]
In the event this helps a random developer with some fun experimentation: I had once accidentally independently reinvented drunken pathfinding by adding random additional weights to the node costs, which has the side effect of making an object seeking a path end wander "drunkenly."
azhenley 3 hours ago [-]
I love this blog. 10/10
lucb1e 2 hours ago [-]
One might even say it's an A+ resource
dested 2 hours ago [-]
I see redblobgames, I click
Rendered at 03:37:56 GMT+0000 (Coordinated Universal Time) with Vercel.
Outstanding.
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).
> the number of nodes A* has to explore decreases from 12693 to 12693
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.