檢測組沒有遞歸或堆棧/隊列

Question

我正在嘗試用這種算法來檢測網格上類似塊的組。這是一個簡單的遊戲演示，在12×10的網格上隨機丟棄一些片段，並在每個片斷檢查後檢查網格是否有三個或更多相鄰片斷。我正在使用下面的代碼試圖做到這一點沒有洪水填充，遞歸或堆棧/隊列。它似乎幾乎奏效，但會摧毀有時不屬於同一類型的方格，或者留下應該被摧毀的方格。那麼，算法的邏輯錯了，還是執行/編碼錯了？

編輯：我認爲這現在有效。請參閱評論

public void checkMatches(int type) 
{ 
    /* 
    * Step 1: Iterate through each square to see how many of the same type are adjacent to it 
    */ 
    for (int i = 0; i < PIECES_WIDE; i++) 
    { 
     for (int j = 0; j < PIECES_TALL; j++) 
     { 
      if (grid[i][j].getType() == type) // EDITED IN CODE. Make sure current square is of correct type 
      { 
       if (i > 0) // Bounds checking 
        if (grid[i - 1][j].getType() == type) 
         grid[i][j].setAdj(grid[i][j].getAdj() + 1); 
       if (i < PIECES_WIDE - 1) // Bounds checking 
        if (grid[i + 1][j].getType() == type) 
         grid[i][j].setAdj(grid[i][j].getAdj() + 1); 
       if (j > 0) // Bounds checking 
        if (grid[i][j - 1].getType() == type) 
         grid[i][j].setAdj(grid[i][j].getAdj() + 1); 
       if (j < PIECES_TALL - 1) // Bounds checking 
        if (grid[i][j + 1].getType() == type) 
         grid[i][j].setAdj(grid[i][j].getAdj() + 1); 
      } 
     } 
    } 

    /* 
    * Step 2: If there are 2 or more adjacent squares with the same type then it is part of a blob and to be destroyed 
    */ 
    for (int i = 0; i < PIECES_WIDE; i++) 
    { 
     for (int j = 0; j < PIECES_TALL; j++) 
     { 
      if (grid[i][j].getAdj() >= 2) 
       grid[i][j].setDestroy(true); 
     } 
    } 

    /* 
    * Step 3: If there is only 1 adjacent, then check to see if any adjacent squares have been marked to be destroyed (part 
    * of a group). If so, set these to be destroyed as well. 
    */ 
    for (int i = 0; i < PIECES_WIDE; i++) 
    { 
     for (int j = 0; j < PIECES_TALL; j++) 
     { 
      if (grid[i][j].getAdj() == 1) 
      { 
       if (i > 0) // Bounds checking 
        if (grid[i - 1][j].isDestroy() == true) 
        { 
         grid[i][j].setDestroy(true); 
         break; 
        } 
       if (i < PIECES_WIDE - 1) // Bounds checking 
        if (grid[i + 1][j].isDestroy() == true) 
        { 
         grid[i][j].setDestroy(true); 
         break; 
        } 
       if (j > 0) // Bounds checking 
        if (grid[i][j - 1].isDestroy() == true) 
        { 
         grid[i][j].setDestroy(true); 
         break; 
        } 
       if (j < PIECES_TALL - 1) // Bounds checking 
        if (grid[i][j + 1].isDestroy() == true) 
        { 
         grid[i][j].setDestroy(true); 
         break; 
        } 
      } 
     } 
    } 

    /* 
    * Step 4: Iterate through grid and destroy the squares marked for destruction and reset all squares to 0 adjacent and 
    * destroy flag to false 
    */ 
    for (int i = 0; i < PIECES_WIDE; i++) 
    { 
     for (int j = 0; j < PIECES_TALL; j++) 
     { 
      if (grid[i][j].isDestroy()) 
       destroyPiece(grid[i][j]); 

      grid[i][j].setAdj(0); 
      grid[i][j].setDestroy(false); 
     } 
    } 
} 

Answer 1

當您將項目分類到存儲桶時，您可以更快地找到組。您可以使用空間索引，例如kd-tree。