Jumping in a little late here, but I've done A* on a scale simliar to DF, with some of the same kinds of issues that DF has.
The approach I'd initially take is the hierarchical one - using certain elements to serve as reference points and build out a cache only using these points. The reference points would be:
door
stair
bridge
hatch
floodgate with mechanism
trade depot
etc.
I'd concentrate on the elements that the player can control (let the players interested in running massive fortresses design them with the pathfinder in mind), which routinely serve as chokepoints and are variable in state. This might also include workshops and stockpiles. Toady could even add the ability for the player to designate a reference point using the zone tool, or some such.
I overall agree with Teiwaz here. I wouldn't get obsessed with keeping this cache perfectly calculated for one main reason - we don't do that in real life, and because we know that actual travel costs in DF rarely match theoretical costs once the per-tile cost of traffic is included. IRL, we know we want to get to some place over there. Let's say we decide to ride our bike to the store. We know where we are going and we predetermine the reference points we're going to move through - street intersections and so on, but we don't have a priori knowledge of the state of these reference points. We know they presumably exist and we might have some probabilistic knowledge of their reliability, but that's about it. When we embark on our trip, we then discover the state of each of these reference points and recalculate accordingly. Construction may have a street blocked and we then recalculate from that observation to the next reference point on our journey. A gate might be locked and we recalculate again. Each time, we store that information so we don't repeat the mistake the next time. By and large, we use something that resembles a hierarchical A* system, but with different reference points, weightings and so on for each person.
So it's okay to have imperfect pathing, so long as it's imperfect in reasonable ways. Further, it's okay to embark with an incomplete path, so long as you have reasonable reference points - and that's where I'd put all the focus. There are some gameplay benefits to doing it this way, in fact. Right now, a dwarf can set a path across the map, only to find 99% of the way there that something has changed and they need to recalculate the path - perhaps having to retrace a huge distance. You can interrupt them by drafting them, etc. but otherwise they'll happily wander into a siege that every other dwarf is rapidly fleeing from. If there were a series of reference points the dwarf were navigating among, you'd only calculate a full path from the current position to the next reference point (much less A* work) and upon reaching that reference point, you'd check the updated state of the reference points in case something changed (such as someone pulled the 'stay inside' alarm), find the new optimal path from the cached reference distances (very fast), and then take the cached path. This way, the dwarf would adjust their path periodically based on new information arriving in the cache. By assuming that dwarves communicate such things freely, the game gets more realistic. Normally in a hierarchical A*, you don't have much discovery of new information in mid-path but with 200 dwarves running around, it's not unreasonable to have that occur, so let's call it a feature.
Each time a dwarf encounters a path which is no longer valid (a wall was put in, for example) the cache is updated for the distance between those two reference points (and possibly for all paths that share one of those two references, since there may be more), and dwarves will update accordingly.
One further benefit to this is that, memory permitting, the game can maintain two (or more) different sets of caches - one for dwarves and one for enemies. Dwarves will know all the shortcuts, but enemies should not, so their cache should be incomplete. Early sieges and squads may bumble about the place, but each encounter will fill in the cache a little more and cause them to act more efficiently. Depending on how memory efficient it is (it can even be saved to disk since it's only periodically invoked) different caches can be in place for gobbos, orcs, etc. so each one can have their own knowledge of your site and provide the player with differing behaviors, all for a relatively low cost. Further, species with different abilities would have caches better suited to their abilities.
Memory permitting, one other bit of data can be accumulated to influence pathing. In addition to the theoretical travel cost, the real cost can be stored for each reference node pair. The theoretical cost to go from A to B might be 100, but if it's a heavily travelled route, the last real cost might be 1000 as dwarves constantly climb over each other. That cost could be factored into the algorithm and also discounted over time so that as time passes, the stored real cost naturally declines, encouraging dwarves to try the route again. Again, this is more similar to how people behave.
Personally, I'd encourage people to embrace a slightly sloppy and fast solution over an ideal one.
Author
Topic: Anouncing The PathFinder Project (Read 98112 times)