用传送器寻找路径

Question

我正在与一个虚拟机器人（海龟在Computercraft模组为我的世界），其中的机器人将在迷宫的隧道，并必须在其中导航。这个世界已经很方便地被分成了几个瓦片（它们的二维笛卡尔图形，每个瓦片都有一个布尔可通过/不可通过的值），并且建造隧道的机器人将会随着他的走向而映射它们。

此外，还有传送器“快捷键”散布在机器人需要快速切换的区域。

问题是：有什么方法让机器人路径到达目的地？系统如何识别需要传送器的区域？ A *是最着名的算法，但有其他可能更适合应用程序的算法吗？请记住，我在寻路算法方面的经验很少，因此您可能必须将其分解为基本术语以供我理解。有什么建议么？

Answer 1

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

系统将如何识别需要传送器的区域？

这取决于乌龟实际在哪里移动/从哪里移动。如果他总是往/从相同的起点/终点移动，则答案很简单：在开始和结束时添加传送。对于更复杂的设置，我的猜测是这是NP难度;如果属实，你必须考虑global-optimization strategies（或者只是尝试一堆随机位置，并采取最好的一个）。