Very good write up, as always, from Red Blob. It turned my high-level assumption on Google Maps pathfinding upside down. I thought, recalling algorithms class, that Google Maps worked so fast due to "optimal substructure" of shortest-path finding. That is that the shortest path from A-C through B also produces the shortest paths from A-B and B-C, and that for most of any given path you could route through some number of precalculated "midpoint" paths. Reading this turns it upside down in the sense that landmarks go behind the target, and not in the middle of the route! Very handy tool.

Discussed here five days ago: https://news.ycombinator.com/item?id=49079995

(Honestly though this is such a cool piece of work it deserves a second conversation, that one only hit 40 comments.)

Good article and demonstrations. 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 am not colorblind.

Many of your maps consist of rooms connected at a few points. Have you considered running pathfinding first through the graph of rooms and then through each room individually? You could even precompute all paths through a room from one portal to another, but you probably don't need to, but you would need to precompute how costly they are. This is probably about the same pathfinding cost as putting a landmark in each room.