Hacker News new | past | comments | ask | show | jobs | submit
inigyou | on: Differential Heuristics
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.

loading story #49301051
namibj | parent | next
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).

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