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.
Yes, it's a bit weird! There are also optimizations that do what you describe, with landmarks along the way, but at least at the time I learned about it, road map pathfinding was using landmarks behind the target.
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.
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.
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.
Yes, it's a bit weird! There are also optimizations that do what you describe, with landmarks along the way, but at least at the time I learned about it, road map pathfinding was using landmarks behind the target.
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.
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.