algorithm - 3D Pathfinding AI算法推荐与分析

Question

我正在尝试解决以下问题:我有一个 2D 平铺游戏，其中包括在领空飞行的飞机，试图降落在最近的机场(可以有“n”个目标)。这个想法是让飞机自己搜索最佳路径，避免碰撞。

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

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

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

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

曼哈顿距离 = |xa-xb| + |ya-yb| + |za-zb|

numberOfStraightSteps = manhattanDistance - 2*numberOfDiagonalSteps

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

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

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

我的另一个问题是关于时间复杂度的。很明显，这些算法的最坏情况是指数级的，但它确实可以通过良好的启发式算法得到改进。但是我没有找到如何精确分析我的问题中的算法。我可以为该算法提供什么时间复杂度，或者您建议我在我的情况下做什么？

感谢您的关注。

Answer 1

我会使用简单的 map 填充见:

• http://en.wikipedia.org/wiki/Dijkstra 's_algorithm
• https://www.allegro.cc/forums/thread/599046

但是 map 会有更多层(飞行高度)。它们可以很少(以限制时间/内存浪费)，例如 8 层应该足以容纳多达 128 架飞机。

当然这取决于 2D map 区域的大小，并且在填充 map 后只需从中取最短路径。在填充 map 时，将任何平面视为障碍物(为了安全起见，周围有一些边界)。在此算法中，您可以非常简单地添加油耗标准或任何其他标准。

机场的选择也可以很简单(先想先得到最近的)。您必须在做出决定时为每架飞机准备好 map (或分别为每架飞机重新填写相同的 map )。不需要是整个 map ......只是目的地和飞机之间的区域

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