Hello again

The pathfinding solution presented by Damocles has been coming along very well. My units know how to navigate the graph in eight directions, so a unit can move north/south/west/east and diagonally. They can also find their way around simple obstacles like pits and mountains, since I am taking terrain into account when the graph is built.

But I have encountered a problem in my graph building method. The units can easily lead themselves into corners and pockets in the terrain from which they cannot leave unless the player manually directs them out. This happens because when the terrain is added to the graph, high-cost graph cells are placed next to low-cost graph cells, creating a "trap" which any unit can fall into.

So what I need to do is "smooth out" the graph, averaging high-cost cells with low-cost cells so that the units can "roll around" these traps without being manually directed to do so. But I don't know of any algorithms that can do this.

So what algorithms would you guys suggest to accomplish this?