吃豆子:眼睛怎么回到怪物洞?

我发现了许多关于吃豆子的幽灵的AI,但是他们没有一个提到吃豆子被吃掉的鬼魂是怎么回到中央幽灵洞的。

在我的实现中,我实现了一个简单但可怕的解决scheme。 我只是硬编码在每个angular落应该采取的方向。

有没有更好的或最好的解决scheme? 也许是一个通用的不同级别的devise?

其实,我会说你的方法是一个非常好的解决scheme,几乎零运行的时间成本相比,任何types的寻路。

如果您需要将其推广到任意地图,则可以使用任何寻路algorithm(例如,宽度优先search很容易实现),并在运行游戏之前使用它来计算在每个angular落编码的方向。

编辑(2010年8月11日):我刚才提到了一个关于Pacman系统的非常详细的网页: Pac-Man档案 ,由于我在这里已经接受了答案,我觉得我应该更新它。 这篇文章似乎没有涉及到明确地回到怪物屋的行为,但它指出,在吃豆人的直接寻路是一个例子:

  • 继续前进到下一个路口(虽然这实际上是一个特殊情况,“当给出select时,select不涉及逆转方向的方向,如下一步所示);
  • 在十字路口,看看相邻的出口广场,除了你刚刚来的那个;
  • select最接近目标的一个。 如果不止一个球员同样接近球门,按顺序select第一个有效的方向:上,左,下,右。

我已经通过这样的方式解决了通用关卡的问题:在关卡开始之前,我会从怪物洞做一些“洪水填充” 每一个不是墙的迷宫的瓦片都会得到一个数字,表明距离这个孔有多远。 所以当眼睛在68的距离上的时候,他们看看哪个相邻的瓷砖有67的距离; 那就是要走的路

对于更传统的寻路algorithm的替代,你可以看看(适当命名的) Pac-Man气味对象模式 。

你可以在启动时在迷宫周围散发怪物洞的气味,并让眼睛跟随它回家。

一旦气味build立,运行成本是非常低的。


编辑:可悲的维基百科文章已被删除,所以回机救援 …

您应该看一下path查找algorithm,如Dijsktraalgorithm或A *algorithm 。 这是你的问题是:一个graphics/path问题。

任何简单的解决scheme的工作是可维护的,可靠的和performance不错,是一个很好的解决scheme。 这听起来像你已经find了一个很好的解决scheme…

path寻找解决scheme可能比您当前的解决scheme更复杂,因此更可能需要debugging。 它可能也会变慢。

国际海事组织,如果它没有损坏,不要修复它。

编辑

国际海事组织,如果迷宫是固定的,那么你现在的解决scheme好的/优雅的代码。 不要把“好”或“优雅”与“聪明”等同起来。 简单的代码也可以是“好”和“优雅”。

如果您具有可configuration的迷宫级别,那么也许您应该在最初configuration迷宫时进行寻路。 最简单的方法就是让迷宫devise师手工完成。 如果你有一个bazillion迷宫…或者用户可以devise它,我只会打扰自动化。

(另外:如果路线是手工configuration的,迷宫devise师可以通过使用不理想的路线使水平更有趣…)

在原始的吃豆人中,鬼魂通过他的“味道”发现黄丸子,他会在地图上留下一丝痕迹,鬼魂会随机地四处游荡,直到他们发现了这种味道,然后他们只会沿着气味直接导致他们玩家。 每次Pacman移动,“气味值”都会减less1。

现在,扭转整个过程的一个简单方法就是拥有一个“鬼魅金字塔”,它的最高点位于地图的中心位置,然后鬼魂正朝着这个气味的方向移动。

假设你已经有追求帕克曼所需的逻辑为什么不重用? 只要改变目标。 看起来好像比试图用完全相同的逻辑创build一个全新的例程要less得多。

这是一个寻路问题。 有关stream行algorithm,请参阅http://wiki.gamedev.net/index.php/A*

每个广场都有距离中心的距离? 这样,对于每个给定的方块,你可以得到在所有可能的方向上的直接相邻方块的值。 你select最低价格的广场,并移动到该广场。

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

我认为你的解决scheme对于这个问题是正确的,比这个更简单,就是让一个新的版本更“现实”,鬼眼可以穿过墙壁)

这里是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 

这个想法是,这是一个广度优先的search,所以每次遇到一个新的邻接方块,最好的path是通过p。 我相信是O(N)。

