找到彼此距离最远的两个点的算法

Question

我正在寻找一种用于我正在制作的赛车游戏的算法。 map /关卡/轨道是随机生成的，所以我需要找到两个位置，即起点和终点，它们充分利用了 map 。

• 算法在二维空间内运行
• 从每一点出发，只能从四个方向遍历到下一点；上、下、左、右
• 点只能是阻塞点或非阻塞点，只能遍历非阻塞点

关于距离的计算，应该不是“鸟径”，没有更好的词。如果 A 和 B 之间有墙(或其他阻挡区域)，则 A 和 B 之间的路径应该更长。

我不确定从哪里开始，非常欢迎评论，建议的解决方案最好是伪代码。

编辑:对。翻看后gs's code我又试了一次。这次我用 C++ 编写了它，而不是 python。但是，即使在阅读了Dijkstras algorithm之后, floodfill和 Hosam Alys solution ，我没有发现任何重要的区别。我的代码仍然有效，但不像您运行的那样快。完整来源在 pastie .唯一有趣的行(我猜)是第 78-118 行的 Dijkstra 变体本身。

但是速度并不是这里的主要问题。如果有人愿意指出算法中的差异，我将不胜感激。

• 在 Hosam Alys 算法中，唯一的区别是他从边界而不是每个节点开始扫描吗？
• 在 Dijkstras 中，您会跟踪并覆盖行走的距离，但在 floodfill 中不会，仅此而已？

Answer 1

假设 map 是矩形的，你可以遍历所有的边界点，并开始填充以找到距离起点最远的点:

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

我猜这会在 O(n^2) 中。如果我没记错的话，它是 (L+W) * 2 * (L*W) * 4，其中 L 是长度，W 是 map 的宽度，(L+W) * 2 表示越过周长的边界点数，(L*W) 是点数， 4 是假设 flood-fill 最多访问一个点 4 次(从所有方向)。由于n相当于点数，所以这个相当于(L + W) * 8 * n，应该比O(n²)。 (如果 map 是正方形，则顺序为 O(16n^1.5)。)

更新:根据评论，由于 map 更像是一个迷宫(而不是像我最初想的那样只有简单的障碍)，您可以按照上面的逻辑进行检查，但要检查所有点在 map 中(与仅边界上的点相反)。这应该是O(4n²)的顺序，还是比F-W和Dijkstra的都好。

注意: Flood filling更适合这个问题，因为所有顶点只通过 4 个边界直接连接。 map 的广度优先遍历可以相对快速地产生结果(仅需 O(n))。我假设每个点都可以在其 4 个邻居中的每一个的洪水填充中进行检查，因此上面公式中的系数。

更新 2:我很感谢我收到的有关此算法的所有积极反馈。特别感谢@Georg his review .

附言欢迎任何意见或更正。