在《吃豆人》游戏中，鬼是否独立选择路径来找到吃豆人？

Question

最近我一直在手机上玩吃豆人游戏，不知道鬼是如何独立运作的。我思考了一下它是如何被编程的。

第一个想法是使用线程。四个鬼在各自的线程中运行，并找到吃豆人的位置。但是这样就需要四个线程同时工作并进行同步，这似乎有点过于复杂。而且，谷歌用JavaScript编写了吃豆人游戏，而JavaScript不支持线程，所以必须有一种更简单的方法。

我的第二个想法是使用事件处理程序。我将“方向改变”事件连接到四个事件处理程序中的每一个，让每个鬼决定如何走向吃豆人。我认为这更可能是正在发生的事情。但是，如果事件处理程序同步执行，计算路径将会按顺序进行，第四个鬼要改变方向需要时间，这可能会导致明显的延迟。此外，当鬼撞到墙壁时，它们会触发一个事件，它们的事件处理程序会改变鬼的方向。但是，考虑到吃豆人改变方向的频率以及四个鬼的响应速度，事件处理程序似乎也有些过于复杂。

我之所以说以上想法有些过于复杂，是因为请记住，这个游戏是在30年前编写的，当时CPU时间和内存非常稀缺，所以我认为必须有一种更简单的方法。

此外，似乎即使吃豆人静止不动，四个鬼也会沿着不同的路径移动。所有鬼是否使用完全不同或经过优化的路径查找算法？

我更感兴趣的是找出所有鬼如何同时工作的方式，而不是它们使用的路径查找算法。你有什么想法？

- Punit Vora

Answer 1

有很多关于pacman如何工作的信息，这里包括一些有关鬼怪行为的详细描述。

**请注意，我前段时间从寻路算法用于Pacman找到了这些信息。

编辑：

这篇博客文章还有更多有关鬼怪的信息。

- GWW

---

哇塞，这个页面真是太棒了 :D - Robert Karl

那是一个真正伟大的页面。但那个人肯定已经好几周没出过他的公寓了！！ - David Hoerster

http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior 这里有另一个关于它们行为的很好的解释。 - GWW

Answer 2

你在过度思考了。

对于视频游戏来说，线程和事件处理器非常缓慢。多线程游戏引擎是一个相对较新的发明，出现在《吃豆人》发布几十年之后。《吃豆人》的逻辑将在单个紧密循环中发生，类似于这个非常简化的伪代码：

while (!pacman_dead) {
  foreach ghost {
    if (ghost has hit a wall) {
      if (pacman to left) turn left
      if (pacman to right) turn right
    } else {
      go straight
      if (ghost touched pacman) {
        pacman_dead = true
      }
    }
  }

  handle_input();
  move_pacman();
  draw_screen();      
}

这是游戏中相当常见的模式，它给人并发的印象。通常一个游戏会在单个循环中运行，在屏幕重绘之间的空间里以微小的增量推进游戏状态。这就是为什么性能在游戏开发中仍然非常重要的原因：你的游戏必须迭代每个需要做某些事情或做出某些决策（AI控制的对手、移动平台、简单动画等）的游戏对象，并且每秒至少更新它们的状态30次。

- user229044

---

虽然内部肯定有更多的逻辑，但我认为这基本上应该是已经实现的想法。谢谢。 - Punit Vora

除非鬼魂在寻找/逃离你的情况下，否则它们会使用你的位置来确定最佳的道路选择（或随机选择其中之一）。顺便说一下，它们需要一个线程，以便独立于用户事件移动（如果你不移动，它们会抓住你）。 - Rudu

你需要一些鬼的移动中的随机性，否则，迟早所有的鬼都会一起成群移动，这样游戏就相对容易了。当然，鬼不必撞到墙壁才能改变方向，他可以在任何交叉口改变方向。在原始的吃豆人游戏中，鬼甚至可以毫无预警地倒退。 - Erich Kitzmueller

如果我没记错的话，幽灵的移动越远就越随机。或者说，当它们靠近时，它们的追逐变得更加激烈。如果你在逃跑时从一个幽灵身边跑过去，它们确实会堆积起来。一旦你成功地获得了一些距离，它们就会再次分散。 - Simon

@ErichKitzmueller：原始游戏对每个怪物使用不同的算法；没有任何随机性，也没有任何努力让幽灵避开彼此，但使用不同的算法意味着它们经常会聚集在一起，但不会永久保持在那里。 - supercat

Answer 3

在渲染每一帧之前，我会循环遍历幽灵。这样就没有事件、线程或异步问题了。每个幽灵可能都有一个非常简单的启发式算法来评分和决策（向左转还是向右转，不采取任何行动，随便怎么样）。

你可以查看这里的实现。:)

- Robert Karl