传送器寻路

Question

我正在做一个虚拟机器人的项目(我的世界的ComputerCraft模型中的海龟)，机器人将在一个迷宫般的隧道中，必须在其中导航。方便的是，世界已经被划分为瓦片(它们的二维笛卡尔图，每个瓦片都有一个布尔可通过值/不可通过值)，建造隧道的机器人将在移动过程中绘制它们的地图。

此外，在机器人需要快速到达它们之间的区域中，还散布着传送器“捷径”。

问题是:让机器人找到目的地的最好方法是什么？系统如何识别需要传送器的区域？A*是最著名的算法，但有没有其他算法可能更适合该应用程序？请记住，我在寻路算法方面的经验很少，所以你可能必须将事情分解成基本术语才能让我理解。有什么建议吗？

Answer 1

使用A*的唯一问题是找到解决问题的admissible heuristic。幸运的是，here已经回答了这个问题。

系统如何识别需要远程传输的区域？

这取决于海龟实际移动到/离开的位置。如果他总是移动到/从相同的起点/终点移动，答案很简单:在起点和终点添加远程传输。对于更复杂的设置，我的猜测是这是NP难的；如果是真的，您将不得不查看global-optimization strategies (或者只是尝试一堆随机位置并选择最好的位置)。