A few quick questions: How are we expecting calls from the program to the pathfinder to work? Given that some critters may be moving towards a moving target, I'm assuming that it's a series of "I am at location X and I need to get to location Y, what is the next step I should take?" and the return value will be a direction in some format (sub-question: is there a standard format for these vectors?). The primary goal is then to return from that call as quickly as possible, without returning an impossible move and without causing "waggle dance" or other atrtfacts.
Personally, I think the return call should be the
entire path from current location to intended destination, and possibly some more jiggery pokery (as noted belote). On an trip that takes 100 steps, a mythical beyond-theoretically-possible pathfinding alorithm that takes N cycles to work out the optimally short 'N'-step journey that must be taken, and tells the agent the next step, would need 100*101/2 cycles to get them to the destination. And, in reality, we know that it's probably somewhere between N Log N and something truly exponentional, for a single N-step, which
then gets added. So, best to calculate a single path, once, and follow it. At least until something tells you that a recalculation is needed.
Obviously, recalculation at each step of the way handles dynamic environments exceedingly well. And also simplifies things in an 'intuitive' system where
only the next step (or two) is queried, which would involved back-reference to rule out "been there, and it's blocked off" possibilities). To that end, the additional 'jiggery pokery' could involve waypoints where conditions should be queried, or even (at a memory-mapping level) implementing memory pointers that mean that when obstructions are created/removed they can create an 'event'/interupt to be picked up by all relevent pathing agents, to force them[1] or encourage them[2] to re-evaluate their path.
This latter would reduce re-pathing needs,
length of any particular repathing need[3] and act
almost as if the omniscient repathing were being reassessed after every single tick. Not quite, because unforseen new paths from multi-tile landscape destruction are among the trickiest things to consider (and probably not worth the trouble), although an event-initiated link to currently routing agents might also be considered when a new agent plans its own path and discovers not only the new and better routing possibility, but that it shares significant waypoints with those remaining in the currently travelling agents queue of intentions. The triggered events can then prompt the more senior router to reassess their position, with most of the required calculation already done.
Of course, this is the omniscient solution. Some people, I know, would rather it be reduced to discovery/trial-and-error. And I certainly think that could be factored in, but not in a pheremone-style way. An ant's nest has a whole mass of active agents, running their own instantaneous partial-path routing, not externally controlled by a solid purpose but creating an
apparent purpose from the combined 'waveforms' of purposelessness within the hive mind and hive body. I don't see enough of those aspects being sufficiently relevent to dwarfkind.
[1] Where a blocking affects the currently intended path, but allow them to remember this for point [2]...
[2] When a path segment opens that was previously blocked, or (if you want to get complicated) by some means remember "could have, if only" shorter viable paths prevented only by a temporary style of blockage. By adding a little extra effort/information storage, it might even streamline travel through zones such as repeater-led cyclic barriers across a path. And if you allow natives (and possibly, by experience, long-term transient entities like a multi-season beseiging force) this skill, but leave opportunistic thieves/fauna/etc to continue their current method of pathing, it could mean that the creation of a 'dynamic labyrinth' could be a viable means of 'defence by confusion'.
[3] Imagine wandering half way round the mountain to find that the area previously impassible from a straight-through route and needing the detour was now
only passable via the straight-through route. Something you might easily get if setting up a satelite 'watchtower' or outlying habitation/cafeteria specifically for certain resource-handlers. The overhead of recalculation (and 'dwarf energy' in this (extreme) example could have been avoided if, shortly after they set off on their way round, there had been a 'psychic summons' bringing them back again to the now-opened direct route (before or after the original indirect route was shut off[4]).
[4] Technically, a shut-off before the official short-cut actually opening should trigger relevent "cannot reach, abandoning job" events. But it's up to the player to work out how they want to synchronise the activities of blocking masons/channellers/etc with permitting miners/bridgers/etc.