特定の範囲内でグリッドセルを見つける

Question

私はグリッドを基にした構造の2Dゲームに取り組んでいます。このグリッドでは、特定の範囲内のあるセルから到達可能なすべてのセルを見つけたいと思っています。移動は垂直方向と水平方向にのみ許可されますが、斜めには許可されません。

これは次の画像で実証されています。緑色の四角形は検索の原点であり、赤色の四角形は交差できない「壁」であり、青色は緑色の四角形を囲む最大のセルです。 10の距離：

私はすでに再帰アルゴリズムの作業の実装を持っているが、それは（範囲10のための140msの範囲15にはほとんど分）めちゃめちゃ遅いので、私はそれを改善するために、いずれかの必要がありますか完全に書き換えます。ここでは、次のとおりです。

//accessible is a vector of points 
//blocked is a 2D array of bools 

void updateAccessible(Point currentPoint, int restRange) { 
    bool existing = false; 
    for (int i = 0; i < accessible.size(); i++) { 
     Point p = accessible[i]; 
     if (p.x == currentPoint.x && p.y == currentPoint.y) { 
      existing = true; 
      break; 
     } 
    } 
    if (!existing) { 
     accessible.push_back(currentPoint); 
    } 

    if (restRange == 0) 
     return; 

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

    for (int i = 0; i < 4; i++) { 
     Point nextPoint{ currentPoint.x + dx[i], currentPoint.y + dy[i] }; 
     if (nextPoint.x > 0 && nextPoint.y < gridWidth && nextPoint.y > 0 && nextPoint.y < gridHeight) { 
      if (!blocked[nextPoint.x][nextPoint.y]) { 
       updateAccessible(nextPoint, restRange - 1); 
      } 
     } 
    } 
} 

既存のアルゴリズムは、経路探索のための*のように、この問題のためにあるのか、どのように地雷を改善するための任意のアイデアを持っていますか？私はどんな提案にも開放的です。

---

編集：MBOは「幅優先検索」を述べた後、私はしても、適切な深さ優先ではなかったし、すべてのセルを複数回訪問した私の最初の試み、と間違っていた知っていました。これは私の2番目のバージョンです。これは息を先に使い、反復的です。それははるかに高速（範囲10のための3msの範囲15のための10ミリ秒、範囲50のための1秒）です。

まだ

void updateAccessible(Point start, int range) { 
    struct Node { 
     int x, y, r; 
    }; 
    std::vector<Node> nodes = std::vector<Node>(); 
    accessible = std::vector<Point>(); 
    nodes.push_back(Node{ start.x,start.y,range }); 
    while (nodes.size() > 0) { 
     Node currentNode = nodes[0]; 
     accessible.push_back(Point{ currentNode.x, currentNode.y }); 
     nodes.erase(nodes.begin()); 

     if (currentNode.r > 0) { 
      int dx[] = { -1, 1, 0, 0 }; 
      int dy[] = { 0, 0, -1, 1 }; 

      for (int i = 0; i < 4; i++) { 
       Node nextNode{ currentNode.x + dx[i],currentNode.y + dy[i], currentNode.r - 1 }; 
       if (nextNode.x > 0 && nextNode.x < gridWidth && nextNode.y > 0 && nextNode.y < gridHeight) { 
        if (!blocked[nextNode.x][nextNode.y]) { 
         bool existing = false; 
         for (int ii = 0; ii < nodes.size(); ii++) { 
          Node n = nodes[ii]; 
          if (n.x == nextNode.x && n.y == nextNode.y) { 
           existing = true; 
           break; 
          } 
         } 
         for (int ii = 0; ii < accessible.size(); ii++) { 
          Point p = accessible[ii]; 
          if (p.x == nextNode.x && p.y == nextNode.y) { 
           existing = true; 
           break; 
          } 
         } 
         if (!existing) { 
          nodes.push_back(nextNode); 
         } 
        } 
       } 
      } 
     } 
    } 
} 

、あなたはそれを改善する方法についての提案があれば、私はそれを聞いてうれしいです。

Answer 1

あなたの実装は、同じセルを何度も何度も繰り返します。

このグリッドでは、奥行き（距離） - 制限BFS（breadth-first-search）が必要です。これを実装するには、セルマークの配列を追加するだけです。一度訪問したセルにマークを付けると、それ以上のことはしないでください。