对于我的《吃豆人》游戏，我创造了一个“最短多条回家路径”算法，它适用于我所提供的任何迷宫(在我的规则集内)。它也适用于隧道。

当关卡被加载时，每个十字路口的所有归途数据都是空的(默认)，一旦幽灵开始探索迷宫，它们每次遇到“新的”十字路口或从不同的路径再次遇到已知的十字路口时，它们的归途路径信息就会不断更新。

《吃豆人》中的幽灵遵循或多或少可预测的模式，即尝试先匹配X或Y，直到实现目标。我一直认为这对于眼睛寻找回去的路是完全一样的。

下面是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)。

知道吃豆人的路径是非随机的(例如，每个特定的关卡0-255,inky, blinky, pinky和clyde将在该关卡中工作完全相同的路径)。

我会选择这个，然后猜测有一些主路径围绕整个 迷宫是眼球物体的“返回路径”，当吃豆人吃掉幽灵时，它就在那里。

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

然而，你可以利用它低效的“回家”算法，通过在游戏难度中引入更多变化来让游戏变得更有趣。你可以通过应用上面的方法，比如你的路径点或洪水填充来做到这一点，但这样做是非确定性的。所以在每个角落，你都可以生成一个随机数来决定是走最优路线，还是随机方向。

随着玩家不断推进关卡，你将减少玩家选择随机方向的可能性。这将在关卡速度，幽灵速度，吃药丸暂停等之外为整体难度关卡添加另一个杠杆。你有更多的时间放松，而鬼魂只是无害的眼睛，但随着你的进步，时间会越来越短。

在最初的《吃豆人》中，幽灵会通过“气味”在地图上留下痕迹，鬼魂会随机四处游荡，直到它们找到气味，然后它们会沿着气味路径直接找到玩家。吃豆人每移动一次，“气味值”就会减少1。

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