5

我正在使用虚拟机器人(Minecraft 的 ComputerCraft mod 中的海龟)开展一个项目,机器人将在迷宫般的隧道中,并且必须在其中导航。世界已经很方便地划分为瓦片(它们的二维笛卡尔图,每个都有一个可通过/不可通过的布尔值),建造隧道的机器人将在他前进时映射它们。

此外,在机器人需要快速通过的区域周围散布着传送器“捷径”。

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

4

1 回答 1

3

使用 A* 的唯一问题是为您的问题找到一个可接受的启发式方法。幸运的是,这里已经回答了这个问题。

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

这取决于乌龟实际移动到/离开的位置。如果他总是往返于相同的起点/终点,答案很简单:在起点和终点添加传送。对于更复杂的设置,我猜这是 NP 难的;如果属实,您将不得不研究全局优化策略 (或者只是尝试一堆随机位置并选择最好的一个)

于 2013-02-24T21:57:25.970 回答