<- Back
Comments (15)
- simonw> 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.
- GroxxRed Blob Games has quite a few S-tier posts, highly recommend exploring further if this is at all interesting to you
- dietr1chDamn, 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 otherYou 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).
- LPisGoodUsually 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
- destedI see redblobgames, I click
- lokarIt 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.
- taneqFrom the title I was expecting something about jump point search but this is even more interesting. Bravo!
- bellowsgulchIn 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."
- azhenleyI love this blog. 10/10