如何为 pacman 实现 BFS 算法？

Question

我正在使用 DFS 、 BFS 、 UCS 和 A* 等搜索算法在迷宫世界中为吃豆人实现 AI。 DFS 的实现非常简单，但是对于 BFS 我搞混了。我不知道如何实现它，因为我不明白 pacman 怎么可能从一个位置开始并将其邻居的位置排入队列并检查它们并通过它们。：/ 谁能帮我？ !

Answer 1

在 BFS 中，您遍历算法并发现到每个节点的最短路径。

为了以后得到这个路径，需要存储parent:V->V，也就是说，需要"remember"从哪个单元格到当前单元格。这很容易通过存储 dictionary/map 来完成，其中键是一个单元格，值是您用来发现键的单元格。

在伪代码中：

BFS(source, target):
   queue = empty new queue
   queue.add(source)
   parent= new dictionary
   parent.add(source, None)
   while (queue.empty() == false): 
      curr = queue.dequeue()
      if (curr == target)
          return getPath(dict, curr)
      for each neighbor u of curr:
          if u is not a key in parent:
             parent[u] = curr
             queue.add(u)

上面的BFS填充parent字典，路径由下面的getPath()函数返回，基本上是遍历字典，直到找到"root"（也就是原始出处）节点）。

getPath(dict, target):
   sol = [] //empty list
   curr = target
   while curr != None:
         sol.addFirst(curr)
         curr = dict.get(curr)

Answer 2

如果你正在寻找最短路径，你必须记住已经访问过的位置，因为最短路径只会使用它的所有位置一次。

这里是算法的简化版本：

Q := an empty queue of positions
V := an empty set of already visited positions
Q.pushBack( initial position )
While Q is not empty:
    current_position := Q.popFront()
    If current_position == goal_position:
        Return "You won!"
    If current_position Is Not In V:
        Q.pushBack( NeighboursOf(current_position) )

我用了一个很简单的状态，只持有位置。但是如果你想要一个完整的算法，你的状态必须包含位置加上到这个位置的路径。而且当你比较两个状态时，只是比较位置，而不是路径。

如何为 pacman 实现 BFS 算法？

How to implement BFS algorithm for pacman?

algorithm

artificial-intelligence

maze

pacman

breadth-first-search