1

I'm trying to make a Minesweeper-like game in Java and I've got most of it to work. Something I need help with is FloodFill - http://en.wikipedia.org/wiki/Flood_fill.

Can someone explain how it works? I've looked online but I don't really understand the explanation so I thought it would be easier to ask here.

In my Minesweeper I have:

JButton[] btn = new JButton[100]//buttons being clicked and displaying the values/bombs
int[] mines = new int[100];//int array holding the values for each button.

The grid is a 10x10 grid so say the button you clicked was btn[14],

btn[4]  // north of btn[14](14-10)
btn[24] // south of btn[14](14+10)
btn[13] //  west of btn[14](14-1)
btn[15] //  east of btn[14](14+1)

So back to the question, could someone explain it to me?

EDIT: I changed my code to be 2D so instead of the above one it is now

btn[1][4]//row one, column 4

When the button is clicked, i want it to check a variable called mines[][] which has the values and if the value is equal to 0(around the initial clicked) it changes the BG

btn[x][y].setBackground(Color.GRAY);
6
  • You should really use a multidimensional array to organize your mines/buttons. It will be much easier for you to understand your code. Example: JButton[][] btn = new JButton[10][10]; Instead of JButton[] btn = new JButton[100]; By doing this, you could access your mines by using XY values, instead of the confusing way you're accessing them right now.
    – Name
    Dec 28, 2012 at 21:40
  • @Lucero How would this not compile? In fact I just compiled that exact code and it worked fine. I understand you cannot create a jagged array like this, but he doesn't need one.
    – Name
    Dec 28, 2012 at 21:47
  • @JesusPlusPlus: Your JButton[][] btn = new JButton[10][10] does not create a multidimenational array, but (in this case) 10 nested arrays. This is called a "jagged array".
    – Lucero
    Dec 28, 2012 at 21:51
  • @Lucero I thought a jagged array was something like this: int[][] ints = new int[5][];
    – Name
    Dec 28, 2012 at 21:53
  • @JesusPlusPlus, the [10][10] is just syntactic sugar for a loop creating all the inner arrays of the jagged array. Java has no multidimensional arrays. stackoverflow.com/questions/5313832/…
    – Lucero
    Dec 28, 2012 at 21:54

2 Answers 2

7

Its a recursive algorithm. You start at some start position in a 2D Grid [x,y], then look in all directions and fill them if you can. If (x,y) can't be filled, return.

void floodFill( int x, int y ) {
   if ( btn( x, y ) isFillable ) {
       fillBtn(x,y);
       floodFill( x+1, y );
       floodFill( x-1, y );
       floodFill( x, y-1 );
       floodFill( x, y+1 );
   } else {
       return;
   }
}

(ommited check for boundaries of grid)

10
  • @RMoeller would this mean i have to modify the code for rows and columsn? to get x&y
    – Exikle
    Dec 28, 2012 at 21:43
  • 1
    @Exikle, you should make generic accessors that thake a X and Y coordinate, both for getting and setting values/states in your grid. How the grid stores the data is quite irrelevant then, you can change that by just changing the way the accessors work (the single-dimensional array is fine, but it should remain an implementation detail that only affects the accessors)
    – Lucero
    Dec 28, 2012 at 21:45
  • 1
    @Exikle, exactly what JesusPlusPlus said. Create methods for accessing the data and by doing so you make it irrelevant how the data is actually stored for the rest of the code.
    – Lucero
    Dec 28, 2012 at 21:53
  • 1
    @Exikle: In this sample, btn would be the getter (e,g, it returns an object), and (note that the code above is missing a dot) isFillable would be a field (or method - add parens in that case) on it. fillBtn would then be the setter, which marks it as filled and also sets isFillable to false, so that the floodfill doesn't try and fill it a second time.
    – Lucero
    Dec 28, 2012 at 23:54
  • 1
    @Exikle, its a method that you need to write. It retrieves a JButton (or better, a wrapper object) at the index x, y.
    – Lucero
    Dec 29, 2012 at 0:08
2

I guess you are mainly asking about floodfill. Actually it is a simple and common recursive algorithm. It can solve whatever your data structure is 1D or 2D. For 2D version, @RMoeller has given the answer. For your previous 1D declaration, it is also similar like this:

void floodFill( int pos ) {
   if ( btn( pos ) isFillable ) {
       fillBtn(pos);
       floodFill( pos+1 );
       floodFill( pos-1 );
       floodFill( pos+10 );
       floodFill( pos-10 );
   } else {
       return;
   }
}

One thing you should remember is that floodfill, and almost all recursive algorithms, need to check boundaries. Otherwise you may get into an infinite loop or get a wrong result. In above example (1D version), you should check whether: pos >= 1 && pos <= 100 Similar to 2D version which is to check: x >= 1 && x <= 10 && y>=1 && y <=10

Hope this helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.