c++ - 使用 BFS 在网格中重建路径时出错

问题描述

我面临的问题如下：我有一个基于我在 NxM 网格中使用的 BFS 搜索算法的函数，该函数的任务是从一组可能的 Directions = {Up, Down, Left , Right} （没有对角线移动！）玩家必须移动到的位置，因此在每个“回合/帧”中，有一种游戏项目（例如，在这种特定情况下，火箭筒）是离物品更近。为了解决这个问题，我创建了一个 Map 类，vector <vector <Cell> >其中 vector 来自标准库，而 Cell 是网格的组成部分，并对其中一个 NxM 单元中的内容提供了一些咨询方法（如果有建筑物，敌人、火箭筒等）

因此，为了实现一个解决方案，我制作了一个 struct 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 链接][1] 要阅读此图像，在顶部和左侧有访问矩阵的每个单元格的坐标，带有绿色字体的单元格，是已经访问过的，它们存储路径的下一个单元/顶点，带有 (-1,-1) 的那些是 BFS 算法没有访问过的，因此它们没有任何先前的节点并且是白色的。很好！它似乎工作，至少访问矩阵。

我的问题是当我调试图形/网格的边/方向向量时，这是我在图像示例中使用的：

  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

标签： c++searchgame-physicsbreadth-first-searchpath-finding

c++ - 使用 BFS 在网格中重建路径时出错

问题描述

解决方案

推荐阅读