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

我不太清楚你是如何执行游戏的，但你可以这么做:

Determine the eyes location relative position to the gate. i.e. Is it left above? Right below? Then move the eyes opposite one of the two directions (such as make it move left if it is right of the gate, and below the gate) and check if there are and walls preventing you from doing so. If there are walls preventing you from doing so then make it move opposite the other direction (for example, if the coordinates of the eyes relative to the pin is right north and it was currently moving left but there is a wall in the way make it move south. Remember to keep checking each time to move to keep checking where the eyes are in relative to the gate and check to see when there is no latitudinal coordinate. i.e. it is only above the gate. In the case it is only above the gate move down if there is a wall, move either left or right and keep doing this number 1 - 4 until the eyes are in the den. I've never seen a dead end in Pacman this code will not account for dead ends. Also, I have included a solution to when the eyes would "wobble" between a wall that spans across the origin in my pseudocode.

一些伪代码:

   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

我的方法有点内存密集型(从《吃豆人》时代的角度来看)，但你只需要计算一次，它适用于任何关卡设计(包括跳跃)。

一次标记节点

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

全标记示例

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

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

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

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

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