在迷宫中寻找移动实体的算法

Question

我有一个迷宫和一个由玩家控制的角色，还有一个必须自己找到他的无人机。有人知道一种（高效的）AI算法可以做到这样吗？ 附注：我知道有几种路径查找算法（例如A *），但据我所知，这些算法仅适用于查找“不移动”的两个节点之间的路径（如果我的角色静止不动，这将起作用，但显然不是这种情况）。

- conectionist

---

无人机是否知道迷宫的布局，还是必须在移动过程中发现？此外，它在移动时是否知道玩家在迷宫中的位置？ - cdeszaq

A*算法还要求您事先知道起点和终点的位置。无人机知道玩家在哪里并只需到达那里吗？还是无人机也需要定位玩家？ - Jack Edmonds

@cdeszaq 是的，它知道迷宫的布局（尽管我不介意假设它不知道），而且它确实知道玩家在迷宫中的位置。 - conectionist

@JackEdmonds 是的，它只需要到达他那里。但要考虑到玩家不断移动的事实。 - conectionist

如果迷宫不太大，您可以使用 Floyd-Warshall 算法获取所有最短路径。然后，您可以查找所有可能的玩家 <-> 无人机位置的最短路径。如果您的迷宫太大，请尝试搜索道路交叉口之间的最短路径。然后，您可以查找所有可能的玩家（下一个交叉口）<-> 无人机（下一个交叉口）位置的最短路径。 - Zeta

@Zeta 它的维度在每次运行时都不同。但 Floyd-Warshall 算法并不是一个坏主意。 - conectionist

Answer 1

如果“起点”是无人机所在的位置，“终点”是撞到玩家，那么您只能使用“标准”算法定期使用A*，并从中确定无人机需要移动的位置。

随着您越来越接近玩家，由于搜索空间理论上较小，因此您将计算得更快。

使用这种方法，玩家可以找到一组位置，当在它们之间移动时，会导致无人机被卡住来回移动，但这些优化是特定于情况的，通用算法不会包括它们。

基本上，每个“帧”您都有一个固定的搜索空间，但您只需在每个帧上运行它以决定要做什么。

可能有微小扰动的A*调整，但我脑海中没有任何了解。

- cdeszaq

---

这实际上是我第一个想到的事情。这个解决方案的问题之一是计算路径可能会花费无人机很长时间，然后其运动可能看起来像这样：移动一点，然后停下来计算，然后再移动，然后再次计算等等。我希望它能够持续移动（有点像幽灵在吃豆人游戏中移动的方式）。 - conectionist

我同意，A算法可能是你最好的选择。当人类移动时，您需要停止A计算的能力。您还需要在人类或无人机移动时每次更新起始和结束目标。我猜您也可以使用Johnson算法来查找所有可能位置之间的所有最短路径，然后将其用作查找表。如果迷宫不是动态的，那么这应该可以工作。http://en.wikipedia.org/wiki/Johnson%27s_algorithm - Justin

@Justin - 我喜欢查找的想法...比连续执行A要快得多。你可以使用相同的记忆化思想与A一起缓存结果。然后，您将根据玩家和无人机的位置和历史记录逐渐构建查找表，忽略迷宫的“未访问”部分，直到需要它们为止。 - cdeszaq

@Justin 确实，这个解决方案听起来更好。如果我找不到更好的东西，我想我会尝试这个。 - conectionist

越想越觉得，从效率的角度来看，最好还是在初始化时从每个顶点使用普通的Dijkstra算法，并将其用作查找表。就像Johnson算法一样，不需要初始的Bellman-Ford步骤，因为图中不能有负权重。基本上，所有的权重都应该是1。 - Justin