Programming Forums - Algorithm for Mineless Areas in Minesweeper?

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Python (http://www.programmingforums.org/forum43.html)

- - Algorithm for Mineless Areas in Minesweeper? (http://www.programmingforums.org/showthread.php?t=10283)

Algorithm for Mineless Areas in Minesweeper?

I've programmed a rudimentary console-based Minesweeper game, but I have a problem. If the player picks an area without a mine and without any nearby mines, the game is supposed to fill the entire area with empty space so the player won't have to do it.

Like so: http://img138.imageshack.us/img138/4561/mineless0vw.png

Problem is, I have no idea how to implement something like this. I'm sure it involves recursion, at which, to be honest, I'm not good at all.

Any ideas? :confused:

look around in a circle using the point where the player selected as the orign. then expanding.

how did you figure out how to place the numbers next to the mines? that might help.

I just thought of that, yeah, but isn't it extremely inefficient?

Edit: Nah, it works fine. Thanks.

I'm not 100% certain what you mean (never touched Minesweeper), but if I read you right, you're basically looking for a fill algorithm. Imagine each square is a pixel, and you want to set all squares of type X to type Y, much like a fill algorithm sets all pixels of color X to color Y. If you google for fill algorithms, you'll probably get a whole bunch of ideas for implementing this.

I've already got the most basic algorithm. Pseudocode:

def fill(row,col):

    global board

    if row < 0 or row > max or col < 0 or col > max:

        return

    if board[row][col] != unused:

        return

    if mine in proximity:

        board[row][col] = make_number()

        return

    board[row][col] = empty

    fill(row+1,col+1)

    fill(row+1,col)

    fill(row+1,col-1)

    fill(row,col+1)

    fill(row,col-1)

    fill(row-1,col+1)

    fill(row-1,col)

    fill(row-1,col-1)

I'll have a look on Google for better alternatives, though.

I'm not sure about this, but wouldn't a Minesweeper game only check squares that are touching (not diagonal to) each square in this instance?

fill(row+1,col)

fill(row,col+1)

fill(row,col-1)

fill(row-1,col)

No, minesweeper checks all adjacent squares. I once wrote a version called 'sharks'. It added difficulty by causing the sharks (mines) to have a tendency to move toward a square that had just been cleared. If, however, the shark density exceeded a certain threshold, there was a probability that sharks would snack on a neighbor until the density dropped below another threshold. More fun to program than play, I must say.

Quote:

Originally Posted by titaniumdecoy

I'm not sure about this, but wouldn't a Minesweeper game only check squares that are touching (not diagonal to) each square in this instance?

fill(row+1,col)

fill(row,col+1)

fill(row,col-1)

fill(row-1,col)

Nah, DaWei is right. At least Windows' version does all the adjacent squares:
http://img207.imageshack.us/img207/6586/msadj3ov.png

Quote:

Originally Posted by DaWei

I once wrote a version called 'sharks'. It added difficulty by causing the sharks (mines) to have a tendency to move toward a square that had just been cleared. If, however, the shark density exceeded a certain threshold, there was a probability that sharks would snack on a neighbor until the density dropped below another threshold. More fun to program than play, I must say.

Sounds quite interesting! Do you still have the source code for that? I might learn something from it, and besides, I'm quite interested in how it plays. If you're willing to share it, of course.

I would be perfectly willing, so I'll look. It was about 3 years ago; the probability of it having survived a system change during that interval isn't really high. The thing that irked me about it was I used MFC and I never found a way to get a right-click event in MFC -- I had to go outside to do it.