The landmark data can be calculated in a background thread. For DF I imagine you'd have a background thread running all the time, updating one landmark every so often. But what happens if you look for a path before the landmark data is updated? I haven't tested this yet but I believe this is how it'd work:

1. If the cost of a tile decreases, the precalculated heuristic will be too high, so A* might find a non-shortest but ok path. In game, you can think of the dorf as following the path they already know about, because they don't yet know that there's a shorter way.

2. If the cost of a tile increases, the precalculated heuristic will be too low, so A* will find the optimal path but it will take a little bit longer (still not as long as if we weren't using this heuristic). In game, you can think of the dorf as following the path they already know about, but running into a wall, so then they find a path around it.