对于Pacman女士来说，BFS或DFS是一种有效的搜索算法吗

Question

我正在为Ms Pacman AI实现搜索算法。我认为从一些基本搜索(如BFS或DFS(开始是个好主意。我刚刚实现了一个BFS，但当我运行代码时，pacman女士撞到了墙上。我想知道，我的BFS代码有什么可以改进的吗？还是还不够？

public MOVE BFS(Game game){
EnumMap<Constants.GHOST,MOVE> ghostMove = new EnumMap<>(Constants.GHOST.class);
MOVE bestMove = MOVE.NEUTRAL;
Queue<Game> q = new LinkedList<>();
q.add(game.copy());
while(!q.isEmpty()){
Game current = q.peek();
q.remove();
for (MOVE move : current.getPossibleMoves (current.getPacmanCurrentNodeIndex())) {
Game neighbor = game.copy();
neighbor.advanceGame(move, ghostMove);
q.add(neighbor);
if ((current.getNumberOfActivePills() == 0) && (current.getNumberOfActivePowerPills() == 0)) {
return move;
}
}
}
return bestMove;
}

Answer 1

我将假设您打算使用BFS以最有效的方式解决Pacman女士的问题，即最短路径。我认为BFS存在一些问题，但如果不访问代码的其余部分，很难确切知道每个函数调用都在做什么。代码中可能存在的一个错误是，您从未将bestMove设置为除MOVE.NUMTRAL之外的任何其他值，这可能解释了撞到墙上的原因。通常，在BFS中，您希望找到到达特定目标的最短路径，并希望通过跟踪访问空间来避免回溯。在将BFS应用于游戏之前，使用它来解决迷宫或其他更简单的事情可能会有助于你真正感到舒适。

如果我用bfs实现类似的东西，我会用bfs找到最近药丸的路径并返回该路径。然后，我会用这条路一步一步地让Pacman女士服用避孕药。一旦她吃了药，我就会重复这个过程，直到一粒都没有了。我不确定bfs是否是Pacman的最佳算法，但它应该有效，只是可能不会导致AI成为最佳玩家。同样为了防止玩家陷入困境，我只会记录一条通往药丸的路径的访问空间，然后用每条新路径重置它。

听起来是个有趣的项目，祝你好运！