c++ - PacMan 广度优先搜索的实现

Question

我目前正在开发一个 C++ 项目来制作 PacMan 克隆。基本上我已经完成了游戏所做的几乎所有事情。但是我还没有想出如何实现广度优先搜索以便鬼魂追逐pacman。在过去的几天里，我阅读了很多关于 BFS 的内容。我知道它是什么以及它的作用。我也知道我必须为此目的使用队列。但是，我仍然无法在我的游戏中实际实现这个算法。我有一个 36*28 block 的二维网格。但我真的不确定如何在我的 xy 坐标系统中实现它，将什么推送到队列以及如何操作相邻的图 block 。我被困在这一点上。我不是在要求实际代码。我只需要一个关于 BFS 实际实现的清晰和简单的解释，以及在这个 2d 游戏网格中处理 BFS 时要记住的事情。您的解释将非常有帮助。谢谢。

Answer 1

我假设你想在幽灵每次移动时都进行 BFS。你可以做的是从 PacMan 开始 BFS，直到他找到所有幽灵。请注意，您实际上并不需要幽灵将要走的完整路线，您只需要下一步。在进行 BFS 时，您可以为每个单元存储 PacMan 到该单元的距离。 BFS 完成后，所有幽灵都可以查看相邻的单元格并选择数字最小的单元格。请注意，您应该使用较大的数字初始化所有单元格。

要进行 BFS，您可以使用一些技巧，例如将 (x, y) 坐标映射到一个数字。这个号码可以放在您的队列中。请注意，在将某些内容放入队列之前，您应该检查墙。当你从队列中取出一些东西时，运行一个长度为 4(相邻单元格的数量)的 for 循环。

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void do_bfs() {
    std::queue<int> queue;
    // initialize grid
    // add starting position of pacman to queue

    while(!queue.empty()) {
        // remove and access first element
        cur_place = queue.front(); queue.pop(); 
        map_to_coordinate(cur_x, cur_y, cur_place);
        cur_distance = grid[cur_x][cur_y];
        for (int i = 0; i < 4; i++) {
            if (cur_x + dx[i] >= 0 && /* more checks */) {
                queue.push_back(map_to_number(cur_x + dx[i], cur_y + dy[i]));
                grid[cur_x + dx[i]][cur_y + dy[i]] = cur_distance + 1;
            }
        }
    }
    // now grid is filled, so now you should find out for each ghost how to move
}

作为读者的练习，我在阐述我的观点时尽量保持开放。