找到相距最远的两点的算法 [英] Algorithm to find two points furthest away from each other

问题描述

我正在寻找一种用于我制作的赛车游戏的算法.地图/关卡/轨道是随机生成的，所以我需要找到两个位置，起点和目标，以充分利用地图.

Im looking for an algorithm to be used in a racing game Im making. The map/level/track is randomly generated so I need to find two locations, start and goal, that makes use of the most of the map.

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

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

Regarding the calculation of distance, it should not be the "bird path" for a lack of a better word. The path between A and B should be longer if there is a wall (or other blocking area) between them.

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

Im unsure on where to start, comments are very welcome and proposed solutions are preferred in pseudo code.

对.在查看了 gs 的代码后，我再试一次.这次我不是用 python 写的，而是用 C++ 写的.但是，即使在阅读了 Dijkstras 算法 之后，floodfill 和 Hosam Alys 解决方案，我没有发现任何重要的区别.我的代码仍然有效，但没有你似乎让你的代码运行那么快.完整来源位于 pastie.唯一有趣的几行(我猜)是第 78-118 行的 Dijkstra 变体本身.

Right. After looking through gs's code I gave it another shot. Instead of python, I this time wrote it in C++. But still, even after reading up on Dijkstras algorithm, the floodfill and Hosam Alys solution, I fail to spot any crucial difference. My code still works, but not as fast as you seem to be getting yours to run. Full source is on pastie. The only interesting lines (I guess) is the Dijkstra variant itself on lines 78-118.

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

But speed is not the main issue here. I would really appreciate the help if someone would be kind enough to point out the differences in the algorithms.

• 在 Hosam Alys 算法中，唯一的区别是他从边界扫描而不是从每个节点扫描?
• 在 Dijkstras 中，您会跟踪并覆盖所走的距离，但在洪水填充中不会，仅此而已?

推荐答案

假设地图是矩形的，可以遍历所有的边界点，开始洪水填充，找到离起点最远的点:

Assuming the map is rectangular, you can loop over all border points, and start a flood fill to find the most distant point from the starting point:

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> 是地图的宽度，(L+W) * 2 表示边界点数超过周长，(L*W) 是点数，而 4 是假设 flood-fill 最多访问一个点 4 次(从各个方向).由于n相当于点数，这相当于(L + W) * 8 * n，应该比O(n²).(如果地图是正方形，则顺序为O(16n^1.5).)

I guess this would be in O(n^2). If I am not mistaken, it's (L+W) * 2 * (L*W) * 4, where L is the length and W is the width of the map, (L+W) * 2 represents the number of border points over the perimeter, (L*W) is the number of points, and 4 is the assumption that flood-fill would access a point a maximum of 4 times (from all directions). Since n is equivalent to the number of points, this is equivalent to (L + W) * 8 * n, which should be better than O(n²). (If the map is square, the order would be O(16n^1.5).)

更新:根据评论，由于地图更像是一个迷宫(而不是我最初想到的带有简单障碍的迷宫)，您可以采用上述相同的逻辑，但要检查所有点在地图中(而不是仅在边界上的点).这应该是 O(4n²) 的顺序，这仍然比 F-W 和 Dijkstra 的要好.

Update: as per the comments, since the map is more of a maze (than one with simple obstacles as I was thinking initially), you could make the same logic above, but checking all points in the map (as opposed to points on the border only). This should be in order of O(4n²), which is still better than both F-W and Dijkstra's.

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

Note: Flood filling is more suitable for this problem, since all vertices are directly connected through only 4 borders. A breadth first traversal of the map can yield results relatively quickly (in just O(n)). I am assuming that each point may be checked in the flood fill from each of its 4 neighbors, thus the coefficient in the formulas above.

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

Update 2: I am thankful for all the positive feedback I have received regarding this algorithm. Special thanks to @Georg for his review.

附言欢迎提出任何意见或更正.

P.S. Any comments or corrections are welcome.

这篇关于找到相距最远的两点的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！