> 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.

Red Blob Games has quite a few S-tier posts, highly recommend exploring further if this is at all interesting to you

This Red Blob Games blog post would be accessible to a wider group of readers if it spent just a few sentences up front on motivation and terminology.

If you don't already know exactly what the heuristic function is and that L is something called a landmark marker, and anyway what is a landmark marker anyway, you need to read quite a long way through the blog post to make sense of it.

And when you do finally get to that point, you realise it is all very simple, so why not just say that at the start?

One of my fav LLM tests is asking it to implement A* algorithm, in X language, in a single file, output 80x40 char map with random obstacles and show the path. Ask it to build UI or change path heuristiscs, etc.

It's such a quick prompt but can quickly signal how useful the model is in that language or framework, how much you have to constraint output with specs and tests.

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

i've always been impressed by NBA*: https://github.com/anvaka/ngraph.path

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

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).

Man I opened this website after so so long, so nostalgic.

I see redblobgames, I click

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