There is a path, generated by my implementation of A*, where diagonals aren't allowed, and the heuristics is the Manhattan distance.
Is there a way to always or nearly always find a path with the least amount of turns? Even if it's a bit longer, and even if it costs more computationally.
Or is there a way to algorithmically "fix" a path later? Like on the image below, cut those long detours and replace them with those blue parts.
My current version is far from optimal, both length-wise, and both turn-wise. I also tried multiplying the heuristic value of a tile, if:
- it isn't going in the same direction as the line made from the previous 2 tiles. But that didn't help either.