Birbla

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • i've always been impressed by NBA*: https://github.com/anvaka/ngraph.path

    demo: https://anvaka.github.io/ngraph.path.demo/

    by leeoniya
  • Long time ago I remember reading about D* lite, I wonder how do they compare.
    by HappyPanacea
  • I don't understand how the multiple landmarks works. If you just max all of the landmark distances wouldn't some landmark near the starting point eventually dominate as you move away from it? Once you get halfway through the path the useful landmarks would be returning lower and lower values while ones behind you return larger and larger values. Or just in general one far-away landmark would complete nullify any input from useful ones.

    It seems to me that you would need a step to select useful landmarks but the code doesn't seem to do this and I don't see it discussed.

    by kevincox
  • Ah, I figured it out. It is because he isn't using the distance to the landmark as the heuristic but the difference between the distance to the current location and the distance to the target. This means landmarks behind you will be negative (or useful in an undirected graph). This is also important for making the heuristic admissible as otherwise your heuristic would say zero when you are standing on top of the landmark.
    by kevincox
  • From the title I was expecting something about jump point search but this is even more interesting. Bravo!
    by taneq
  • 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

    by LPisGood
  • 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.
    by amitp
  • It's a little unclear, but it's a live updating number, if you follow the directions, you'll see the second number decrease.
    by Dr_Emann
  • I see redblobgames, I click
    by dested
  • Finally an interesting article about AI!
    by layer8
  • 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).

    by dietr1ch
  • There has been a lot of progress in this field in the research community. Two good papers:

    * https://ojs.aaai.org/index.php/AAAI/article/view/11027 * https://arxiv.org/abs/2212.03978

    by mpmisko
  • Errrrr... how is the first paper related to A* and path finding?

    It's about "planning" (ie. searching an action space) which does not generally have a heuristic, so it needs to do "exploration" (which is exactly the opposite of what you want for optimal path finding) to counteract getting stuck in local optima due to greedy search...

    by jaen
  • 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."
    by bellowsgulch
  • Incredible 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!

    [1] https://www.redblobgames.com/grids/hexagons

    [2] https://boardgamegeek.com/boardgame/31999/tzaar

    by tkocmathla
  • I remember reading it in 2006 or so to better understand pathfinding algorithms for my data structures and algorithms class.
    by leftnode
  • Red Blob Games has quite a few S-tier posts, highly recommend exploring further if this is at all interesting to you
    by Groxx
  • > 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.

    by simonw
  • *Insidestudying
    by moffkalast
  • Teach Yourself A* in Ten Years
    by chii
  • 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.
    by bellowsgulch