使用 BFS 在网格中重建路径时出错
Error reconstructing path in a grid using BFS
我面临的问题如下：
我有一个基于 BFS 搜索算法的函数，我在 NxM 网格中使用该函数，该函数的任务是 return 从一组可能的方向中选择以下方向 = {Up, Down, Left , Right} (没有对角线移动！），玩家必须移动到该位置，以便在每个“回合/帧”中有一种游戏物品（例如，在这种特定情况下，火箭筒）更接近该物品。
为了解决这个问题，我创建了一个由 vector <vector <Cell> > 组成的 Map class，其中 vector 来自标准库，Cell 是网格的组成部分，并且有一些关于其中一个内容的咨询方法NxM 个单元格（如果有建筑物、敌人、火箭筒等）
因此，为了实现解决方案，我制作了一个结构体 TrackingBFS 来重建 BFS 搜索的路径：
struct TrackingBFS {
pair <int,int> anterior;
bool visited;
};
这是 BFS 搜索实现：
//Pre: origen is a valid position on the grid where the player is
//Post:Returns a pair of bool and a direction to the closest bazooka. If we have access to a bazooka, then we will return a pair (true,Dir) where Dir is a direction to take to be closer to the bazooka else a pair (false, Dir) where dir is just the same direction as origen.
pair <bool,Dir> direction_to_closest_gun (const Pos& origen) {
//R = board_rows() C = board_cols()
//m = mapa
//sr,sc = origin positions
int sr = origen.i;
int sc = origen.j;
//Variables para mantener tracking de los pasos cogidos
queue <int> rq; //Queue of x-row coordinates
queue <int> cq; //Queue of y-row coordinates
int move_count = 0; //Number of steps
int nodes_left_in_layer = 1; //How many nodes we need to de-queue before doing a step
int nodes_in_next_layer = 0; //How many nodes we add to the expansio of the BFS so we can upgrade nodes_left_in_layer in the next iteration
bool arma_mejor_encontrada = false;
//Visited is a MxN matrix of TrackingBFS that for every i,j stores the following information:
//If we visited the cell at position visited [i][j], then the TrackingBFS struct will be visited = true and last_node = (k,l) where k and l are the components of the LAST cell on the grid we visited in the BFS search.
//Else if we didn't visited the cell at [i][j], the TrackingBFS struct will be visited = true and last_node (-1,-1).
TrackingBFS aux;
aux.last_node = make_pair(-1,-1);
aux.visited = false;
//We create a Matrix of TrackingBFS named visited of NxM filled with the unvisited cells
vector < vector <TrackingBFS> > visited (board_rows(), vector <TrackingBFS> (board_cols(),aux));
//--------------------------------SOLVE---------------------------------
rq.push(sr);
cq.push(sc);
visited[sr][sc].visited = true;
visited[sr][sc].last_node = make_pair(sr,sc);
int xfound;
int yfound;
while (!rq.empty()) {
int r = rq.front();
int c = cq.front();
rq.pop();
cq.pop();
if (mapa[r][c].weapon == Bazooka) {
arma_mejor_encontrada = true;
xfound = r;
yfound = c;
break;
}
//Explore neighbours
Pos p (r,c);
for (Dir d : dirs) {
Pos searching = p + d;
int rr = searching.i;
int cc = searching.j;
//If the position we are searching is out of range or it's been visited before or there is a obstacle then continue
if (!pos_ok(searching) or visited[rr][cc].visited or mapa[rr][cc].type == Building or mapa[rr][cc].resistance != -1 or mapa[rr][cc].id != -1) {
//NADA
}
//Else we add the visited node to the queue, and fill the information on visited[rr][cc] with the node we are coming and mark it as visited
else {
rq.push(rr);
cq.push(cc);
visited[rr][cc].visited = true;
visited[rr][cc].last_node = make_pair (r,c);
nodes_in_next_layer++;
}
}
nodes_left_in_layer--;
if (nodes_left_in_layer == 0) {
nodes_left_in_layer = nodes_in_next_layer;
nodes_in_next_layer = 0;
move_count++;
}
}
//If we found the Bazooka
if (arma_mejor_encontrada) {
//Return the pair (true,next direction of the player at position (sr,sc) to approach the bazooka)
return make_pair(arma_mejor_encontrada, reconstruir_camino(visited,xfound,yfound,sr,sc));
}
else {
//If there is no bazooka we return (false,Up (this second component is meaningless))
return make_pair(arma_mejor_encontrada, Up);
}
}
reconstruir_camino（英文recosntruct_path）实现：
//This function is made to reconstruct the path from where we found de bazooka (x,y) to where our player is (ox,oy), whe are only interested in the next position of because this is run each frame, so we are constantly refreshing the state of the map.
Dir reconstruir_camino(const vector < vector <TrackingBFS> >& visited, const int& x, const int& y, const int& ox, const int& oy) {
//In v we save the pair of coordinates of our path, this was done only for debuging and in debug_matriz_tracking(visited) is also only for debuging
vector <pair<int,int>> path;
debug_matriz_tracking(visited);
//
int i = visited[x][y].last_node.first;
int j = visited[x][y].last_node.second;
while (not (i == ox and j == oy)) { //While the next node is not iqual as the original node we started de search (The one where our player is)
path.push_back(make_pair(i,j)); //Just for debuging
i = visited[i][j].last_node.first;
j = visited[i][j].last_node.second;
}
//So now in path we have the start and end nodes of every edge on the path
int siguiente_x = path.back().first;
int siguiente_y = path.back().second;
debug_camino(path);
return direccion_contiguos(ox,oy,siguiente_x,siguiente_y);
}
和direccion_contiguos（连续方向/英文相对方向）实现：
//Returns the RELATIVE direction to go if we want to go from (ox, oy) to (dx, dy) being these two contiguous positions, that is, (dx, dy) is in Up, Down, Left or Right with respect to (ox, oy) IT WORKS FINE, NOTHING WRONG WITH THIS DON'T TOUCH
Dir direccion_contiguos (const int& ox, const int& oy, const int& dx, const int& dy) {
Pos o (ox,oy);
Pos d (dx,dy);
if (o + Up == d) {
return Up;
}
else if (o + Down == d){
return Down;
}
else if (o + Left == d) {
return Left;
}
else if (o + Right == d) {
return Right;
}
return Down;
}
所以现在在 visited 中，我们有重建路径的信息，事实上我调试了它（我知道它有点乱，对不起），以视觉方式所以这就是我在 origen = 中为玩家得到的(7,10) 和火箭筒在位置 = (4,11):
[Imgur link 用于重建从原点到火箭筒路径的矩阵的视觉表示][1]
读这张图，左上角是被访问矩阵的每个单元格的坐标，绿色字体的是已经被访问过的，它们存储路径的下一个cell/vertex，带有 (-1,-1) 的是 BFS 算法尚未访问过的节点，因此它们没有任何先前的节点并且为白色。
太赞了！它似乎有效，至少访问矩阵。
我的问题是当我调试 graph/grid 的 edges/directions 向量时，这是我在图像示例中使用的：
void debug_camino(const vector <pair<int,int>>& v) {
cerr << "----------------------CAMINO-------------------- DEBUG_CAMINO" << endl;
for (long unsigned int i = 0; i < v.size(); ++i) {
cerr << "(" << v[i].first << "," << v[i].second << "),";
}
cerr << endl;
}
当我执行程序时，这是我用 debug_camino() 得到的路径：
如果您看到附加的图像，您会发现这几乎就是路径，但还不完全是。
(4,12),(4,13),(4,14),(3,15),(3,16),(4,16),(5,16 ),(6,16),(7,15),(7,14),(7,13),(7,12),(7,11)
这些加粗的不是真实的（即使是有效的，因为它们是对角线移动）路径的重建，我真的不知道为什么会这样，但它让我的玩家不遵循正确的路径，我想要修复错误，我有点绝望，因为我真的不知道错误在哪里，我已经尝试了好几天:(！我希望有人能帮我解决这个问题。感谢您阅读所有这些内容，如果代码在某些部分是西班牙语的，或者如果它不是那么可读的话。
[1]: https://i.stack.imgur.com/vZ2Go.png
好吧，我实际上设法修复了这个错误，我覆盖了 i 变量，所以这是导致错误的原因。
//This function is made to reconstruct the path from where we found de bazooka (x,y) to where our player is (ox,oy), whe are only interested in the next position of because this is run each frame, so we are constantly refreshing the state of the map.
Dir reconstruir_camino(const vector < vector <TrackingBFS> >& visited, const int& x, const int& y, const int& ox, const int& oy) {
//In v we save the pair of coordinates of our path, this was done only for debuging and in debug_matriz_tracking(visited) is also only for debuging
vector <pair<int,int>> path;
debug_matriz_tracking(visited);
//
int i = visited[x][y].last_node.first;
int j = visited[x][y].last_node.second;
while (not (i == ox and j == oy)) { //While the next node is not iqual as the original node we started de search (The one where our player is)
path.push_back(make_pair(i,j)); //Just for debuging
**i** = visited[i][j].last_node.first;
j = visited[**i**][j].last_node.second;
}
//So now in path we have the start and end nodes of every edge on the path
int siguiente_x = path.back().first;
int siguiente_y = path.back().second;
debug_camino(path);
return direccion_contiguos(ox,oy,siguiente_x,siguiente_y);
}
已经修复
我面临的问题如下：
我有一个基于 BFS 搜索算法的函数，我在 NxM 网格中使用该函数，该函数的任务是 return 从一组可能的方向中选择以下方向 = {Up, Down, Left , Right} (没有对角线移动！），玩家必须移动到该位置，以便在每个“回合/帧”中有一种游戏物品（例如，在这种特定情况下，火箭筒）更接近该物品。
为了解决这个问题，我创建了一个由 vector <vector <Cell> > 组成的 Map class，其中 vector 来自标准库，Cell 是网格的组成部分，并且有一些关于其中一个内容的咨询方法NxM 个单元格（如果有建筑物、敌人、火箭筒等）
因此，为了实现解决方案，我制作了一个结构体 TrackingBFS 来重建 BFS 搜索的路径：
struct TrackingBFS {
pair <int,int> anterior;
bool visited;
};
这是 BFS 搜索实现：
//Pre: origen is a valid position on the grid where the player is
//Post:Returns a pair of bool and a direction to the closest bazooka. If we have access to a bazooka, then we will return a pair (true,Dir) where Dir is a direction to take to be closer to the bazooka else a pair (false, Dir) where dir is just the same direction as origen.
pair <bool,Dir> direction_to_closest_gun (const Pos& origen) {
//R = board_rows() C = board_cols()
//m = mapa
//sr,sc = origin positions
int sr = origen.i;
int sc = origen.j;
//Variables para mantener tracking de los pasos cogidos
queue <int> rq; //Queue of x-row coordinates
queue <int> cq; //Queue of y-row coordinates
int move_count = 0; //Number of steps
int nodes_left_in_layer = 1; //How many nodes we need to de-queue before doing a step
int nodes_in_next_layer = 0; //How many nodes we add to the expansio of the BFS so we can upgrade nodes_left_in_layer in the next iteration
bool arma_mejor_encontrada = false;
//Visited is a MxN matrix of TrackingBFS that for every i,j stores the following information:
//If we visited the cell at position visited [i][j], then the TrackingBFS struct will be visited = true and last_node = (k,l) where k and l are the components of the LAST cell on the grid we visited in the BFS search.
//Else if we didn't visited the cell at [i][j], the TrackingBFS struct will be visited = true and last_node (-1,-1).
TrackingBFS aux;
aux.last_node = make_pair(-1,-1);
aux.visited = false;
//We create a Matrix of TrackingBFS named visited of NxM filled with the unvisited cells
vector < vector <TrackingBFS> > visited (board_rows(), vector <TrackingBFS> (board_cols(),aux));
//--------------------------------SOLVE---------------------------------
rq.push(sr);
cq.push(sc);
visited[sr][sc].visited = true;
visited[sr][sc].last_node = make_pair(sr,sc);
int xfound;
int yfound;
while (!rq.empty()) {
int r = rq.front();
int c = cq.front();
rq.pop();
cq.pop();
if (mapa[r][c].weapon == Bazooka) {
arma_mejor_encontrada = true;
xfound = r;
yfound = c;
break;
}
//Explore neighbours
Pos p (r,c);
for (Dir d : dirs) {
Pos searching = p + d;
int rr = searching.i;
int cc = searching.j;
//If the position we are searching is out of range or it's been visited before or there is a obstacle then continue
if (!pos_ok(searching) or visited[rr][cc].visited or mapa[rr][cc].type == Building or mapa[rr][cc].resistance != -1 or mapa[rr][cc].id != -1) {
//NADA
}
//Else we add the visited node to the queue, and fill the information on visited[rr][cc] with the node we are coming and mark it as visited
else {
rq.push(rr);
cq.push(cc);
visited[rr][cc].visited = true;
visited[rr][cc].last_node = make_pair (r,c);
nodes_in_next_layer++;
}
}
nodes_left_in_layer--;
if (nodes_left_in_layer == 0) {
nodes_left_in_layer = nodes_in_next_layer;
nodes_in_next_layer = 0;
move_count++;
}
}
//If we found the Bazooka
if (arma_mejor_encontrada) {
//Return the pair (true,next direction of the player at position (sr,sc) to approach the bazooka)
return make_pair(arma_mejor_encontrada, reconstruir_camino(visited,xfound,yfound,sr,sc));
}
else {
//If there is no bazooka we return (false,Up (this second component is meaningless))
return make_pair(arma_mejor_encontrada, Up);
}
}
reconstruir_camino（英文recosntruct_path）实现：
//This function is made to reconstruct the path from where we found de bazooka (x,y) to where our player is (ox,oy), whe are only interested in the next position of because this is run each frame, so we are constantly refreshing the state of the map.
Dir reconstruir_camino(const vector < vector <TrackingBFS> >& visited, const int& x, const int& y, const int& ox, const int& oy) {
//In v we save the pair of coordinates of our path, this was done only for debuging and in debug_matriz_tracking(visited) is also only for debuging
vector <pair<int,int>> path;
debug_matriz_tracking(visited);
//
int i = visited[x][y].last_node.first;
int j = visited[x][y].last_node.second;
while (not (i == ox and j == oy)) { //While the next node is not iqual as the original node we started de search (The one where our player is)
path.push_back(make_pair(i,j)); //Just for debuging
i = visited[i][j].last_node.first;
j = visited[i][j].last_node.second;
}
//So now in path we have the start and end nodes of every edge on the path
int siguiente_x = path.back().first;
int siguiente_y = path.back().second;
debug_camino(path);
return direccion_contiguos(ox,oy,siguiente_x,siguiente_y);
}
和direccion_contiguos（连续方向/英文相对方向）实现：
//Returns the RELATIVE direction to go if we want to go from (ox, oy) to (dx, dy) being these two contiguous positions, that is, (dx, dy) is in Up, Down, Left or Right with respect to (ox, oy) IT WORKS FINE, NOTHING WRONG WITH THIS DON'T TOUCH
Dir direccion_contiguos (const int& ox, const int& oy, const int& dx, const int& dy) {
Pos o (ox,oy);
Pos d (dx,dy);
if (o + Up == d) {
return Up;
}
else if (o + Down == d){
return Down;
}
else if (o + Left == d) {
return Left;
}
else if (o + Right == d) {
return Right;
}
return Down;
}
所以现在在 visited 中，我们有重建路径的信息，事实上我调试了它（我知道它有点乱，对不起），以视觉方式所以这就是我在 origen = 中为玩家得到的(7,10) 和火箭筒在位置 = (4,11):
[Imgur link 用于重建从原点到火箭筒路径的矩阵的视觉表示][1] 读这张图，左上角是被访问矩阵的每个单元格的坐标，绿色字体的是已经被访问过的，它们存储路径的下一个cell/vertex，带有 (-1,-1) 的是 BFS 算法尚未访问过的节点，因此它们没有任何先前的节点并且为白色。 太赞了！它似乎有效，至少访问矩阵。
我的问题是当我调试 graph/grid 的 edges/directions 向量时，这是我在图像示例中使用的：
void debug_camino(const vector <pair<int,int>>& v) {
cerr << "----------------------CAMINO-------------------- DEBUG_CAMINO" << endl;
for (long unsigned int i = 0; i < v.size(); ++i) {
cerr << "(" << v[i].first << "," << v[i].second << "),";
}
cerr << endl;
}
当我执行程序时，这是我用 debug_camino() 得到的路径： 如果您看到附加的图像，您会发现这几乎就是路径，但还不完全是。 (4,12),(4,13),(4,14),(3,15),(3,16),(4,16),(5,16 ),(6,16),(7,15),(7,14),(7,13),(7,12),(7,11)
这些加粗的不是真实的（即使是有效的，因为它们是对角线移动）路径的重建，我真的不知道为什么会这样，但它让我的玩家不遵循正确的路径，我想要修复错误，我有点绝望，因为我真的不知道错误在哪里，我已经尝试了好几天:(！我希望有人能帮我解决这个问题。感谢您阅读所有这些内容，如果代码在某些部分是西班牙语的，或者如果它不是那么可读的话。 [1]: https://i.stack.imgur.com/vZ2Go.png
好吧，我实际上设法修复了这个错误，我覆盖了 i 变量，所以这是导致错误的原因。
//This function is made to reconstruct the path from where we found de bazooka (x,y) to where our player is (ox,oy), whe are only interested in the next position of because this is run each frame, so we are constantly refreshing the state of the map.
Dir reconstruir_camino(const vector < vector <TrackingBFS> >& visited, const int& x, const int& y, const int& ox, const int& oy) {
//In v we save the pair of coordinates of our path, this was done only for debuging and in debug_matriz_tracking(visited) is also only for debuging
vector <pair<int,int>> path;
debug_matriz_tracking(visited);
//
int i = visited[x][y].last_node.first;
int j = visited[x][y].last_node.second;
while (not (i == ox and j == oy)) { //While the next node is not iqual as the original node we started de search (The one where our player is)
path.push_back(make_pair(i,j)); //Just for debuging
**i** = visited[i][j].last_node.first;
j = visited[**i**][j].last_node.second;
}
//So now in path we have the start and end nodes of every edge on the path
int siguiente_x = path.back().first;
int siguiente_y = path.back().second;
debug_camino(path);
return direccion_contiguos(ox,oy,siguiente_x,siguiente_y);
}
已经修复