Everyone who have written an implementation of A* path-finding algorithm knows that it generates good enough but often weird/unrealistic paths:
The resulting path should be smoothed before actual use. The first algorithm that comes to mind is: starting from the first point in the path, remove all the next intermediate points that have a line of sight except the last one; make it a check-point; repeat until the finish is reached.
The rule I use to determine if there is a line of sight between two points is: there should be no obstacles like trees of water tiles in between, and there should be no change of terrain type (I don’t want my characters to walk on sand or other “slow” tiles more than is needed.) The algorithm works well most of the time, but fails in some special cases:
These two tiles marked with black squares restrict the “visibility” too much and completely break the smoothing.
I’m looking for an algorithm for path smoothing that won’t produce such artifacts. The only one I can think of right now is a brute-force method.