31

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

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

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

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

编辑：对。在查看了gs 的代码后，我又试了一次。这次我用 C++ 编写而不是 python。但是，即使在阅读了Dijkstras 算法、洪水填充和Hosam Alys 解决方案之后，我仍然没有发现任何关键的区别。我的代码仍然有效，但没有你看起来运行的那么快。完整的源代码在paste上。唯一有趣的行（我猜）是第 78-118 行的 Dijkstra 变体本身。

但速度不是这里的主要问题。如果有人愿意指出算法中的差异，我将非常感谢您的帮助。

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

9 回答 9

10

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

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是假设洪水填充最多可以访问一个点4 次（从各个方向）。因为n等于点数，所以这就等于(L + W) * 8 * n，应该比O(n2)好。（如果地图是正方形，则顺序为O(16n1.5)。）

更新：根据评论，由于地图更像是一个迷宫（而不是像我最初想的那样有简单障碍的迷宫），您可以在上面进行相同的逻辑，但检查地图中的所有点（而不是地图上的点）仅限边框）。这应该是O(4n2)的顺序，这仍然比 FW 和 Dijkstra 的要好。

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

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

PS 欢迎大家提出意见或更正。

于 2009-01-25T12:17:08.053 回答
9

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

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

在所有测试用例中，Floyd-Warshall 的速度都慢了很多，这可能是因为帮助该算法实现这一目标的边缘数量非常有限。

这些是时代，每次场都是四组，10个场中有3个是障碍物。

尺寸 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 2，显然超过了需要。如果您知道为什么 Floyd-Warshall 这么慢，请发表评论或编辑这篇文章。

PS：好久没写C或者C++了，希望没有犯太多错误。

于 2009-01-25T19:15:34.407 回答
6

听起来您想要的是由图形直径分隔的端点。一个相当好且易于计算的近似值是选择一个随机点，找到离该点最远的点，然后找到离那里最远的点。最后两点应该接近最大分离。

对于矩形迷宫，这意味着两个洪水填充应该为您提供一对非常好的起点和终点。

于 2009-01-25T21:13:09.257 回答
5

我删除了推荐 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 任务的正确选择，因为它涉及非常稀疏的图。
于 2009-01-25T20:17:57.853 回答
3

Raimund Seidel 在他的论文On the All-Pairs-Shortest-Path Problem in Unweighted无向图 [pdf]。

输入是邻接矩阵，输出是所有对最短路径距离矩阵。对于 n 个点，运行时间为 O(M(n)*log(n))，其中 M(n) 是矩阵乘法算法的运行时间。

如果您也需要，本文还提供了计算实际路径（在同一运行时）的方法。

Seidel 的算法很酷，因为运行时间与边数无关，但实际上我们并不关心这里，因为我们的图是稀疏的。但是，如果您想要所有对距离矩阵，这可能仍然是一个不错的选择（尽管运行时间比 n^2 稍差），而且这也可能比迷宫上的洪水填充更容易实现和调试。

这是伪代码：

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

要获得距离最大的点对，我们只需返回 argmax_ij(d_ij)

于 2009-01-25T23:36:14.803 回答
1

完成了该问题的 dijkstra 解决方案的 python 模型。代码有点长，所以我把它贴在别的地方：http ://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

在我设置的大小下，运行一个节点的算法大约需要 1.5 秒。为每个节点运行它需要几分钟。

但似乎不起作用，它总是将左上角和右下角显示为最长的路径；58 块瓷砖。当您没有障碍时，这当然是正确的。但是即使添加了几个随机放置的，程序仍然会找到最长的一个。也许它仍然是真实的，如果没有更高级的形状就很难测试。

但也许它至少可以显示我的野心。

于 2009-01-25T15:48:17.773 回答
1

好的，“Hosam 算法”是在节点上预选的广度优先搜索。Dijkstra 的算法不应该在这里应用，因为你的边缘没有权重。

差异至关重要，因为如果边的权重不同，您需要保持许多选项（备用路线）打开并在每一步中检查它们。这使得算法更加复杂。使用广度优先搜索，您只需探索一次所有边，确保您找到到每个节点的最短路径。即按您找到它们的顺序探索边缘。

所以基本上区别在于 Dijkstra 必须“回溯”并查看它之前探索过的边缘以确保它遵循最短路径，而广度优先搜索总是知道它遵循最短路径。

此外，在迷宫中，外边界上的点不能保证是最长路线的一部分。例如，如果你有一个巨大螺旋形状的迷宫，但外端回到中间，你可以有两个点，一个在螺旋的中心，另一个在螺旋的末端，两者在中间！

因此，一个很好的方法是从每个点使用广度优先搜索，但在搜索后删除起点（您已经知道往返它的所有路线）。广度优先的复杂度是 O(n)，其中 n = |V|+|E|。我们对 V 中的每个节点都这样做一次，所以它变成了 O(n^2)。

于 2009-01-29T00:50:08.100 回答
0

你的描述对我来说听起来像是一个迷宫路由问题。查看李算法。有关 VLSI 设计中的布局布线问题的书籍可能会对您有所帮助 - Sherwani 的“VLSI 物理设计自动化算法”很好，您可能会发现Sait 和 Youssef 的 VLSI 物理设计自动化很有用（而且在 Google 版本中更便宜...... )

于 2009-01-25T12:01:27.570 回答
0

如果您的对象（点）不经常移动，您可以在比 O(n^3) 更短的时间内执行这样的计算。

您所需要做的就是将空间分成大网格并预先计算网格间距离。然后选择占据最远网格的点对是一个简单的查表问题。在一般情况下，您只需要成对检查一小组对象。

如果距离度量是连续的，则此解决方案有效。因此，例如，如果地图中有许多障碍（如迷宫），则此方法可能会失败。

于 2009-01-25T14:16:32.420 回答