# Floodfill algorithm for GO

The floodfill algorithm is used in the bucket tool in MS paint and photoshop, but it can also be used for GO and minesweeper.

http://en.wikipedia.org/wiki/Flood_fill

In go you can capture groups of stones, this website portrays it with two stones. http://www.connectedglobe.com/mindy/cap6.html

This is my floodfill method in Java, it is not capturing a group of stones and I have no idea why because to me it makes sense.

``````public void floodfill(int turn, int col, int row){
for(int a = col; a<19; a++){
for(int b = row; b<19; b++){
if(turn == black){
if(stones[col][row] == white){
stones[col][row] = 0;
floodfill(black, col-1, row);
floodfill(black, col+1, row);
floodfill(black, col, row-1);
floodfill(black, col, row+1);
}
}
}
}
}
``````

It searches up, down, left, right for all the stones on the board. If the stones are white it captures them by making them 0, which represents empty.

-
Have you tried it in a debugger? – XiaoChuan Yu Apr 2 '12 at 22:04
It's just supposed to check in the four directions, up, down, left, right. Not in that order but those 4 regions of the stone. – user1048606 Apr 2 '12 at 22:07
If it's not capturing a group of stones, what is it doing? – doppelgreener Apr 2 '12 at 22:37
It's not doing anything, not working at all... It's supposed to be able to replicate capturing groups of stones just like in GO the board game. Link: connectedglobe.com/mindy/cap6.html I've also tried your implementation and it still does not work. – user1048606 Apr 2 '12 at 22:43
– doppelgreener Apr 2 '12 at 23:19

It seems like you are intending to do this. The flood fill shouldn't have `for` loops in it.

``````public void floodfill(int turn, int col, int row){
if(turn == black){
if(stones[col][row] == white){
stones[col][row] = 0;
floodfill(black, col-1, row);
floodfill(black, col+1, row);
floodfill(black, col, row-1);
floodfill(black, col, row+1);
}
}
}

public void floodfillAll(int turn){
for(int a = 0; a<19; a++){
for(int b = 0; b<19; b++){
floodfill(turn,a,b);
}
}
}
``````

Which is kind of silly. Since the flood fill should fill everything anyway. Just use the first part.

-

You didn't say in what way it's not working (is it crashing, or taking forever?). You ought to do that.

However, it strikes me as immediately absurd that your recursive flood fill has a loop. You could either write a loop to fill everything (which wouldn't be a flood fill), or you could write a recursive flood fill:

``````public void floodfill(int turn, int col, int row){
if(turn == white) return;
// also add: if 'col' and 'row' aren't in the valid range, return
// otherwise you'll get index out of bounds errors because you will
// eventually call to flood column -1.
if(stones[col][row] == black) return;
stones[col][row] = 0; // does black = 0? Saying black would be more readable
floodfill(black, col-1, row);
floodfill(black, col+1, row);
floodfill(black, col, row-1);
floodfill(black, col, row+1);
}
``````

If you want to loop through every tile, you don't need a recursive flood fill. If you want to do a recursive flood fill, you don't need to loop through every tile.

Every time your old method was called it was spanning through every tile above it in the x/y direction, then calling a tile before it, which would then call every tile after it and a tile before it. I imagine your 'flood fill' would never have ended.

-
Nice, 11 seconds difference. – Byte56 Apr 2 '12 at 22:17
@Byte56 Brilliant! – doppelgreener Apr 2 '12 at 22:23
Sorry I meant to say that it's not capturing a group of stones. – user1048606 Apr 2 '12 at 22:31