Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Jonathan Hobbs 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
1  
Let's continue this discussion in chat –  Jonathan Hobbs Apr 2 '12 at 23:19

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Nice, 11 seconds difference. –  Byte56 Apr 2 '12 at 22:17
    
@Byte56 Brilliant! –  Jonathan Hobbs 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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