🔒 Locked

Help on minesweeper recursive problem

Started by Mike B Dec 2, 2008 at 11:35 PM 1 replies 1.8k views

Original Post

Dec 2, 2008 at 11:35 PM

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
        }
    }
}

Drigovas

Dec 3, 2008 at 12:17 AM

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]

Mike B

Dec 3, 2008 at 12:09 PM

Very, very helpful. I appreciate it so much. I knew, I knew, I knew i was missing something. It makes much more sense now. Thanks a bunch.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.