Originally Posted by Digital_Utopia
The trouble is, if you're going to do any routing whatsoever - such as finding a path between an arbitrary point A, and a quest objective, you need to know what is, and what isn't passable terrain.
It gets even more complicated. Though a particular path may not be passable in one direction, it may be in the other, and it sometimes even depends on the character and player choice. As a burglar, I have a skill that will protect me from damage from falling, so I may very well jump off of even a very high cliff as a shortcut. Even without the skill, as a player I may choose to risk/sustain falling damage to my character in certain situations. Jumping over obstacles is another example, and that may even be affected by whether or not you're mounted...I'm not sure. Any pathfinding algorithm would have to ignore such possibilities. This is why enemies/NPCs never jump over obstacles or slide/fall down slopes - the game simplifies the pathfinding by avoiding such possibilities altogether.
Though these limitations would mean that such an algorithm would never be 100% optimal, at least it could offer you a path that would be guaranteed to get you to your destination reasonably efficiently. I'm not usually in THAT big of a hurry...and if I was chugging along and saw that the marked path was taking me around a cliff, I could always still choose to jump and have the path recalculated from the bottom.
Ideally, this would be based off of a procedurally-generated height map, with every in-game obstacle plotted. That's obviously not possible. What I had in mind was basically taking the world map and plotting off areas that the algorithm should avoid. One interesting possibility there would be to use a tool that logs the coordinates from the plugin itself to trace the borders of passable terrain. You could potentially even recruit others to help gather this data. It wouldn't have to be perfect - we can work around trees and other minor obstacles - just having the major terrain barriers outlined would be a huge advantage.