我不太了解你如何实现你的游戏,但是,你可以做到以下几点:

  1. 确定眼睛相对于门的位置。 即它是否在上面? 在下面?
  2. 然后把眼睛朝两个方向中的一个方向移动(如向左移动,如果在门的右边,在门的下方),检查是否有墙壁阻止你这样做。
  3. 如果有墙壁妨碍你这样做,那么使它反方向移动(例如,如果眼睛相对于引脚的坐标是正北,目前正在向左移动,但是有一堵墙,向南移动。
  4. 记住每次检查时要保持检查眼睛相对于门的位置,并检查没有纬度坐标的时间。 即它只在大门之上。
  5. 如果有一面墙,只有在门的上方向下移动,那么可以左右移动,继续进行这个数字,直到眼睛在洞穴里。
  6. 我从来没有见过Pacman的死胡同,这个代码不会说死胡同。
  7. 此外,我还包括一个解决scheme,当眼睛在我的伪代码中跨越原点的墙壁之间“摆动”时。

一些伪代码:

  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 

dtb23的build议是在每个angular落随意select一个方向,最终你会发现这个怪物洞听起来非常不合适。

然而,你可以利用其低效率的回归algorithm,通过在游戏难度中引入更多的变化来使游戏变得更有趣。 您可以通过应用上述方法之一(如航点或洪水填充)来做到这一点,但这样做是非确定性的。 所以在每一个angular落,你都可以生成一个随机数来决定是采取最佳的方式还是随机的方向。

随着玩家的进级,你减less了随机方向的可能性。 除了等级速度,幻影速度,吃药暂停(等等)之外,这将在整体难度等级上增加另一个杠杆。 你有更多的时间来放松,而鬼只是无害的眼睛,但随着你的进步,时间会变得越来越短。

这是我能find它的实际工作的最好的来源。

当鬼魂死亡时,他们的眼睛回到原来的位置。 这只是通过将鬼魂的目标拼贴设置到该位置来完成的。 导航使用相同的规则。

这实际上是有道理的。 也许不是世界上最高效的,而是一个非常好的方法,不必担心另一个国家,或者只是改变目标。

附注:我不知道这些pac-man程序员是多么的棒,他们基本上是在一个非常有限的内存的非常小的空间里创build了一个完整的消息系统,这真是太棒了。

简短的回答,不是很好。 :)如果你改变吃豆人的迷宫,眼睛不一定会回来。 一些在周围漂stream的黑客有这个问题。 所以这取决于有一个合作的迷宫。

我会build议鬼魂储存他从洞里吃到吃豆子的path。 所以只要鬼魂死亡,他就可以沿着这个存储的path反向。

知道pacmanpath是非随机的(即,每个特定级别0-255,墨黑,闪烁,小指和克莱德将工作在该级别完全相同的path)。

我会拿这个,然后猜测有几条主path环绕着整个迷宫,作为一个眼球对象所采取的“返回path”,直到pac man吃鬼时。

pacman中的幽灵可能会根据X或Y的匹配程度或多或less的可预测的模式,直到达到目标。 我一直认为,这是完全相同的眼睛寻找回来的路。

  1. 在游戏开始之前,保存地图中的节点(十字路口)
  2. 当怪物去死点(坐标)并find节点列表中最近的节点
  3. 计算从该节点开始到洞的所有path
  4. 采取最短的path的长度
  5. 添加点与最近节点之间的空间长度
  6. 在path上绘制并移动

请享用!

对于我的PacMan游戏,我做了一个有点“ shortest multiple path home ”algorithm,它适用于我提供的任何迷宫(在我的规则集内)。 它也适用于他们的隧道。

当这个级别加载时, path home data in every crossroad所有path home data in every crossroad都是空的(默认),一旦鬼魂开始探索迷宫,他们的crossroad path home information在每次遇到“新”十字路口或者从不同的path再次绊倒在他们已知的十字路口。

我的方法是有点内存密集(从吃豆子时代的angular度来看),但是你只需要计算一次,它适用于任何级别的devise(包括跳跃)。

标签节点一次

当你第一次加载一个关卡时,标记所有的怪物巢穴节点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()); } } 

洪水填充从巢穴

眼睛移动到最低距离标签的邻居

一旦所有的节点被标记,路由眼睛是微不足道的…只select距离最小的标签(注意:如果多个节点距离相等,那么select哪一个都没有关系)。 伪代码:

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

完全标记的例子

完整的地图

原来的pac-man没有使用path寻找或花式AI。 这只是让玩家相信比实际更深入,但实际上是随机的。 正如游戏的人工智能/ Ian Millington,John Funge所说的那样。

不知道这是不是真的,但对我来说很有意义。 老实说,我没有看到人们正在谈论的这些行为。 如前所述,红/眨眼间并不随时关注玩家。 似乎没有人会一直跟踪玩家。 他们会跟随你的机会随机给我看。 看到随机性的行为,特别是在一个小空间里被追逐的几率非常高,有4个敌人,转弯select非常有限的时候,这是非常诱人的。 至less在最初的实施中,游戏非常简单。 看看这本书,这是在第一章之一。