寻路与传送门技术

Question

5

我正在与虚拟机器人（Minecraft的计算机工艺模组中的海龟）一起开展一个项目，它将处于迷宫中并需要在其中导航。该世界已经方便地被划分为网格状的平铺砖块（每个砖块都有一个布尔类型的可通过/不可通过值），随着机器人建造通道，他将在地图上标记这些砖块。

此外，在机器人需要快速穿越的区域散布着传送门“快捷方式”。

问题来了：什么是最佳的路径规划方法？系统如何识别需要传送门的区域？A*是最著名的算法，但是否有其他更适合这种应用场景的算法？请注意我对路径规划算法几乎没有经验，因此您可能需要将其解释得更简单易懂。有什么建议吗？

- Schilcote

3

为何不先尝试使用A*算法，看看其表现如何？ - n. m.

我当然可以，但我认为A*算法不会考虑传送门等“捷径”，除非进行黑客攻击。我需要更深入地研究这个算法的工作原理。 - Schilcote

什么意思？我认为A*算法可以很好地处理零长度的边缘。我很好奇。 - n. m.

嗯，我会进行一些研究并编写实现。说不定可以开箱即用，谁知道呢。 - Schilcote

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BlueRaja - Danny Pflughoeft · Accepted Answer

使用A*算法唯一的问题在于需要为您的问题找到一个合适的启发式算法。幸运的是，这个已经在这里得到了解答。

“系统如何确定需要传送门的区域?”

这取决于海龟实际移动的起点/终点在哪里。如果它总是从相同的起始/终止点移动，那么答案就很简单：在起点和终点添加传送门。对于更复杂的设置，我猜这是NP难题; 如果是真的，你将不得不探索全局优化策略（或尝试许多随机位置并选择最佳位置）。