I'm not using A* or Djikstra.

I had my doubts you would understand what I am saying, so I created some pictures showing in stages what I do to generate the graph. The highest points are white, and the low points are black (just so we're clear).

Stage 1: The graph is empty. The cost of every cell is zero.


Stage 2: Cells farther from the destination are raised by either their horizontal or vertical distance, whichever is larger. Thus a diamond shaped "bowl" is formed, with the destination at the lowest point:


Stage 3: Terrain is added to the path. Walkable areas aren't added, only obstacles like mountains, pits, etc.


But obviously problems can arise in scenarios like this:

(The green dot is the start point, the red dot is the destination)

Naturally the green dot travels to the northwest as it is the path of least resistance, but the dot will inevitably get caught between the mountain and the terrain around it like a marble.

To fix this without ever having to make the mountains passable, I devised a solution wherein these "pockets" are smoothed out and/or filled in so that the green dot simply "rolls" around them, like this:


I'm pretty sure there are algorithms available that I can use to achieve this, but I'm not sure what they are. So what I was asking in my original post was, "What algorithm would you guys suggest for this?"


Excuse my objection/misunderstanding, but why would I want to do this? Isn't it less costly to travel diagonally then in a straight direction? After all, the length of the hypotenuse of a triangle is always less than the sum of the lengths of the other two sides.

EDIT: It doesn't matter if the smoothing algorithm is slow, I can precompute the smoothed "terrain-graph" and overlay it on top of the real pathfinding graph when the graph is being built.