I am using some sort of navigation structure, which splits the world into areas and maintains links to every connected area - this results in a smaller graph and works as abstraction layer for the world (and even allows for detecting rooms and dynamic doors) - this graph is used for early pathing checks mainly. For actual pathfinding a modified A* is used on block-level which runs in a separate thread.
Currently the graph does not find the shortest path as it does not provide any heursistics over its nodes. But the early checks help a lot
The way this is all connected to the main thread is basically some “messaging queue”. For example, when an entity get’s an order to build something, it first issues a search (message to thread) which then finds the closest item of the specified type which has a path to the target and then returns the actual path - the agent then walks this path and so on - so the other thread is basically a task/msg handler. And because all this happens in the other thread I can mostly eliminate syncronization issues and don’t need to “lock” everything.
there is a LOT of optimization in there