Bubble Shooter 游戏中的 Flood-Fill 算法

Question

我在泡泡射击游戏工作。当我用相同颜色的射击泡泡击中泡泡时，我必须删除泡泡，然后我尝试使用洪水填充算法搜索我应该删除哪个泡泡。当射手泡泡碰到另一个泡泡时出现错误：

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

我对 Flood-Fill 算法的实现：

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;
        }
    }
}

气泡从右到左自上而下。

你知道我做错了什么吗？

Answer 1

您在递归时没有将当前数组单元格置为空，这导致无限递归。您应该在执行 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 是一个布尔数组，可让您跟踪已访问过的单元格（初始化为 false）。

希望对您有所帮助:)

Answer 2

由于您的 floodFill 是如何实现的，您将一遍又一遍地重新访问以前的位置，直到出现 Stack Overflow（因为您的递归深度如此之高）。

例如考虑位置x = 1, y = 1是红色，位置x = 2, y = 1是红色，所有其他位置都是其他颜色。

我们在 x = 1, y = 1 上打电话给 floodFill。

然后在 x = 2, y = 1 上调用 floodFill，x = 2, y = 1 又在 x = 1, y = 1 上调用它。

只要确保不要重新访问相同的节点即可。

Answer 3

因为您将 tab 中的位置仅标记为 null 在您递归调用该方法之后，这意味着它永远不会到达它所在的阶段实际上将一个地方标记为空。它会匹配其中一个条件，然后再次调用自己，然后它会匹配其中一个条件，并再次调用自己。它永远不会达到任何可以阻止它的地步。

最好把当前位置tab的c的值作为参数传递给方法，这样在之前可以标记为null 您继续搜索。例如：

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); } } ... }

Bubble Shooter 游戏中的 Flood-Fill 算法

Flood-Fill algorithm in BubbleShooter game

java

stack-overflow

algorithm