BFS/DFS适用于Ms Pacman AI吗？现有BFS实现代码可如何优化？

核心代码bug（这是撞墙的首要原因） #

你写的BFS代码存在3个致命逻辑错误，和BFS算法本身无关：

• 邻居节点生成错误：循环内扩展子节点时，你调用的是game.copy()，这里的game是方法入参的初始状态，而非当前出队的current状态。这导致你所有扩展的节点都是从初始位置走一步的状态，完全没有沿着BFS的路径逐层搜索，路径逻辑完全失效。
• 终止条件逻辑错误：你在扩展子节点时判断的是current节点是否吃完所有豆子，但返回的是当前循环的子节点移动方向，状态和移动方向完全不匹配；且没有校验子节点状态的合法性，也没有标记已访问的状态，会导致节点重复入队、无限循环，甚至出现无效移动。
• 幽灵行为处理为空：你调用advanceGame时传入的是空的ghostMove集合，相当于搜索阶段完全假设幽灵静止，实际运行时幽灵会按规则移动，你搜索出来的路径本身就没有考虑幽灵的位置，自然会出现撞鬼、撞墙的问题。

相关错误代码片段的修复示例：

public MOVE BFS(Game game){
    EnumMap<Constants.GHOST,MOVE> ghostMove = new EnumMap<>(Constants.GHOST.class);
    // 新增已访问集合，避免重复入队
    Set<Game> visited = new HashSet<>();
    Queue<Game> q = new LinkedList<>();
    Game root = game.copy();
    q.add(root);
    visited.add(root);
    while(!q.isEmpty()){
        Game current = q.poll();
        // 先判断当前节点是不是目标状态
        if ((current.getNumberOfActivePills() == 0) && (current.getNumberOfActivePowerPills() == 0)) {
            // 这里可以额外加逻辑回溯路径拿到第一步移动，这里简化处理
            return current.getLastMove();
        }
        for (MOVE move : current.getPossibleMoves(current.getPacmanCurrentNodeIndex())) {
            // 修复：从current节点复制，而非初始game
            Game neighbor = current.copy();
            // 补充幽灵移动逻辑，比如用当前游戏的幽灵预期移动填充ghostMove
            fillGhostMove(ghostMove, current);
            neighbor.advanceGame(move, ghostMove);
            if(!visited.contains(neighbor)){
                visited.add(neighbor);
                q.add(neighbor);
            }
        }
    }
    return MOVE.NEUTRAL;
}

BFS算法的适配性说明 #

BFS本身完全可以适配Ms Pacman的短路径规划场景，比如局部找最近的豆子、躲避近距离的幽灵，效率足够高。
但如果要做全局通关的全状态搜索，BFS会面临状态爆炸问题：游戏的全局状态包含豆子状态、幽灵位置、幽灵冷却时间、吃豆人位置等多个维度，状态总量会随着搜索深度指数级上升，很难搜到吃完所有豆子的最终状态。实际使用时建议给BFS加10~20步的深度限制，每次搜索选择当前深度内收益最高的移动方向即可。

内容的提问来源于stack exchange，提问作者dynamo