Floodfill using an ArrayList not working

Question

I'm wanting to use Floodfill to uncover neighbouring cells in a Minesweeper game. I'm new to Floodfill and perhaps I'm misunderstanding it. It never stops when it reaches a cell that isn't surrounded by a mine.

Here is the code for the uncovering method:

public static void uncoverSurroundings(int x, int y, JButton[][] buttons)
{
    queue.add(new Point(x,y));
    int currentPnt = queue.size() - 1;
    Point p = queue.get(currentPnt);
    try
    {
        if (mineLayout[x][y+1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x][y-1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x+1][y+1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x-1][y-1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x-1][y].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x+1][y].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x-1][y+1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x+1][y-1].equals("Mine"))
            queue.remove(p);        
    }
    catch (NullPointerException|ArrayIndexOutOfBoundsException e)
    {
    }
    try
    {
        if (currentPnt + 1 == queue.size())
        {
        Point r = queue.get(currentPnt);
        queue.remove(currentPnt);
        buttons[r.x][r.y].setEnabled(false);
        queue.add(new Point (x, y+1));
        queue.add(new Point (x, y-1));
        queue.add(new Point (x+1, y+1));
        queue.add(new Point (x-1, y-1));
        queue.add(new Point (x-1, y));
        queue.add(new Point (x+1, y));
        queue.add(new Point (x-1, y+1));
        queue.add(new Point (x+1, y-1));
        }
    }
    catch (NullPointerException|ArrayIndexOutOfBoundsException e)
    {
    }
    if (!queue.isEmpty())
        index = queue.size() - 1;
        Point nextPnt = queue.get(index);
        uncoverSurroundings(nextPnt.x, nextPnt.y, buttons);
    }
}

Answer 1

There are a number of problems with your code that I can see.

Firstly, at the bottom of your code, you fetch the last point in the queue and recursively call your uncoverSurroundings method with this last point in the queue. This adds the point to the queue. If the point then gets removed from the queue using one of your queue.remove(p) calls, you then reach the bottom of uncoverSurroundings without having changed the size of the queue. You then call uncoverSurroundings again with the same point and the same-size queue, which ends up calling uncoverSurroundings again with the same point and the same-size queue, which ends up calling uncoverSurroundings again with the same point and the same-size queue ....

You need to remove the point from the queue at the end of uncoverSurroundings.

The second problem you have is that you appear to have no way of recording whether a square has been uncovered. Clearly, if you've uncovered a square, there's no point in trying to uncover it again. You need to keep track of what squares have been uncovered, and if uncoverSurroundings is called on a square that has already been uncovered, it should do nothing.

After fixing these two problems, your code will no longer cause a stack overflow, but it still won't do what you want it to. In fact, it is possible for your uncoverSurroundings method to call itself on a square that contains a mine. The reason why it does this is due to the following block of code:

    try
    {
        if (mineLayout[x][y+1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x][y-1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x+1][y+1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x-1][y-1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x-1][y].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x+1][y].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x-1][y+1].equals("Mine"))
            queue.remove(p);
        else if (mineLayout[x+1][y-1].equals("Mine"))
            queue.remove(p);        
    }
    catch (NullPointerException|ArrayIndexOutOfBoundsException e)
    {
    }

If, say, square (x, y-1) is off the grid (due to y being zero, for instance), but square (x-1, y+1) contains a mine, then your point p will not get removed from the queue because mineLayout[x][y-1] will cause an ArrayIndexOutOfBoundsException to be thrown and the remaining checks on mineLayout will be skipped.

It's bad practice to catch exceptions such as NullPointerException or ArrayIndexOutOfBoundsException. If one of these exceptions is thrown, that is normally because you have a bug in your code. Expecting such exceptions to be thrown and catching them when they are thrown is sloppy coding. However, to be fair to you, I suspect you were trying to avoid having to check your coordinate values were in-range for each of your eight mineLayout calls. It would be far better in this situation to have a method for checking whether a given square contains a mine, and you can put the logic for checking whether the x and y values are on the grid in there. For example, this method could look something like the following:

    private static boolean isMineAt(int x, int y) {
        return 0 <= x && x < width && 0 <= y && y < height && mineLayout[x][y].equals("Mine");
    }

(I'm assuming width and height contain the width and height of the grid here.)

That way you can replace all of your mineLayout checks with the following:

        if (isMineAt(x, y+1))
            queue.remove(p);
        else if (isMineAt(x, y-1))
            queue.remove(p);
        // and so on...

You might also want to do something similar with the eight calls to queue.add(new Point(...));. You could write a method that checks to see if the x and y values are on the grid before adding the point to the queue. You could also check whether the point you wish to add to the queue is already in the queue, and only add it if it isn't. I'll leave that as an exercise for you.