boy, i'm drunk. i hope i did get all the answers.
my path caching idea ...
1) ... has nothing to do with the ant approach of the thread starter. i probably should have started another thread, but ... whatever (i had the idea here as an anser/alternative (kind of "'ACO' is nice, but what about caching?")).
2) ... is nothing more than a simplyfied: if (a->b) was already computed, store it. if the same path needed again, reuse it. as soon as a dwarf runs into a block (because the map changed in between), recompute the graph or part of the graph. use some kind of age/rating based garbage collector
3) ... is pathfinding algorithm independed. i use a very simple flooding algorithm with no weighting, but the caching should work with weighted graphs too. my demo doesn't use z-levels, but there's almost not difference.
4) ... the demo is not optimized. there is no cache-size limitation, there is no reverse path recycling (a->b == b->a), there is no reuse of graphs in the neighborhood (a+-1 -> b+-1, should work for most a->b, because theres almost certainly no block between adjacent tiles), i don't do line-of-sight optimisations, ...
5) you could tweak the caching algorith a bit. e.g. instantly recompute the source path if the first dwarf runs into a block. then there would no dwarves running into walls (after the first one did). altough shortcuts would still be ignored until purging the aged paths.
6) there's no direct support for temporary blocks (other creatures that move, doors, drawbridges which change their state regulary). indirectly it does support it by rating the path (a path is purged only after a certain amount of dwarves running into blocks). optimizing pathfinding by communication between temporary blocks (moving creatures) is deadlock-prone (d1: "i'll move if you move!", d2: "me too")
7) path-finding wouldn't be "perfect" anymore (that is, dwarves wouldn't find the best path all the time). they'd make mistakes, as shown in my debug-output.
meh. waaaaay too drunk to think about all that. i love you all, man!
ps: (other replies been postet while i've been typing)
@draco18: the advantage of caching is: if there's memory for caching available, use it - if not, switch back to traditional atomic real time pathfinding. pre-computing every possinble path is too memory-intensive for DF.
@granite: don't pre-cache everything. cache the recently needed paths. there's a little look-up overhead, but nothing compared to recomputing the whole path all the time. if the cache is full, purge the least used.
pps: hangover now. never again dwarven ale!