有效的路径查找算法避免锯齿形[重复]

I am developing a software which connects objects with wires. This wiring has a rule that these wires cannot pass on other objects and no diagonal move is accepted.

我知道的所有最短路径算法（A*、dijkstra 等）都会找到这种类型的路径：

我不希望第二个屏幕截图中出现不必要的锯齿形。我如何实现这个目标？

注意：任何想尝试算法的人都可以使用this http://qiao.github.io/PathFinding.js/visual/应用。

Another Note: This is the exact situation that i do not want. It finds the zigzag path instead of the one "go to the right until the you reach x position of the target, go to the up until you reach the y position of the target" which has the same cost with the zigzagged one.

您当前的算法找到一条最短路径，Pmin，但改进后的算法应该找到一条需要最少转弯数的最短路径(Pmin, Tmin)。一般解决方案要求您使用一对数字而不是单个数字。如果是新发现的Pnew小于当前Pmin或者如果它相等但是Tnew小于Tmin然后采取(Pnew, Tnew)作为新的最小路径。

如果棋盘足够小，您仍然可以使用当前使用的单个数字，但该数字必须是复合数字C = P * N + T, where N是足够大且足够小的常数。它必须大于该棋盘的最大可能 T，这几乎是棋盘中瓷砖的总数。它还必须足够小，以便当算法碰巧处理棋盘中的最大路径（也是棋盘中的图块总数）时不会出现整数溢出。所以N必须满足这两项（B 是棋盘中的棋子总数）：

N > B
B * N < INT_MAX

If B is larger than SQRT(INT_MAX) then this system is unsolvable, and you should go with pair of values. N should be SQRT(INT_MAX), which for 2³² is 2¹⁶.

现在的主要问题是如何计算所有转弯，但这取决于您所拥有的算法。添加该部分应该不会太困难。