Comment by munificent

Yes, threading within your pathfinding code is hard. But in this case I'm suggesting running all of pathfinding on one thread separate from the main game thread.