XNA Creators Club Online
Forums Hi, Visitor Sign In
community forums
XNA Community Forums » General » Game Algorithms » Minesweeper uncovering blocks..
Page 1 of 1 (8 items)
Sort Posts: Previous Next

Minesweeper uncovering blocks..

Last post 11/21/2009 3:04 AM by Steve Walker. 7 replies.
  • 11/20/2009 1:59 AM

    Minesweeper uncovering blocks..

    Reply Quote
    I am attempting to make a minesweeper game but I'm not sure how to get past this. When you uncover a block with 0 mines around it, the region of uncovered blocks grows until it hits a block that has mines around it, or the edge of the grid. That's my best shot at explaining it, so I'm hoping you've played minesweeper before. I need an algorithm to do this, and would very much appreciate it if someone could help me. Thanks!
  • 11/20/2009 2:15 AM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote
    I would maintain a list of blocks that still need to be cleared. On each iteration, if the current block has no mines surrounding it, add all surrounding blocks to the list that have not been added yet. Something like this:

    void ClearBlock(Point currentBlock) 
    { 
       var blocksToClear = new List<Point>(); 
       blocksToClear.Add(currentBlock); 
     
       SetBlockAsVisited(currentBlock); 
     
       for (int i = 0; i < blocksToClear.Count; ++i) 
       { 
          if (IsMine(currentBlock)) 
          { 
             // BOOM! 
          } 
          else if (!IsAdjacentToMine(currentBlock)) 
          { 
             for (int y = currentBlock.Y - 1; y <= currentBlock.Y + 1; ++y) 
             { 
                for (int x = currentBlock.X - 1; x <= currentBlock.X + 1; ++x) 
                { 
                   Point nextBlock = new Point(x, y); 
                   if (nextBlock != currentBlock && 
                       !IsBlockVisited(nextBlock)) 
                   { 
                      blocksToClear.Add(nextBlock); 
                   } 
                } 
             } 
          } 
       } 
    } 
     

    Edit: You could also use recursion, if you wanted. The implementation is a bit easier, but there is the potential for performance issues, depending on the size of your maps. Also, the iterative approach I've shown you here is adaptable to occur over multiple frames, in case you want to use animations when clearing a block.
    Previously known as "Rainault".
    Twitter - me, Jade Vault Games
    Announcing ASCII Quest, a Roguelike under development for Xbox LIVE Indie Games
  • 11/20/2009 2:58 AM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote
    Sorry, I suck at explaining things. Haha

    What I'm having trouble with is actually finding which squares to uncover. It's not all the squares on the board, you click one, and the ones around that square get uncovered, and then the ones around those squares get uncovered, and it goes on like this until each square off of a square etc. hits a square with a number in it and then it stops. I guess it's like a hierarchy. Is there any way to do what I'm trying to do?
  • 11/20/2009 3:02 AM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote
    Look up the flood fill algorithm.  That is what you want to use.  You will flood fill the blank areas and use numbered squares as your boundry cases.
    Sidus Bellum -- About me
  • 11/20/2009 3:20 AM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote
    Egad:
    It's not all the squares on the board, you click one, and the ones around that square get uncovered, and then the ones around those squares get uncovered, and it goes on like this until each square off of a square etc. hits a square with a number in it and then it stops. I guess it's like a hierarchy. Is there any way to do what I'm trying to do?

    But that is what my algorithm does; it only touches all squares that are connected to the square that the player clicked. The call to IsAdjacentToMine (which you would have to implement) takes care of that.
    Previously known as "Rainault".
    Twitter - me, Jade Vault Games
    Announcing ASCII Quest, a Roguelike under development for Xbox LIVE Indie Games
  • 11/20/2009 10:09 PM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote

    I would do a simple indirect recursive method, here is an example I made for my minesweeper clone (in Java)

         public void cascade (int x, int y)  
          {  
              for (int a = x - 1; a < x + 2; a++)  
               {  
                   for (int b = y - 1; b < y + 2; b++)  
                    {     
                        if (a > -1 && a < rows && b > -1 && b < columns && !squares[a][b].getClicked() && !squares[a][b].getFlagged())  
                         {  
                             guess (a, b);  
                         }  
                    }  
               }  
          }  

    I had a method called guess which uncovers the blocks. The board was represented as a 2d array. columns and rows are constants that represent the number of rows and columns the board has. The guess method will call this cascade method again if the square has no adjacent mines.
    Basically you want to uncover every square that is adjacent to the one clicked as long as it is not flagged or already clicked. And if the square you are trying to uncover has no adjacent mines, call the method for that new square.
  • 11/21/2009 12:08 AM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote
    I agree that the flood fill would be your best bet

    http://en.wikipedia.org/wiki/Flood_fill
    My Blawg - http://devrygsp.blogspot.com/
  • 11/21/2009 3:04 AM In reply to

    Re: Minesweeper uncovering blocks..

    Reply Quote
    both the provided example methods implement a simplistic form of the flood fill algorithm
Page 1 of 1 (8 items) Previous Next