避免锯齿形的有效路径查找算法 [英] Efficient Path finding algorithm avoiding zigzag's

问题描述

我正在开发一种将物体与电线连接起来的软件。此接线的规则是这些电线不能通过其他物体，并且不接受对角线移动。

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等）会找到这种类型的路径：

All of the shortest path algorithms that i know (A*, dijkstra etc.) find this type of paths:

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

I do not want the unnecessary zigzags in the second screenshot. How do i achive this goal?

注意：任何想尝试算法的人都可以使用此应用程序。

Note: Anyone who want to try the algorithms can use this application.

另一个注意：这是我所不希望的确切情况。它找到锯齿形路径，而不是向右移动，直到到达目标的x位置，向上直到到达目标的y位置，这与锯齿形路径的成本相同。

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）作为新的最小路径。

Your current algorithm finds a shortest path, Pmin, but the improved algorithm should find a shortest path that takes minimum number of turns (Pmin, Tmin). General solution requires that you work with pair of numbers instead of a single number. If newly found Pnew is smaller than current Pmin OR if it is equal but Tnew is smaller than Tmin then take (Pnew, Tnew) as new minimal path.

如果电路板足够小，您仍可以使用当前使用的单个数字，但是该数字必须是复合数字 C = P * N + T ，其中 N 足够大而足够小的常数。它必须大于该板可能的最大T，该T几乎是板上的瓦片总数。它也必须足够小，以使算法碰巧处理电路板中的最大路径（即电路板上的瓦片总数）时不会出现整数溢出。因此， N 必须满足这两个条件（B是板上的瓷砖总数）：

If the board is small enough you could still use a single number as you currently use, but this number must be a compound number C = P * N + T, where N is sufficiently large and sufficiently small constant number. It must be larger than largest possible T for that board, which is almost the total number of tiles in the board. It must be also small enough so that there is no integer overflow when algorithm happens to handle the largest path in the board, which is also the total number of tiles in the board. So N must satisfy these two terms (B is total number of tiles in the board):

N > B
B * N < INT_MAX

如果 B 大于 SQRT（INT_MAX），则该系统无法解决，您应该使用一对值。 N 应该是 SQRT（INT_MAX），对于2 ³² 来说是2 ¹⁶ 。

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¹⁶.

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

Main problem now is how to count all the turns, but that depends on the algorithm that you have. It shouldn't be too difficult to add that part.

这篇关于避免锯齿形的有效路径查找算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！