I've never done any work with pathfinding, and I found this interesting, Is this really the basic background of a pathfinder? I expected something a bit cleaner or without so much unneeded work being done, I can understand basically whats going on here, and I never attempted to think of a way of doing it myself, it just seems like a lot more than I would have thought.
This is a pretty standard flat implementation of A*. They may be optimisations in certain situations that can be made, but they usually require either the graph being optimised for them or certain assumptions be made. For example, you could treat the overall room structure as a graph and use A* to find your way from room to room, and then use A* again to find your way through each room.
A* is rather efficient as far as path finding goes. It's based on Dijkstra's Algorithm, which checks every node in the graph but is guaranteed to return the shortest path. A* on the other hand, is guaranteed to return a path. It won't always return the shortest path, but the path it returns is reasonably decent and it's faster than Dijkstra's as it doesn't check every node.
You might be able to optimise DF by making it detect 'rooms' as they are made, and then use them for path-finding.
As for threading, DF may be better optimised in terms of concurrency by spreading the search across all the cores. That's usually the easier, less optimal, way of shoe-horning concurrency into a project not designed for it.