吃豆人:眼睛是如何找到回到怪物洞穴的？

Question

我在“吃豆人”中找到了很多关于幽灵的人工智能的参考资料，但没有一个提到在幽灵被吃了之后眼睛是如何找到回到中央幽灵洞的。

在我的实现中，我实现了一个简单但糟糕的解决方案。我只是在每个角落硬编码了应该走的方向。

有没有更好的/或最好的解决方案？也许是一个通用的，可以与不同级别的设计一起工作的？

Answer 1

实际上，我想说你的方法是一个非常棒的解决方案，与任何类型的寻路相比，几乎没有运行时间成本。

如果你需要它来推广到任意地图，你可以使用任何寻路算法，例如，广度优先搜索很容易实现，并在游戏运行之前，使用它来计算在每个角落编码的方向。

编辑(2010年8月11日)：我刚刚被推荐到一个关于吃豆人系统的非常详细的页面：The Pac-Man Dossier，既然我在这里有了公认的答案，我觉得我应该更新它。这篇文章似乎没有明确地涵盖返回怪物屋的行为，但它指出了Pac-Man中的直接寻路是以下情况的一个例子：

• 继续朝下一个交叉口前进(尽管这本质上是一个特例，如果有选择，请选择不涉及反转方向的方向，如下一步所示)；
• 在交叉口，查看相邻的出口方块，除了您刚从的那个；
• 选择离目标最近的一个。如果不止一个离目标同样近，请按以下顺序选择第一个有效方向:上、左、下、右。

Answer 2

我以这种方式解决了通用关卡的这个问题:在关卡开始之前，我从怪物洞中进行了某种“洪水填充”；迷宫中不是墙的每一块瓷砖都会得到一个数字，上面写着它离洞有多远。因此，当眼睛在距离为68的瓷砖上时，他们会查看相邻的瓷砖中距离为67的瓷砖；这就是前进的方向。

Answer 3

对于更传统的寻路算法的替代方案，您可以查看一下(命名恰当！) Pac-Man Scent Antiobject pattern。

你可以在启动时在迷宫周围散布怪物的气味，让眼睛跟着它回家。

一旦设置了嗅觉，运行时成本就非常低。

编辑:遗憾的是，维基百科的文章已经被删除了，所以WayBack Machine to the rescue...