CODEWITHSUNDEEP
javaflood-fill
Exikle
Exikle

Reputation: 1165

Recursive Floodfill Overflowing

public void floodFill(int x, int y) {
    if (x >= 0 && x <= 9 && y >= 0 && y <= 9) {
        if (mines[x][y] == 0) {
            btn[x][y].setBackground(Color.GRAY);
            floodFill(x - 1, y);
            // floodFill(x + 1, y);
            floodFill(x, y - 1);
            // floodFill(x, y + 1);
        } else {
            return;
        }
    }
}

This is the floodFill code I'm using for a minesweeper-like game I'm making. However, as you can see 2 parts are commented out. As soon as I un-comment it and run the program.

Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError
at sun.awt.NullComponentPeer.setBackground(Unknown Source)
at java.awt.Component.setBackground(Unknown Source)
at javax.swing.JComponent.setBackground(Unknown Source)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:95)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:99)
at Minesweeper.BoardBuild.floodFill(BoardBuild.java:98)

I'm not sure why this is happening, and I'm not sure how to fix it. Any help is appreciated.

EDIT:

The answer that Fls'Zen came up with in chat, just in case anyone else ever has this problem

public void floodFill(int x, int y) {
    if (x >= 0 && x <= 9 && y >= 0 && y <= 9) {
        if (mines[x][y] == 0 && btn[x][y].getBackground() != Color.GRAY) {
            btn[x][y].setBackground(Color.GRAY);
            floodFill(x - 1, y);
            floodFill(x + 1, y);
            floodFill(x, y - 1);
            floodFill(x, y + 1);
        } else {
            return;
        }
    }
}

Upvotes: 1

Views: 1729

Answers (2)

Fls&#39;Zen
Fls&#39;Zen

Reputation: 4664

When those lines are uncommented, you call floodFill for both x - 1 and x + 1. Consider what happens when you call floodFill for x - 1. It also calls floodFill for x + 1 which is the x value that called floodFill. You have floodFill calling itself for the same two x values, the original x value, and the original x - 1.

If you're going to use recursion, you should pick one 'direction' (+ or -) and stick with it. Otherwise, you'll need to add something to track which coordinates have been evaluated.

Edit: The following code will avoid recursion when a cell has already been processed by the algorithm. It accomplishes this by checking the background color of the current coordinates. If the background is already gray, then it assumes it has already processed the coordinates and won't process them again. 

if (mines[x][y] == 0 && btn[x][y].getBackground() != Color.GRAY) {
    btn[x][y].setBackground(Color.GRAY);
    floodFill(x - 1, y);
    floodFill(x + 1, y);
    floodFill(x, y - 1);
    floodFill(x, y + 1);
} else {
    return;
}

Upvotes: 4

Tharwen
Tharwen

Reputation: 3107

It looks like you aren't recording which squares you've already checked, so it's infinitely looping over the entire board.

Upvotes: 0

Related Questions