Well, tinkering with pure mathematical heuristics of A* it should be possible to make it find always the best path, ie. the shortest route. But here I was aiming at optimizing speed.

Theoretically speaking all this is so very interesting. For example, instead of mere random noise there are other ways of emulating "a hunch" when choosing which tile to explore next. UrW random world generator assigns an internal height value for each tile on the big world map. And then every tile with height value of say 60 or less is converted to a water tile. Now, using that information it should be possible to make the A* to avoid going too much downhill. If the origin is at height level 120 and destination is at level 160, then the algorithm would prefer tiles in between those values, unwilling to go much higher or lower. That kind of simple heuristic should make paths curving around lake areas - often finding a longer path but being faster. Maybe I can test that one day =)

Well, but for actual use in UrW, I'd guess it is safe to assume that all the NPC's travelling the world map are already somewhat familiar with the surroundings. (But of course for the sake of realism we also need another algorithm for situations where an explorer is exploring unknown terrain). We have been thinking about post-processing the path so that it will be stored as a handful of waypoints. But I'd guess we will also use some degree of pre-processing to speed up the pathfinding. I'll write more about this when I get back to working with this =)

PS. More of "work-in-progress" thoughts; http://www.enormouselk.com/?q=erkkasblog/images/28th-march-2015