322

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

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

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

4

22 回答 22

153

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

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

编辑（2010 年 8 月 11 日）：我刚刚被提到了 Pacman 系统上的一个非常详细的页面：The Pac-Man Dossier，因为我在这里得到了接受的答案，所以我觉得我应该更新它。这篇文章似乎没有明确提到返回怪物屋的行为，但它指出吃豆人中的直接寻路是以下情况：

  • 继续向下一个交叉点移动（尽管这本质上是“当给出选择时，选择不涉及反转方向的方向，如下一步所示）的特殊情况；
  • 在十字路口，看看相邻的出口广场，除了你刚来的那个；
  • 选择离目标最近的一个。如果不止一个同样靠近目标，请按以下顺序选择第一个有效方向：上、左、下、右。
于 2010-06-30T10:50:08.597 回答
86

我通过这种方式解决了通用关卡的这个问题：在关卡开始之前，我从怪物洞中进行了某种“洪水填充”；迷宫的每一块不是墙的瓷砖都有一个数字，表示它离洞有多远。因此，当眼睛在距离为 68 的棋子上时，他们会看相邻的哪个棋子的距离为 67；那就是要走的路。

于 2010-06-30T13:10:22.403 回答
43

对于更传统的寻路算法的替代方法，您可以查看（适当命名的！）Pac-Man Scent Antiobject pattern。

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

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

编辑：可悲的是，维基百科的文章已被删除，所以WayBack Machine 来救援......

于 2010-06-30T11:17:54.853 回答
19

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

于 2010-06-30T10:47:13.970 回答
18

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

寻路解决方案可能比您当前的解决方案更复杂，因此更可能需要调试。它可能也会更慢。

IMO，如果它没有损坏，请不要修复它。

编辑

IMO，如果迷宫是固定的，那么您当前的解决方案是好的/优雅的代码。不要把“好”或“优雅”等同于“聪明”。简单的代码也可以是“好”和“优雅”的。

如果您有可配置的迷宫级别，那么也许您应该在最初配置迷宫时进行寻路。最简单的方法是让迷宫设计师手工完成。如果您有无数迷宫，我只会费心将其自动化......或者用户可以设计它们。

（顺便说一句：如果路线是手动配置的，迷宫设计者可以通过使用次优路线使关卡更有趣......）

于 2010-06-30T10:48:51.133 回答
13

在最初的吃豆人中，鬼魂通过他的“气味”找到了黄色的食丸者，他会在地图上留下痕迹，鬼魂会随意四处游荡，直到他们找到气味，然后他们会简单地沿着气味路径直接引导他们到玩家。每次吃豆人移动时，“气味值”都会减少 1。

现在，一个简单的扭转整个过程的方法是建立一个“幽灵气味金字塔”，它的最高点在地图的中心，然后幽灵就朝着这个气味的方向移动。

于 2010-07-05T03:28:26.750 回答
5

假设你已经有了追逐 pacman 所需的逻辑，为什么不重用它呢？换个目标就好了。似乎这比尝试使用完全相同的逻辑创建一个全新的例程要少得多。

于 2010-07-01T04:38:24.793 回答
3

这是一个寻路问题。有关流行的算法，请参阅http://wiki.gamedev.net/index.php/A*。

于 2010-06-30T10:47:07.720 回答
3

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

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

于 2010-07-16T23:34:13.970 回答
3

这是我能找到的关于它实际工作原理的最佳来源。

http://gameai.com/wiki/index.php?title=Pac-Man#Respawn 当鬼魂被杀死时，他们脱离实体的眼睛会回到他们的起始位置。这只需将幽灵的目标图块设置到该位置即可完成。导航使用相同的规则。

这实际上是有道理的。也许不是世界上最有效的方法，但这是一种非常好的方法，无需担心其他状态或任何类似的事情，您只是在更改目标。

旁注：我没有意识到那些吃豆人程序员有多棒，他们基本上在一个非常小的空间和非常有限的内存中构建了一个完整的消息系统……这太棒了。

于 2012-01-11T19:07:43.467 回答
2

我不太了解您是如何实现游戏的，但是您可以执行以下操作：

  1. 确定眼睛位置相对于门的位置。即它在上面吗？就在下面？
  2. 然后将眼睛移到两个方向之一的相反方向（例如，如果它在门的右侧，则使其向左移动，在门的下方）并检查是否有墙壁阻止您这样做。
  3. 如果有墙阻止你这样做，那么让它向另一个方向移动（例如，如果眼睛相对于图钉的坐标是右北并且它当前正在向左移动但有一面墙挡住了它向南移动。
  4. 记住每次移动时都要不断检查，以不断检查眼睛相对于门的位置，并检查何时没有纬度坐标。即它只在大门上方。
  5. 在只有在门上方的情况下，如果有墙，则向下移动，向左或向右移动并继续执行此数字 1 - 4，直到眼睛进入书房。
  6. 我从未在 Pacman 中看到过死胡同，这段代码不会说明死胡同。
  7. 此外，我还提供了一个解决方案，当眼睛在我的伪代码中跨越原点的墙壁之间“摆动”时。

