我正在尝试解决以下问题：我有一个2D拼接游戏，游戏中飞机在空域中飞行，试图降落在最近的机场（可能有’n’个目标）。我的想法是让飞机自己寻找最佳路径，同时避免碰撞。
所以我原本打算尝试A*算法，但随后我发现了另一个限制：飞机可以在需要时改变高度。因此，我有了在3D中实现A*算法相同哲学的想法（扩展节点到可能的移动，让飞机也可以向上、向下、向下-北、上-东等移动，创建一个抽象的3D来处理相对高度，从而让算法找到使用3D移动的最佳路径）。
关于启发式，我放弃了曼哈顿距离，因为我希望算法更有效（因为你知道好的启发式可以使搜索更有效，曼哈顿距离会高估成本，而我使用的是对角线移动），所以我决定实现对角线距离（它结合了曼哈顿和欧几里得距离的特点），推荐用于8相邻（节点也扩展到对角线移动）。但我有更多的相邻情况，所以我试图将对角线距离公式调整到16相邻（不包括像上-东北、下-西南等上下对角线），因此每个“对角线移动”（除了我提到的那些）的曼哈顿估计具有相同的成本值（1个对角线移动=2个正交移动，而不是我排除的“上下对角线”中的3个），基于此，该启发式的公式被概括如下：
设节点A为起点，B为目标，它们的各自位置为(xa,ya,za)和(xb,yb,zb)
对角线步数 = min{|xa-xb|,|ya-yb|,|za-zb|}
曼哈顿距离 = |xa-xb| + |ya-yb| + |za-zb|
直线步数 = 曼哈顿距离 – 2*对角线步数
假设对角线步数的成本为sqrt(3)（你知道，毕达哥拉斯，正交成本为1）：
启发式为：h(n) = 直线步数 + sqrt(3)*对角线步数
嗯…我的一个问题是，由于飞机在移动（“障碍节点”），算法必须不断刷新、重新执行，那么你建议我怎么做最好？我是说…这样尝试更好，还是尝试实现D*-Lite更好？
我的另一个问题是关于时间复杂度。这些算法的最坏情况显然是指数级的，但可以通过好的启发式大大改善。但我找不到如何精确分析我问题中的算法。我能给这个算法什么样的时间复杂度，或者你建议我在我的情况下做什么？
谢谢你的关注。
回答：
我会使用简单的地图填充，参见：
但地图将有更多层（飞行高度）。这些层可以很少（以限制时间/内存浪费），例如8层应该足以应对最多128架飞机。
当然，这取决于2D地图区域大小，并且在填充地图后，只需从中选择最短路径。在填充地图时，将任何飞机视为障碍物（周围有一些安全边界）。在这种算法中，你可以非常简单地添加燃料消耗标准或任何其他标准。
机场选择也可以通过这种方式变得非常简单（先到先得最近的一个）。你必须在决策时为每架飞机准备一张地图（或为每架飞机单独重新填充同一张地图）。不需要是整个地图…只需是目的地和飞机之间的区域
如果你必须遵守空中交通规则，那么你需要应用飞行计划+临时调度。这不是一个简单的任务（我花了将近半年时间来编写它），而且空中交通控制有点复杂，尤其是空中和地面上的等待队列和场地共享。所有这些都必须是动态可变的（天气、等待、技术/政治或安全问题等），但我强烈怀疑这不是这种情况，所以上面的简单地图填充应该可以做到 🙂
