三维寻径AI算法的推荐与分析

Question

我正试图解决以下问题:我有一个2D平铺游戏，包括飞机在空域飞行，试图降落在最近的机场(可以有'n‘个目标)。这样做的目的是让飞机自己寻找最好的路径，避免出现结肠炎。

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

关于启发式方法，我放弃了曼哈顿实例，因为我希望算法更高效(因为你知道，一个好的启发式算法可以进行更有效的搜索，曼哈顿的搜索成本过高，而且我正在使用对角线移动)，所以我决定实现对角线距离(它结合了曼哈顿和欧几里得的两个方面)，推荐为8-邻接(也是在对角线移动中扩展节点)。但我有更多的邻接，所以我试图将对角距离公式调整为16-邻接(不包括上下对角线，如上、东北、下、下斜线等)，因此曼哈顿对每一个“对角线移动”的估计(除了我提到的那些)具有相同的成本值(1对角移动=2个八角形移动，而不是3，就像我已经排除的“上下对角线”中的那样)，并且这个启发式的公式被概括如下：

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

numberOfDiagonalSteps =min{xb\x，\{xb\x}，\x{xb}}

manhattanDistance =xa\xb/yb/yb+\x-zb/zb

numberOfStraightSteps = manhattanDistance -2*

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

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

好吧..。我的一个问题是，当飞机在移动(“障碍节点”)，算法必须刷新，重新执行，那么，你建议我做什么最好呢？我是说..。这样做更好，还是更好地实现D*-Lite？

我的另一个问题是时间的复杂性。很明显，这些算法的最坏情况是指数型的，但是它确实可以从一个好的启发式中得到改进。但我不知道如何精确地分析问题中的算法。对于这个算法，我能给出什么时间复杂度，或者你建议我在我的情况下做什么？

感谢您的关注。

Answer 1

我会使用简单的地图填充参见：

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

但地图将有更多的层次(飞行高度)。其中只有少数几层(以限制时间/内存浪费)，例如，8层应该足以容纳128架飞机。

当然，它取决于二维地图的面积大小，而且在填充地图之后，只需从地图中选择最短的路径。在填写地图时，考虑任何平面都是障碍物(为了安全起见，周围有一些边界)。在这个算法中，您可以非常简单地添加燃料消耗标准或任何其他。

此外，机场的选择可以非常简单，这(首先要先得到最接近的一个)。您必须在决定时为每架飞机绘制地图(或为每架飞机分别重新归档同一架飞机)。不需要成为整个地图..。只是目的地和飞机之间的区域

如果你必须遵守空中交通规则，那么你需要应用飞行计划+临时调度代替。这不是一件容易的事情(我花了将近半年的时间对其进行编码)，而且空中交通管制也有点复杂，特别是空中和实地共享的等待问题。所有这些都必须通过动态变化(天气、等待、技术/政治或安全问题，.)但我强烈怀疑上面简单的地图填充应该是这样的情况:)