Earlier I was working with my own algorithm which plots the path by placing way-points. Yesterday I started working with A*-based algorithm, which traces the path tile by tile. It is not very intelligent yet, and I'm afraid that there is still a memory leak somewhere, as it tends to crash if I ask it to seek a full path from left side of the map to the right side...

I designed the test map to feature the challenges of URW map. Because of rivers and fords there might be dead-ends. And some obstacles are rather big with tricky, irregular shapes. But, yeah, A* is guaranteed to find a solution if there is one. And there is a lot of room for optimization. So, I still think that I'll end up with some combination, like using A* to find a way around an obstacle, and then with some heuristics convert the tile-by-tile path to a handful of waypoints... All this is so very interesting =)