We've looked into this somewhat as you could make basically make it a path finding problem.
The difficulty is creating the paths from A to B that feel worthy of being chosen e.g. taking a path that goes through quirky (potentially unmarked) alleyways, rather than going along the main road to the crossroad and turn left etc.
A lot of thought goes into choosing paths and locations that really set the scene, especially in the narrative based games!
Would to hear more thoughts on this though as it could be a nice pre-process to do and then refine