一些伪代码：

   x = getRelativeOppositeLatitudinalCoord()
   y
   origX = x
    while(eyesNotInPen())
       x = getRelativeOppositeLatitudinalCoordofGate()
       y = getRelativeOppositeLongitudinalCoordofGate()
       if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
            while (move(y) == false)
                 move(origX)
                 x = getRelativeOppositeLatitudinalCoordofGate()
        else if (move(x) == false) {
            move(y)
    endWhile
于 2010-07-01T04:32:39.227 回答
2

我建议幽灵存储他从洞到吃豆人的路径。所以鬼一死，他就可以沿着这条存储的路径反向。

于 2010-08-19T12:01:38.510 回答
2

dtb23 建议在每个角落随机选择一个方向，最终你会发现怪物洞听起来非常低效。

但是，您可以利用其低效的返家算法，通过引入更多游戏难度的变化来使游戏更加有趣。您可以通过应用上述方法之一来做到这一点，例如您的航路点或洪水填充，但这样做是不确定的。所以在每个角落，你都可以生成一个随机数来决定是采取最优的方式，还是随机的方向。

随着玩家等级的提高，您会降低采取随机方向的可能性。除了关卡速度、幽灵速度、吃药暂停等之外，这将在整体难度级别上增加另一个杠杆。当幽灵只是无害的眼睛时，你有更多的时间放松，但随着你的进步，时间会变得越来越短。

于 2010-09-02T06:08:51.500 回答
2

我认为您的解决方案适合该问题，比这更简单，是使新版本更“逼真”，鬼眼可以穿过墙壁=）

于 2010-06-30T12:57:41.700 回答
2

简短的回答，不是很好。:) 如果你改变吃豆人迷宫，眼睛不一定会回来。一些四处流传的黑客有这个问题。所以它取决于有一个合作迷宫。

于 2012-01-11T22:17:02.257 回答
2

这是 ammoQ 的洪水填充想法的模拟和伪代码。

queue q
enqueue q, ghost_origin
set visited

while q has squares
   p <= dequeue q
   for each square s adjacent to p
      if ( s not in visited ) then
         add s to visited
         s.returndirection <= direction from s to p
         enqueue q, s
      end if
   next
 next

这个想法是，它是一个广度优先搜索，所以每次遇到一个新的相邻正方形 s，最好的路径是通过 p。这是 O(N) 我相信。

于 2010-06-30T13:59:29.273 回答
1

知道 pacman 路径是非随机的（即，每个特定级别 0-255、inky、blinky、pinky 和 ​​clyde 将为该级别工作完全相同的路径）。

我会采取这个，然后猜测有一些主路径环绕整个迷宫作为“返回路径”，当吃豆人吃鬼时，眼球物体在它所在的位置等待。

于 2010-06-30T13:08:02.283 回答
1
  1. 在游戏开始之前保存地图中的节点（交叉点）
  2. 当怪物死亡时，获取点（坐标）并在节点列表中找到最近的节点
  3. 计算从那个节点到洞的所有路径
  4. 按长度取最短路径
  5. 添加点和最近节点之间的空间长度
  6. 绘制并在路径上移动

享受！

于 2012-04-11T10:42:06.140 回答
1

pacman 中的幽灵或多或少遵循可预测的模式，首先尝试匹配 X 或 Y，直到达到目标。我一直认为这对于眼睛找到回去的路是完全一样的。

于 2010-06-30T13:12:29.623 回答
1

我的方法有点占用内存（从 Pacman 时代的角度来看），但你只需要计算一次，它适用于任何关卡设计（包括跳跃）。

标记节点一次

首次加载关卡时，将所有怪物巢穴节点标记为 0（表示与巢穴的距离）。继续向外标记连接的节点 1，连接到它们的节点 2，依此类推，直到所有节点都被标记。（注意：即使巢穴有多个入口，这也有效）

我假设您已经拥有代表每个节点的对象以及与其邻居的连接。伪代码可能看起来像这样：

public void fillMap(List<Node> nodes) { // call passing lairNodes
    int i = 0;

    while(nodes.count > 0) {
        // Label with distance from lair
        nodes.labelAll(i++);

        // Find connected unlabelled nodes
        nodes = nodes
            .flatMap(n -> n.neighbours)
            .filter(!n.isDistanceAssigned());
    }
}

从巢穴中填满洪水

眼睛移动到具有最短距离标签的邻居

一旦所有节点都被标记，路由眼睛是微不足道的......只需选择具有最低距离标签的相邻节点（注意：如果多个节点具有相等的距离，则选择哪个并不重要）。伪代码：

public Node moveEyes(final Node current) {
    return current.neighbours.min((n1, n2) -> n1.distance - n2.distance);
}

完全标记的示例

完整地图

于 2017-08-11T16:15:45.170 回答
0

对于我的 PacMan 游戏，我制作了一个有点“ shortest multiple path home”的算法，它适用于我提供的所有迷宫（在我的规则集内）。它也适用于它们的隧道。

加载关卡时，所有path home data in every crossroad内容都是空的（默认），一旦幽灵开始探索迷宫，crossroad path home information每次遇到“新”十字路口或从不同路径再次绊倒他们已知的十字路口时，它们都会不断更新。

于 2015-03-15T12:50:41.213 回答
-2

最初的吃豆人没有使用寻路或花哨的人工智能。它只是让游戏玩家相信它比实际更深入，但实际上它是随机的。正如人工智能游戏/Ian Millington，John Funge 所述。

不知道是真是假，但对我来说很有意义。老实说，我没有看到人们在谈论这些行为。正如他们所说，前任的 Red/Blinky 并没有一直跟随玩家。似乎没有人会故意一直跟踪玩家。他们跟随你的机会在我看来是随机的。而且很容易看到随机行为，特别是当被追逐的机会非常高时，有 4 个敌人和非常有限的转弯选择，在狭小的空间内。至少在最初的实现中，这款游戏非常简单。看看这本书，它在第一章之一。

于 2015-03-12T20:03:43.993 回答