If I may be so bold, I don't think algorithmic path-finding is your best solution to implement more realistic NPC 'ambient' behaviors. Certainly, path-finding becomes important when NPCs are interacting with a player however, less granular solutions would prove more useful and probably be more beneficial on a strategic level. For instance, a player doesn't care about the exact path an NPC took to get from his home in village a) to the market in village b) UNLESS he plans on interacting with said NPC somewhere along the way. Say, to rob him somewhere between a) and b). So, for the purposes of a developer, we would only be interested in knowing the probability that a player will have of interacting with a specific NPC at a specific TIME in a specific PLACE. This can be abstracted into algorithms meant to simulate the NPCs behavior. The cool thing is that if you properly utilize an PRNG in conjunction with good simulation algorithms you can use ONE seed to store all the behaviors of ONE NPC for his entire lifespan. In this way you can skip the path-finding altogether UNTIL the probability that the NPCs and the Players will interact becomes very high.

So essentially, what I am saying is that 90% of the time you only need to know that NPC a) is doing Task b) near location c) at time d). And, so knowing every little step the NPC takes for 90% of his time is WASTED effort.

Hope this helps.