Sign in to follow this  

Help on minesweeper recursive problem

This topic is 3299 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I started making a minesweeper game a few days ago and figured I'd use recursion to do the "Flip all spots that are zero thing if ya know what I mean". For one, I'm not that great with vectors and I'm actually using a vector of vectors of objects. My first question, is there a better way to do this? Such as accessing the vector maybe. This was the first way I thought of to keep the vector from accessing parts that don't exist and I don't think it's the best. (It's also too slow because of all the conditionals and stuff). For one, is there something that may come in handy that I'm not aware of? And two, maybe post suggestions on how I can improve it. There's also a problem where it goes out of bounds sometimes and actually reenters and comes back in and continues recurring. I don't understand that, and another problem: I originally had the top left, top right, etc recurring again instead of just flipping. But I didn't think it was necessary because it would reach that square eventually anyway (i.e for top-right, go up, go right), but i did need to do something there to show the number if it was a corner of the zero cluster. When I just do as I did, it stops recurring when it's still unfinished. I thought I covered all the bases with this but I'd like a new set of eyes to take a look at it. I'd super appreciate ANY help, I usually don't ask for help because I hate being a burden but if there's a better way to work on this, I'd rather not spend time going in circles. Thanks.
void board::FlipAllZeros(int row, int column)
{
    ShowBoard(buffer, images); //just temp to illustrate whats happening
    if(tileset[row][column].isFlip()) //first base case to prevent redoing work
        return;
    tileset[row][column].Flip(); 
    
    if(tileset[row][column].GetValue() == 0){ //second base case, zero is 0 bombs around square
        if(column > 0){
            if(!tileset[row][column-1].isFlip())
                FlipAllZeros(row, column-1); //recur on top
            if(row > 0)
                tileset[row-1][column-1].Flip(); //top left
            }
        if(column < tileset[0].size()-1){
            if(!tileset[row][column+1].isFlip())
                FlipAllZeros(row, column+1); //recur on bottom
            if(row < tileset.size()-1)
                tileset[row+1][column+1].Flip(); //bottom right
            }
        if(row > 0){
            if(!tileset[row-1][column].isFlip())
                FlipAllZeros(row-1, column); // recur on left
            if(column < tileset[0].size()-1)
                tileset[row-1][column+1].Flip(); //bottom left
            }
        if(row < tileset.size() - 1){
            if(!tileset[row+1][column].isFlip())
                FlipAllZeros(row+1, column); //recur on right
            if(column > 0)
                tileset[row+1][column-1].Flip(); //top right
        }
    }
}

Share this post


Link to post
Share on other sites
Effectively what you are looking for is Flood fill, which actually has a surprisingly decent wikipedia article, with a special case for bound checking. The problem you are describing with things falling off the grid and reappearing elsewhere is likely an issue with your bound checking. For conciseness, here is a quick overview of a reasonable algorithm to do this:
void FlipAllZeros(Board board, int x, int y){
if(y < 0 || y >= board.height) // off the board
return;
if(x < 0 || x >= board.width)
return;
if(board.tile(x,y).isFlipped())
return; // the base case you identified
board.tile(x,y).flip();
if(board.tile(x,y).number == 0)
{
FlipAllZeros(board,x+1,y);
FlipAllZeros(board,x-1,y);
FlipAllZeros(board,x,y+1);
FlipAllZeros(board,x,y-1);
...
}
}
It isn't quite what you've got there, in that it doesn't use vectors or your notation, but it is likely pretty clear what is going on. Here is a quick 'find-and-replace' version that uses vectors.
void FlipAllZeros(vector<vector<tile>> board, int row, int column){
if(column < 0 || column >= board.size()) // off the board
return;
if(row < 0 || row >= board[column].size())
return;
if(board[row][column].isFlipped())
return; // the base case you identified
board[row][column].flip();
if(board[row][column].GetValue() == 0)
{
FlipAllZeros(board,row+1,column);
FlipAllZeros(board,row-1,column);
FlipAllZeros(board,row,column+1);
FlipAllZeros(board,row,column-1);
...
}
}
Also, I don't have time to grind through and figure it out, but did 'minesweeper' traditionally expose diagonal zeros? [not that you have to do exactly what they did... just curious]

*edit* fixed a blunder i made, and...

I just remembered that Minesweeper exposes tiles next to zero, which this doesn't... so how about this.
FlipAllZeros(vector<vector<tile>> board, int row, int column, bool lastWasZero /* initially true */){
if(column < 0 || column >= board.size()) // off the board
return;
if(row < 0 || row >= board[column].size())
return;
if(board[row][column].isFlipped())
return; // the base case you identified
board[row][column].flip();
if(lastWasZero)
{
FlipAllZeros(board,row+1,column,board[row][column].GetValue() == 0);
FlipAllZeros(board,row-1,column,board[row][column].GetValue() == 0);
FlipAllZeros(board,row,column+1,board[row][column].GetValue() == 0);
FlipAllZeros(board,row,column-1,board[row][column].GetValue() == 0);
...
}
}


[Edited by - Drigovas on December 3, 2008 12:17:15 AM]

Share this post


Link to post
Share on other sites

This topic is 3299 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this