Thanks — yes, I'm still struggling to find a good way to explain the colors. The landmark is green. The blue tiles are the savings — the difference between using the landmark and not using it. I'll work on a different wording or maybe a visualization.

Changing the graph is another optimization that's commonly used. A graph of rooms is far smaller than a graph of tiles, and you can precompute paths on the small graph. The landmark heuristic can work on that graph too, although with the small examples on the page you probably wouldn't need to.

I'd like to point out that according to a tech blog or similar from years back, Google Maps public transit routing supposedly employs the zone-boundary hierarchy to do similar preprocessing, exploiting that at least in networks like e.g. Germany, there's a hierarchy level roughly corresponding to what is perceptually "same city" where the number of border crossings between the zones has a local minimum (splitting a zone and merging two adjacent zones would both increase the border crossing count of the resulting zone relative to the local minima one).

They then do all-pairs precomputing between the border nodes and connections within the zone; then use this to cheaply handle the long-distance travel, while only needing to do full non-precomputable pathing locally within the start and the end zone (and ofc jumping across the contractions on the way between the border of the start zone and the border of the destination zone).

> I was a bit confused about the colors - at least once the text talks about blue tiles being the ones that don't need to be checked because of the landmark, but they are actually green, and the blue ones are the ones that weren't checked anyway

I think the first demo in the introduction is supposed to have some blue but the default setup for some reason doesn't. If you move the landscape over to the other side you can see some blue appear.