1

我正在尝试解决以下问题：我有一个 2D 平铺游戏，其中包括在空域中飞行的飞机，试图降落在最近的机场（可能有 'n' 个目标）。这个想法是让飞机自己寻找最佳路径，避免碰撞。

所以我打算尝试 A* 算法，但后来我发现了另一个限制：如果需要，飞机可以改变它们的高度。所以我有了实现 A* 相同理念的想法，但在 3D 中（将节点扩展到可能的移动，让平面也向上、向下、向下、向北、向上等移动，制作抽象的 3D处理相对高度，从而让算法找到具有 3D 移动的最佳路径）。

关于启发式，我放弃了 manhattan 实例，因为我希望算法更高效（因为你知道一个好的启发式可以进行更有效的搜索，manhattan 高估了成本，而且我正在使用对角线移动），所以我决定实现对角线距离（结合了曼哈顿和欧几里得的方面），推荐用于 8 邻接（扩展节点也在对角线移动中）。但是我有更多的邻接点，所以我试图将对角线距离公式调整为 16 个邻接点（不包括向上和向下对角线，如 up-northeast、down-sowthwest 等），所以曼哈顿对每个 ' 的估计对角线移动'（除了我提到的那些）具有相同的成本值（1 个对角线移动 = 2 个正交移动，而不是 3，因为它在我排除的“上下对角线”中），

设节点 A 为起点，节点 B 为目标，它们各自的位置为 (xa,ya,za) 和 (xb,yb,zb)

numberOfDiagonalSteps = min{|xa-xb|,|ya-yb|,|za-zb|}

曼哈顿距离 = |xa-xb| + |是的| + |za-zb|

numberOfStraightSteps = manhattanDistance - 2*numberOfDiagonalSteps

并假设对角线步骤成本 sqrt(3)（你知道，毕达哥拉斯，正交成本为 1）：

启发式是：h(n) = numberOfStraightSteps + sqrt(3)*numberOfDiagonalSteps

嗯......我的一个问题是，随着飞机的移动（“障碍节点”），算法必须刷新，重新执行，所以，你建议我做什么最好？我的意思是......是这样尝试更好，还是更好地尝试实施 D*-Lite？

我的另一个问题是关于时间复杂度的。很明显，这些算法的最坏情况是指数级的，但它可以从一个好的启发式算法中得到真正的改进。但是我没有找到如何精确分析我的问题中的算法。我可以给那个算法多少时间复杂度，或者你建议我在我的情况下做什么？

感谢您的关注。

4

1 回答 1

0

我会使用简单的地图填充，请参阅：

但地图将有更多图层（飞行高度）。它们中可能只有少数（以限制时间/内存浪费），例如 8 层应该足以容纳多达 128 架飞机。

当然，这取决于2D地图区域的大小，并且在填充地图后，只需从中选取最短路径。在填充地图时，将任何飞机视为障碍物（为安全起见，周围有一些边界）。在这个算法中，您可以非常简单地添加燃料消耗标准或任何其他标准。

机场选择也可以通过这个非常简单（首先想要最接近的）。您必须在做出决定时为每架飞机准备好地图（或分别为每架飞机重新填写相同的地图）。不需要是整个地图......只是目的地和飞机之间的区域

如果您必须遵守空中交通规则，那么您需要改为应用飞行计划 + 临时调度。这不是一件容易的事（我花了将近半年的时间来编写它），而且空中交通管制有点复杂，尤其是在地面上等待空中和现场共享的问题。一切都必须通过动态变化（天气，等待，技术/政治或安全问题，...），但我强烈怀疑这种情况，所以上面的简单地图填充应该这样做:)

于 2013-11-13T10:25:38.330 回答