One of the big questions for an algorithm is - when do you recalculate the path? A real "human" doesn't recalculate until they receive information that the chosen bath is blocked/changed (they see the road closed sign, etc).
But many games recalculate distance to target (one ping only) over and over again each step, so moving a single block half a map away causes an entire army to repath immediately.
Real humans also don't have perfect knowledge of the map and have additional concerns besides the path length so A* should only be part of the whole solution if you want realistic movement.
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.
Experimental multithreading was added in 2023 https://www.bay12forums.com/smf/index.php?topic=181776
I'm not sure if it's improved since then. Performance doesn't seem to be a priority for Tarn. It's kind of unfortunate, since I think DF would be an interesting problem space for optimizations, similar to Factorio, and it really needs it.
Comments
It uses df as an example, but it (unlike the others) has the problem that the set of valid paths between any two points can be constantly changing.
One of the big questions for an algorithm is - when do you recalculate the path? A real "human" doesn't recalculate until they receive information that the chosen bath is blocked/changed (they see the road closed sign, etc).
But many games recalculate distance to target (one ping only) over and over again each step, so moving a single block half a map away causes an entire army to repath immediately.
Real humans also don't have perfect knowledge of the map and have additional concerns besides the path length so A* should only be part of the whole solution if you want realistic movement.
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.
One of the famous problems with df is that it's very much single threaded. At least the last time I checked, which is some years ago by now.
Besides that blocker, your idea sounds like a nice win.
Experimental multithreading was added in 2023 https://www.bay12forums.com/smf/index.php?topic=181776 I'm not sure if it's improved since then. Performance doesn't seem to be a priority for Tarn. It's kind of unfortunate, since I think DF would be an interesting problem space for optimizations, similar to Factorio, and it really needs it.