I didn’t see a generic pathfinding slowness post for A20. Feel free to merge if you know of one.
There is a 2 part performance problem. First, an excessive amounts of scaffolding is made.
2nd, Your pathfinding chokes on number of vertical connections.

Game Save:
I would upload my gave save in 1 file, but even at max compression, it is barely too large.
Astar.zip (2.1 MB)
server_state.zip (7.8 MB)
Potential Solution:
Real scaffolding doesn’t have vertical pathing everywhere.
My suggestion would be to make sporadic vertical connections for scaffolding.
Poor ASCI Art Ex:
____________________________________________________________
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
| | | | | | |
| | | | | | |
Hearthings would just raise the flat, top-level scaffolding when building up. This would be fine because your dependency graph always builds bottoms up. Otherwise, fix the traversing of all vertical connections.
I have a high end machine, so astar is usually 1-3% usage. The perf issue goes away as soon as scaffolding goes down.