Unfortunately without preset nodes, natural movement becomes incredibly taxing. For paths, I put preset nodes into the paths. These nodes contain information about which direction goes where.
So, a NPC was off path (chasing a rabbit) and needs to get back on. You work possible route(s) to the node, go back through path, always choosing lowest cost and then travel that cost effective path (this should eliminate that weird part where his NPC walked backwards randomly).
As soon as you start requiring things like 'must be 2 tiles from nearest walls' and such it just becomes far too taxing on the server.
Once I was going to set up communication so i could offload these calculations to a dev server
