Public Group

# Help on minesweeper recursive problem

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

## 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 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 on other sites
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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633663
• Total Posts
3013236
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!