Programming Forums > Script Programming > Python

UnKnown X · Jun 11th, 2006, 5:19 AM

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:

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?

mrynit · Jun 11th, 2006, 5:29 AM

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.

UnKnown X · Jun 11th, 2006, 5:34 AM

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

Edit: Nah, it works fine. Thanks.

lectricpharaoh · Jun 11th, 2006, 9:42 AM

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.

UnKnown X · Jun 11th, 2006, 10:29 AM

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

(Toggle Plain Text)

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.

titaniumdecoy · Jun 11th, 2006, 2:00 PM

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?

(Toggle Plain Text)

fill(row+1,col)
fill(row,col+1)
fill(row,col-1)
fill(row-1,col)

DaWei · Jun 11th, 2006, 3:30 PM

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.

UnKnown X · Jun 11th, 2006, 4:56 PM

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?

(Toggle Plain Text)

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:

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.

DaWei · Jun 11th, 2006, 7:47 PM

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.

Jun 11th, 2006, 5:19 AM	#1
UnKnown X Hobbyist Programmer Join Date: Dec 2005 Location: Sandvika, Norway Posts: 114 Rep Power: 0	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: 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?

Jun 11th, 2006, 5:29 AM	#2
mrynit Hobbyist Programmer Join Date: Mar 2006 Location: WA, USA Posts: 332 Rep Power: 3	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 dont know much about programming but i try to help

Jun 11th, 2006, 5:34 AM	#3
UnKnown X Hobbyist Programmer Join Date: Dec 2005 Location: Sandvika, Norway Posts: 114 Rep Power: 0	I just thought of that, yeah, but isn't it extremely inefficient? Edit: Nah, it works fine. Thanks. Last edited by UnKnown X; Jun 11th, 2006 at 5:56 AM.

Jun 11th, 2006, 9:42 AM	#4
lectricpharaoh Caffeinated Neural Net Join Date: Jun 2005 Location: Dry west coast of Canada Posts: 1,005 Rep Power: 5	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. __________________ And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot. - Vaarsuvius, Order of the Stick

Jun 11th, 2006, 10:29 AM	#5
UnKnown X Hobbyist Programmer Join Date: Dec 2005 Location: Sandvika, Norway Posts: 114 Rep Power: 0	I've already got the most basic algorithm. Pseudocode: (Toggle Plain Text) 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) 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.

Jun 11th, 2006, 2:00 PM	#6
titaniumdecoy Expert Programmer Join Date: Nov 2005 Posts: 839 Rep Power: 3	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? (Toggle Plain Text) fill(row+1,col) fill(row,col+1) fill(row,col-1) fill(row-1,col) fill(row+1,col) fill(row,col+1) fill(row,col-1) fill(row-1,col)

Jun 11th, 2006, 3:30 PM	#7
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	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. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Jun 11th, 2006, 7:47 PM	#9
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	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. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Script Programming > Python

Algorithm for Mineless Areas in Minesweeper?