BubbleShooter遊戲中的Flood-Fill算法

我在泡沫射擊遊戲工作。當我用相同顏色的射手泡泡擊中泡泡時，我必須刪除泡泡，並嘗試搜索使用泡泡填充算法刪除哪個泡泡。當射手泡沫觸碰另一個泡沫我有一個錯誤：BubbleShooter遊戲中的Flood-Fill算法

Exception in thread "Thread-1" java.lang.StackOverflowError

我實現的洪水填充算法：

public void floodFill(int disX, int disY){ 
    //up 
    if(tab[disX][disY - 1] != null){ 
     if (tab[disX][disY - 1].c == tab[disX][disY].c){ 

      floodFill(disX, disY - 1); 
      tab[disX][disY - 1] = null; 
     } 
    } 
    //right 
    if(tab[disX + 1][disY] != null){ 
     if (tab[disX + 1][disY].c == tab[disX][disY].c){ 
      floodFill(disX + 1, disY); 
      tab[disX + 1][disY] = null; 
     } 
    } 
    //left 
    if(tab[disX - 1][disY] != null){ 
     if (tab[disX - 1][disY].c == tab[disX][disY].c){ 
      floodFill(disX - 1, disY); 
      tab[disX - 1][disY] = null; 
     } 
    } 
    //down 
    if(tab[disX][disY +1] != null){ 
     if (tab[disX][disY +1].c == tab[disX][disY].c){ 
      floodFill(disX, disY + 1); 
      tab[disX][disY + 1] = null; 
     } 
    } 
}

泡泡觸摸自己上下左右。

你知道我做錯了嗎？

來源

2015-06-05 santiag

您正在遞歸而不將當前數組單元格設置爲null，從而導致無限遞歸。你應該標記當前小區做floodFill(X, Y);

之前訪問你也更好地與另一個數組markVisited跟蹤所在小區，而不是使當前單元格null

下面是正確的代碼：

markVisited[disX][disY] = true; // mark the current node as visited 
if(tab[disX][disY - 1] != null && !markedVisited[disX][disY-1]){ // test if target cell is notvisited 
    if (tab[disX][disY - 1].c == tab[disX][disY].c){ 

     floodFill(disX, disY - 1); 

    } 
}

markedVisited其中markedVisited是一個布爾數組，讓您可以跟蹤已經訪問過的單元格（init爲false）。

希望它能幫助:)

來源

2015-06-05 14:09:47

因爲你floodFill是如何實現的，你一遍一遍重溫以前的位置，直到你得到一個堆棧溢出（因爲你的遞歸深度是如此之高）。

例如，考慮位置x = 1, y = 1是紅色，位置x = 2, y = 1是紅色，所有其他位置是其他顏色。

我們致電floodFillx = 1, y = 1。

然後在x = 2, y = 1上調用floodFill，然後在x = 1, y = 1上調用它。

只要確保不要重新訪問相同的節點。

來源

2015-06-05 14:10:16 Clark

因爲你是標誌着tab的地方，你是遞歸調用方法只後空，這意味着它永遠不會得到它實際上標誌着一個地方作爲空階段。它將匹配其中一個條件，然後再次調用自己，然後它將匹配其中一個條件，然後再次調用它自己。它從來沒有達到有任何阻止它的地步。

這將是更好地在當前位置作爲參數的方法，從tab傳遞的c值，這樣就可以將其標記爲空，你在搜索中繼續之前。例如：

public void floodFill(int disX, int disY, int currentColor){ 
    //up 
    if(tab[disX][disY - 1] != null){ 
     if (tab[disX][disY - 1].c == currentColor){ 
      tab[disX][disY - 1] = null; 
      floodFill(disX, disY - 1, currentColor); 
     } 
    } 
    ... 
}

來源

2015-06-05 14:11:01 RealSkeptic

BubbleShooter遊戲中的Flood-Fill算法

回答

相關問題