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

Question

我正在寻找一种算法用于我正在制作的赛车游戏.地图/关卡/轨道是随机生成的,所以我需要找到两个位置,即开始和目标,它们利用了大部分地图.

• 该算法是在二维空间内工作
• 从每个点,只能遍历四个方向的下一个点; 上下左右
• 点数既可以是阻止的也可以是非阻塞的,只能遍历非阻塞点

关于距离的计算,它不应该是缺乏更好词的"鸟道".如果它们之间存在墙(或其他阻挡区域),则A和B之间的路径应该更长.

我不确定从哪里开始,非常欢迎评论,并且建议的解决方案在伪代码中是首选.

编辑:对.在查看了gs的代码后,我又给了它一个镜头.我这次用C++写的,而不是python.但是,即使在阅读了Dijkstras算法,洪水填充和Hosam Alys解决方案后,我也没有发现任何重要的区别.我的代码仍然有效,但没有你想要运行的那么快.完整的消息来源是牧场.唯一有趣的线(我猜)是第78-118行的Dijkstra变体.

但速度不是这里的主要问题.如果有人能够指出算法中的差异,我真的很感激帮助.

• 在Hosam Alys算法中,他是从边界而不是每个节点扫描的唯一区别吗？
• 在Dijkstras你跟踪和覆盖走的距离,但不是在洪水填充,但这就是它？

Answer 1

假设地图是矩形的,您可以遍历所有边界点,并开始填充填充以找到起点的最远点:

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在哪里,表示周长上的边界点的数量,是点的数量,并且假设洪水填充将访问最大点四次(从各个方向).由于等于点数,这相当于,应该优于².(如果地图是正方形,则顺序为^1.5.)LW(L+W) * 2(L*W)4n(L + W) * 8 * nO(n)O(16n)

更新:根据评论,因为地图更像是一个迷宫(比起我最初想的那个有简单障碍的地图),你可以在上面做出相同的逻辑,但检查地图中的所有点(而不是点上的点)只有边境).这应该是O(4n^2的顺序),这仍然比FW和Dijkstra都要好.

注意: 洪水填充更适合此问题,因为所有顶点仅通过4个边框直接连接.地图的广度优先遍历可以相对快速地产生结果(仅仅是O(n)).我假设每个点可以在其4个邻居中的每一个的洪水填充中被检查,因此在上面的公式中的系数.

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

PS欢迎任何评论或更正.

Answer 2

跟进关于Floyd-Warshall或Hosam Aly的简单算法的问题:

我创建了一个可以使用这两种方法的测试程序.这些是文件:

• 迷宫创作者
• 找到最长的距离

在所有测试案例中,Floyd-Warshall的速度要慢一些,可能这是因为有限的边缘量可以帮助这个算法实现这一目标.

这些都是时代,每次这个领域都是四胞胎,10个领域中有3个是障碍.

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

Hosam Aly的时间似乎是二次的,因此我建议使用该算法.Floyd-Warshall的内存消耗也是n ²,显然超过了需要.如果你知道为什么Floyd-Warshall如此之慢,请发表评论或编辑这篇文章.

PS:我很长时间没有写过C或C++,我希望我没有犯过太多错误.

Answer 3

我删除了我推荐Floyd-Warshall算法的原始帖子.:(

gs做了一个现实的基准并且猜测是什么,FW比Hosam Aly的典型地图尺寸的"洪水填充"算法慢得多!因此,即使FW是一个很酷的算法,并且比Dijkstra的密集图快得多,我不能再推荐它的OP问题了,它涉及非常稀疏的图(每个顶点只有4个边).

作为记录:

• Dijkstra算法的有效实现需要O(Elog V)时间用于具有E边缘和V顶点的图形.
• Hosam Aly的"洪水填充"是广泛的第一次搜索,即O(V).这可以被认为是Dijkstra算法的一个特例,其中没有顶点可以修改其距离估计.
• 的Floyd-Warshall算法需要O(V ^ 3)的时候,是很容易的代码,并且仍然是最快为稠密的图(其中,顶点被典型地连接到许多其他顶点的那些图形).但它不是 OP任务的正确选择,它涉及非常稀疏的图形.

Answer 4

听起来你想要的是由图表直径分隔的终点.一个相当好且易于计算的近似是选择一个随机点,从中找到最远点,然后从那里找到最远点.最后两点应该接近最大分离.

对于矩形迷宫,这意味着两次洪水填充应该会给你一对非常好的起点和终点.