CODEWITHSUNDEEP
javaalgorithmstack-overflow
santiag
santiag

Reputation: 21

Flood-Fill algorithm in BubbleShooter game

I working at bubble shooter game. I must delete bubbles when I hit bubble by shooter bubble with this same color and I try search which bubble I should delete with flood-fill algorithm. When shooter bubble touch another bubble I have an error:

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

My implementation of Flood-Fill algorithm:

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

Bubbles touching themselves up down right and left.

Do You know what I made wrong?

Upvotes: 0

Views: 1235

Answers (3)

RealSkeptic
RealSkeptic

Reputation: 34628

Because you are marking the place in tab as null only after you are calling the method recursively, it means that it will never get to the stage that it actually marks a place as null. It will match one of the conditions, and then call itself again, and then it will match one of the conditions, and call itself again. It never gets to a point where there is anything that will stop it.

It would be better to pass the value of c from tab at the current place as a parameter to the method, so that you can mark it as null before you continue in your search. E.g:

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

Upvotes: 1

yahya el fakir
yahya el fakir

Reputation: 562

you are recursing without putting the current array cell to null, which leed to an infinite recursion. you should mark the current cell as visited before doing floodFill(X, Y);

Also you better track the visited cell with another array markVisited, rather than making the current cell to null

Here is the correct code : 

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

    }
}

Where markedVisited is a boolean array that let you keep track of the cells you already visited (init to false).

Hope it helped :)

Upvotes: 0

Clark
Clark

Reputation: 1365

Because of how your floodFill is implemented, you are revisiting previous locations over and over again, until you get a Stack Overflow (because your recursive depth is so high).

For example consider position x = 1, y = 1 is the color red, and the position x = 2, y = 1 is the color red, and all other positions are some other color.

We call floodFill on x = 1, y = 1.

This then calls floodFill on x = 2, y = 1, which in turn calls it on x = 1, y = 1.

Just make sure to not revisit the same nodes.

Upvotes: 0

Related Questions