algorithm - 使用传送器寻路

Question

我正在开发一个虚拟机器人项目(Minecraft 的 ComputerCraft 模组中的 Turtles)，该机器人将处于迷宫般的隧道中，并且必须在其中导航。世界已经很方便地分成了瓷砖(它们的二维笛卡尔图，每个都有一个 bool 值 passable/nonpassable )， build 隧道的机器人将在他走的时候绘制它们。

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

问题是:让机器人寻路到目的地的最佳方式是什么？系统将如何识别需要传送器的区域？ A* 是最著名的算法，但是否还有其他算法可能更适合该应用程序？请记住，我对寻路算法的经验很少，因此您可能需要将事情分解为基本术语以便我理解。有什么建议吗？

Answer 1

使用 A* 的唯一问题是找到 admissible heuristic对于你的问题。幸运的是，这已经得到解答here .

How would the system identify areas that need teleporters?

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