吃豆人游戏：眼睛如何找到怪物洞？

Question

我发现很多关于Pacman中鬼的AI的参考资料，但没有一个提到了在Pacman吃掉鬼后，它们的眼睛是如何找回中央鬼洞的。

在我的实现中，我使用了一种简单但可怕的解决方案。我仅仅硬编码了每个拐角应该采取的方向。

是否有更好或最佳的解决方案？也许有一种通用的解决方案，适用于不同的关卡设计？

- RoflcoptrException

---

你确定在角落处硬编码足够好吗？这并不能保证最佳路线。想象一下幽灵面对一条长而窄的通道。按照你的算法，他必须穿过整个通道，到达一个拐角，然后才能选择最快的路线。如果在每个方格上硬编码指定了方向，他可能会知道先掉头。 - Mark Peters

@Mark，这取决于你对“拐角”的定义。如果是T型连接，即使你只直走顶部线路，也可以通过。 - Thorbjørn Ravn Andersen

@Thorbjørn：我甚至没有谈论交叉口。看看这个游戏板：http://en.wikipedia.org/wiki/File:Pac-man.png。如果幽灵向右移动并位于左下角第二个点，它将一段时间内不会遇到任何交叉口。这将导致它比倒退（向左）并走最短路径多行进10个方块。 - Mark Peters

你的解决方案使用了路标点（或面包屑），我认为这是一种常用的技术，可以加速路径规划算法。 - Nick Dandoulakis

感谢所有的答案！我只是坚持了我的先前解决方案，并在每个角落硬编码了方向。要使其通用，需要关卡设计师/关卡文件在关卡定义中定义此信息。 - RoflcoptrException

Answer 1

实际上，我认为你的方法是一个相当棒的解决方案，与任何寻路算法相比几乎没有运行时间成本。

如果您需要将其推广到任意地图，则可以使用任何寻路算法-例如，广度优先搜索很容易实现，并使用它来计算每个角落应编码的方向，然后再运行游戏。

编辑（2010年8月11日）：我刚被引用到了一篇关于Pacman系统的非常详细的页面：《Pac-Man档案》，既然我在这里有采纳的答案，我觉得我应该更新一下。文章似乎没有明确涵盖返回怪物屋的行为，但它说明了Pac-Man中直接的寻路算法是以下步骤的情况：

• 继续朝下一个交叉点移动（虽然这实际上是“给出选择时，选择不涉及反转方向的方向”的特殊情况，如下一步所示）；
• 在交叉口处，查看相邻的出口方块，除了您刚来的方向；
• 选择离目标最近的出口方块。如果有多个方向离目标一样近，则按以下顺序选择第一个有效方向：上、左、下、右。

- Kylotan

---

我认为他的意思是你可以在运行时计算它（当关卡被加载但在开始玩之前），但只需要计算一次。这很容易维护。 - Mark Peters

好的，如果有一个创建地图的工具的话，那也可以。 - Kylotan

预先计算返回路径并没有错。这是以存储（路径）换取运行时性能为代价的交易。 - Steve Kuo

谢谢。我想我会坚持使用这个解决方案。有人知道在原版Pacman中是如何实现的吗？ - RoflcoptrException

不，我不需要。原先的问题使用了那个术语，但它并不完全具有法律约束力。 - Kylotan

Answer 2

我已经用一种通用的方法解决了这个问题：在关卡开始之前，我会从怪物出生点做一些“泛洪填充”操作；迷宫中每个不是墙壁的方块都会得到一个表示其距离怪物洞口有多远的数字。因此，当眼睛停留在一个距离为68的方块上时，它们会查看哪个相邻的方块距离为67；然后就朝那个方向走。

- Erich Kitzmueller

---

是的，洪水填充算法非常适合用于路径规划，在世界不太大以致于无法使用该算法时特别有效。我认为即使在较大的世界中，也可以通过施加预先计算了连通性的更粗略的网格来使用它。这样做可能会稍微绕路，但比我在这类游戏中看到的交通拥堵要好。 - Loren Pechtel

为节省空间（用于更大的世界或受限系统），您可以在每个交叉口保存行进方向，而不是为每个图块保存值。这本质上就是OP所建议的。 - BlueRaja - Danny Pflughoeft

BlueRaja: 当然可以，但这样做更加复杂，结果也不是最优的——幽灵会在两个交叉口之间被吃掉，所以它可能会朝错误的方向奔跑一段时间。我的解决方案在 http://en.wikipedia.org/wiki/HP_200LX 上运行良好，那么还有多少限制呢？ - Erich Kitzmueller

洪水填充算法很好，但实际上你并不需要一个完整的数字，只需要在每个方格中使用两位表示方向，指向下一个要使用的方格即可。原文意思已保持不变，译文更通俗易懂。 - Matthieu M.

Matthieu：是的，那将是一种可能的优化。 - Erich Kitzmueller

Answer 3

如果你想寻找一种替代传统路径规划算法的方法，你可以看看（名字相当恰当的）Pac-Man Scent Antiobject模式。

在启动时，你可以在迷宫中散布怪物洞口的气味，并让 "眼睛" 跟随气味回家。

一旦气味设置好了，运行时成本非常低。

---

