Going to be a little silly here:
IIRC, each tile is 48x48, and each area has about 20 z levels. That's 150x150x40* int(s)** to determine a normal map. 25 megs of memory to store the entire (pathfinding) map at 32byte integers.***
At most, on any given turn, 600**** squares are going to change their state, so it's easier to track state CHANGES than the path.
We've already got an application that reads the layout of the map and converts it. (AKA we can get that 25 meg pathmap out.) If anyone wants to design something that converts the whole map into the object described and feed it into an API that takes the map, takes updates, and responds to path requests, we could change out the Pathfinding API and actually check the speed of some of these pathfinding suggestions on real maps.
Personally, I think that the A* is going to be the best non-learning algorithm we can get, although cacheing paths between common choke points (similar to Star Weaver's method) would be a cheap learning algorithm.
I was also thinking that the outside is usually very different from the inside, and pathing to the closest door might save a lot of costs for gobbos and woodcutters.
*Need to track Ceilings vs Open vs Stairs between z-levels.
** Need to track Open vs Closed vs Increased Costs (discouraged areas)
*** REALLY rough numbers, don't bother to correct me if that's all you're going to do. It doesn't matter.
**** Digs, builds, doors changing state, player value changes (forbids). I'm assuming that the player isn't flipping all the doors in the fort or laying down massive new discouraged areas on a regular basis. Ignoring player actions, 200 Up/Down Stairs would affect 600 tiles