FloodFill - Minesweeper, Explanation needed

Question

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

You should really use a [multidimensional array](http://thenewboston.org/watch.php?cat=31&number=33) 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 '12 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 '12 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 '12 at 21:51
@Lucero I thought a jagged array was something like this: int[][] ints = new int[5][]; — Name, Dec 28 '12 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. http://stackoverflow.com/questions/5313832/multidimensional-arrays-in-java-and-c-sharp — Lucero, Dec 28 '12 at 21:54
@Lucero Well i'll look at that, thanks for the useful information! — Name, Dec 28 '12 at 21:55

score 7 · Accepted Answer · answered Dec 28 '12 at 21:39

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)

answered Dec 28 '12 at 21:39

R.Moeller

3,436
1
17
12

@RMoeller would this mean i have to modify the code for rows and columsn? to get x&y – Exikle Dec 28 '12 at 21:43
@Exikle You could easily do that via a multidimensional array. – Name Dec 28 '12 at 21:44
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 '12 at 21:45
@Lucero no offence, but i don't understand what you just said. I'm a beginner programmer, sorry – Exikle Dec 28 '12 at 21:47
@Exikle I think he means you should have some method used to access an element in your array, by giving an XY coordinate. – Name Dec 28 '12 at 21:51
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 '12 at 21:53
@Lucero so how would i implement this? like what is fillbtn(x,) and whats is isFillable? – Exikle Dec 28 '12 at 23:42
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 '12 at 23:54
@lucero what is btn(x,y) ? when i put it in my code, and modify it a bit to work with my code "The method btn(int, int) is undefined for the type BoardBuild" – Exikle Dec 29 '12 at 00:05
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 '12 at 00:08

score 2 · Answer 2 · edited Jul 07 '21 at 09:02

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.

FloodFill - Minesweeper, Explanation needed

2 Answers2