编辑： 不幸的是，维基百科文章已被删除，所以请使用WayBack Machine……

- Dan Vinton

---

这将是我的回答。它与ammoQ的基本相同，但我总是记得吃豆人的气味 :) - Luke Schafer

看起来维基百科的文章已经失效/被删除了。谷歌搜索结果中排名最高的是这个帖子，但我认为这个链接接近于所需内容：[http://www.fatvat.co.uk/2010/08/sniffing-out-pacman.html]。 - David

我曾经有一瞬间感到困惑，但立刻明白了“scent”所指的含义。这是描述这些标量场物体的绝佳方式！ - Steven Lu

Answer 4

您应该查看路径查找算法，例如Dijsktra's Algorithm或A* algorithm。这就是您的问题：一个图形/路径问题。

- Clement Herreman

Answer 5

任何简单可行、易于维护、可靠并且性能足够好的解决方案都是一个好的解决方案。听起来你已经找到了一个好的解决方案......

路径查找解决方案可能比您当前的解决方案更加复杂，因此更有可能需要调试，而且速度也可能更慢。

我认为，如果它没有出现故障，就不要修理它。

编辑

在迷宫固定的情况下，您当前的解决方案是好的/优雅代码。不要误将“好”或“优雅”等同于“聪明”。简单的代码也可以是“好”的和“优雅”的。

如果您有可配置的迷宫级别，那么在最初配置迷宫时进行路径查找可能是最简单的解决方案。最简单的方法是由迷宫设计者手动完成。只有当您有大量迷宫...或用户可以设计它们时，才值得自动化这一过程。

（另外：如果路线是手工配置的，迷宫设计师可以通过使用次优路线使级别更有趣...）

- Stephen C

---

是的，它正在工作。但是我想写出好的代码，而不仅仅是代码。另外，我在我的问题中添加了最后一句话，所以如果可能的话，算法应该不仅适用于一个迷宫，而是适用于多个迷宫。 - RoflcoptrException

迷宫也可以生成（我有一个算法可以生成漂亮的吃豆人迷宫），因此自动化是正确的方法。 - Erich Kitzmueller

在这种情况下，您确实有无数的迷宫，或者用户可以设计它们。 - phuzion

@phuzion - 我知道这一点。但是，这两种情况之间有区别。如果是 OP 创建了大量的迷宫，那么手动创建路由就会很麻烦。如果是最终用户...那么这意味着 OP 必须编写文档，对最终用户的迷宫进行无休止的故障排除，处理无尽的关于不友好的投诉等等。换句话说，实现自动路由生成的原因是不同的。 - Stephen C

Answer 6

在最初的Pacman游戏中，幽灵通过他留在地图上的"气味"来找到黄色吃豆人。 幽灵会随机徘徊直到找到气味，然后他们只需沿着气味路径向玩家移动即可直接找到玩家。每次Pacman移动时，“气味值”会减少1。

现在，一个简单的反转整个过程的方法是有一种“幽灵气味金字塔”，它的最高点位于地图的中心，然后幽灵就只需朝着这个气味方向移动即可。

- Ivo Wetzel

---

我非常喜欢这种方法，我也会尝试一下。 - RoflcoptrException

这不正确；如果他们都按照这个算法行动，他们最终会单纯地追着他跑。每个鬼的行为都不同；你可以在维基百科文章中找到更多信息。 - divider

Answer 7

假设您已经拥有追逐pacman所需的逻辑，为什么不重复使用它呢？只需更改目标即可。这似乎比尝试使用完全相同的逻辑创建一个全新的例程要少做很多工作。

- John Gardeniers

---

是的，我已经实现了追逐吃豆人的逻辑，但我对它也不满意 ;) - RoflcoptrException

根据我的经验（我喜欢为了好玩写吃豆人游戏的不同版本），这样做可能会导致眼睛卡在洞外很长时间。这是因为追逐算法通常是按照“如果吃豆人在北边，就向北走”的方式进行的，但是迷宫中可能会有“陷阱”，眼睛必须先向南走。由于吃豆人会移动，所以幽灵迟早会逃脱，但洞是一个固定的目标。（注意：我说的是生成的迷宫） - Erich Kitzmueller

Answer 8

我找到的这是关于它如何实际工作的最好的来源。

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn 当幽灵被杀死时，它们的无形眼睛会返回其起始位置。这只需要将幽灵的目标瓷砖设置为该位置即可。导航使用相同的规则。

这实际上很有道理。也许不是世界上最有效的方法，但这是一种非常好的方式，可以不必担心另一个状态或任何类似的问题，你只需更改目标即可。

旁注：我没有意识到那些吃豆人程序员有多么棒，他们基本上在非常小的空间内用非常有限的内存制作了整个消息系统……这太神奇了。

- Midpipps

Answer 9

这是一个寻路问题。有一种流行的算法叫做A*算法。

- Marijn

Answer 10

每个正方形的值都是距离中心的距离，这样对于给定的每个正方形，您可以获得所有可能方向上的相邻正方形的值。选择具有最低值的正方形并移动到该正方形。

使用任何可用算法预先计算值。

- mvbl fst

---

我本来想建议这个。从“怪物洞”开始进行外部泛洪填充。我认为你的答案会受益于一张图片。 - charles-allen