算法找到两个点最远远离彼此 [英] 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.

• 的算法是工作两维空间
里面
• 从每一个点，一个人只能穿越到四个方向的下一个点;上，下，左，右
• 在积分只能阻止或nonblocked，只有nonblocked点可以遍历

对于距离的计算，它不应该是鸟道为缺乏一个更好的词。 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.

林不能确定从哪里开始，评论是非常欢迎，并提出解决方案pferred伪code $ P $。

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

编辑：右。细算通过<一个href="http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other#478076">gs's code我给它一个镜头。取而代之的蟒蛇，我这次在C ++写的。但尽管如此，即使在Dijkstras算法阅读起来，在此时，floodFill 和<一href="http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other#477627">Hosam艾丽斯解决方案，我没有发现任何重要区别。我的code仍然有效，但没有那么快，你似乎得到你的运行。完整的源是 pastie 。唯一有趣的线（我猜）是Dijkstra算法的变体本身的线78-118。

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.

但速度并不是主要的问题在这里。我真的AP preciate的帮助，如果有人会好心地指出了算法的不同之处。

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艾丽斯算法，是他从边界扫描的每一个节点，而不是唯一的区别？
• 在Dijkstras您跟踪和覆盖的距离走了，但不是在此时，floodFill，但多数民众赞成什么呢？

推荐答案

假设地图是矩形的，你可以遍历所有过境点，并开始倾倒填充发现从起点最远的点：

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 *（长*宽）* 4 ，其中→是长度和是W 是地图的宽度，（L + W）* 2 重presents边界点的数量在周边，（长*宽）是点的数量，而 4 是假设洪水填充将访问一个点的最大的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 ² ），这仍然比好无论FW和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的<一个href="http://stackoverflow.com/questions/477591/algorithm-to-find-two-points-furthest-away-from-each-other#478076">his回顾。

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。任何意见或更正是受欢迎的。

P.S. Any comments or corrections are welcome.

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