Computer Science Canada

Minesweeper help
Author:  cavetroll [ Wed Jul 25, 2007 11:26 pm ]
Post subject:  Minesweeper help
I have a working minesweeper game except for the one feature that is in the windows version. You know when you click a place that has empty spaces all around it shows all the empty places around it. How do I do that, I have researched pathfinding algorithms and have been thinking about ways to modify them. Any source is greatly appreciated.
Author:  Saad [ Thu Jul 26, 2007 2:53 am ]
Post subject:  RE:Minesweeper help
It isnt pathfinding. The algorithm is that for the current cell, if the number of mines around it is not 0 then halt and show the current block, If the value of the current block is > 0 then show the current cell, and for every cell around it call the same algorithm.
Author:  McKenzie [ Thu Jul 26, 2007 7:16 am ]
Post subject:  Re: Minesweeper help
Try looking at the "flood-fill" algorithm, it is a very similar problem.
Author:  cavetroll [ Thu Jul 26, 2007 11:38 am ]
Post subject:  Re: Minesweeper help
Thanks for the quick responses, and yes you were right I wasn't looking for pathfinding but I didn't know the proper term for what I was looking for. I looked up flood-fill algorithms and found how to do it. Again thanks for the response.
Author:  cavetroll [ Thu Jul 26, 2007 12:17 pm ]
Post subject:  Re: Minesweeper help
Sorry I thought I had it but now I can't get the code to work, I am not sure why I tried to do it using recursion(http://en.wikipedia.org/wiki/Flood_fill) based on the first pseudo-code example. Here is the code,

code:
proc floodfill (nodex : int, nodey : int)
    if squares (nodex, nodey, typ) not= 2 then
        return
    else
        squares (nodex, nodey, state) := 2
        for decreasing i : 1 .. -1
            for ii : -1 .. 1
                if nodex - i > 0 and nodex - i < 19 and nodey - ii > 0 and nodey - ii < 19 then
                    if i not= 0 and ii not= 0 then
                        floodfill (nodex - i, nodey - ii)
                    end if
                end if
            end for
        end for
        return
    end if
end floodfill
but it isn't working. Any Ideas?
Author:  Aziz [ Thu Jul 26, 2007 12:23 pm ]
Post subject:  RE:Minesweeper help
There's a recursive and iterative method. I can post more help later on, when I'm not so swamped at work.
Author:  Saad [ Thu Jul 26, 2007 5:21 pm ]
Post subject:  RE:Minesweeper help
Cant diagnose based on the code you have, What error are you getting?
Author:  cavetroll [ Thu Jul 26, 2007 7:08 pm ]
Post subject:  Re: Minesweeper help
No error messages the code just doesn't do what it is intended to do. Have you read the earlier posts? They explain what the code is supposed to do but it doesn't work. I am just trying to figure out where it went wrong.
Author:  CodeMonkey2000 [ Thu Jul 26, 2007 8:35 pm ]
Post subject:  RE:Minesweeper help
How have you implemented your minesweeper game?
Author:  cavetroll [ Fri Jul 27, 2007 12:34 am ]
Post subject:  Re: Minesweeper help
I can post the code if you want but it is very messy right now so I'd rather not, but basically I have an array(squares(1..18,1..18,1..3)) which stores the data(count, type, state) for every square. When the square is click the state value is changed to 2 if it is left-clicked and 3 if it is right-clicked. Then I draw accordingly. The code given is what I want to run if the square clicked has a count of 0. Post if this doesn't help.
Author:  Saad [ Fri Jul 27, 2007 4:05 am ]
Post subject:  RE:Minesweeper help
That alogorithm seems right, only problem I can see is that every square will have set to 2. Since it only checks if that square is 2 because of this all squares will end up as 2.
You want to check the amount of mines around the current cell aswell. If its not= 0 then return
Author:  Aziz [ Fri Jul 27, 2007 7:50 am ]
Post subject:  RE:Minesweeper help
I can see a major problem in your logic.

Why does your array have three dimensions? Array indices should represent position, not value. Then value is store in a position of an array. So it does not make sense to have a 3D array for Minesweeper. If a user clicks a square, it changes the state, which changes the position, not the value.

What you should do is have a 2D array to store the state. I'm assume the array values already hold whether the square holds a mine or not? So squares(x,y,s) is 0 for mine, 1 for clear?

There's to approaches you could make. Both involved store both the state and the mine/not-mine data in the array (actually, you COULD have parallel arrays, but I'm not even going to bring it up to do horribleness)

1:

The value store at a position (x,y) in the array would be an integer. 1,2,3 would be the state. a negative would represent a mine

So a state of 1 would be (I'm assuming) a non-clicked square the is empty. A square with state of -1 would be a non-clicked square that contains a mine.

2: Better, IMO

Declare a type like so:

code:
type block
   record of
      state : int
      mine : boolean
   end record
(at least i think thats the right syntax)

and have an array to store the blocks:

code:
var squares : array 1 .. 10, 1 .. 10 of block

for x : 1 .. 10
   for y : 1 .. 10
      squares(x,y).state = 1
      squares(x,y).mine = false
   end for
end for
Author:  cavetroll [ Fri Jul 27, 2007 1:54 pm ]
Post subject:  Re: Minesweeper help
I think you misinterpreted what I said, if not I misinterpreted your message. I have 3 dimensions because the first 2 hold the x and y position on the grid. the second one stores state(whether it has been left or right clicked), count(how many mines are around this square), and type(whether it is a mine(1) or non-mine square(2)). These are accessed using the constants state, count, and typ. All squares start with the state value of 1(2 is left clicked, 3 is right clicked). the count value is different for each square.
Author:  Aziz [ Fri Jul 27, 2007 2:01 pm ]
Post subject:  RE:Minesweeper help
Could you post your source code?

An array's indices should only represent position.

Having an array with indices (x, y, state) represents squares in terms of x,y and state positions

each state (1,2,3) is a different value. The line squares (nodex, nodey, state) := 2 is "set the square at x position nodex, y position nodey, and state position state to 2. It does not mean set the state of square x,y to 2.

Its a bit confounding, so please post your source code and I can better understand it.
Author:  cavetroll [ Fri Jul 27, 2007 2:46 pm ]
Post subject:  Re: Minesweeper help
K here's the code,
code:

buttonchoose ("multibutton")
setscreen ("graphics:max,max")
const typ : int := 1
const count : int := 2
const state : int := 3
var xback, xfor, yback, yfor : int := 0
var font : int := Font.New ("Arial:20")
var mines : int := 0
var squares : array 1 .. 18, 1 .. 18, 1 .. 3 of int
var x, y, bud, btn : int
proc floodfill (nodex : int, nodey : int)
    if squares (nodex, nodey, typ) not= 2 then
        return
    else
        squares (nodex, nodey, state) := 2
        for decreasing i : 1 .. -1
            for ii : -1 .. 1
                if nodex - i > 0 and nodex - i < 19 and nodey - ii > 0 and nodey - ii < 19 then
                    if i not= 0 and ii not= 0 then
                        floodfill (nodex - i, nodey - ii)
                    end if
                end if
            end for
        end for
        return
    end if
end floodfill
     
loop
    mines := 0
    for i : 1 .. 18
        for ii : 1 .. 18
            squares (i, ii, count) := 0
            if mines = 75 then
                squares (i, ii, typ) := 2
            else
                squares (i, ii, typ) := Rand.Int (1, 6)
                if squares (i, ii, typ) > 1 then
                    squares (i, ii, typ) := 2
                end if
            end if
            if squares (i, ii, typ) = 1 then
                mines += 1
            end if
            squares (i, ii, state) := 1
        end for
    end for
    exit when mines = 75
end loop
for i : 1 .. 18
    for ii : 1 .. 18
        if squares (i, ii, typ) = 2 then
            for t : -1 .. 1
                for tt : -1 .. 1
                    if i + t > 0 and i + t < 19 and ii + tt > 0 and ii + tt < 19 then
                        if squares (i + t, ii + tt, typ) = 1 then
                            squares (i, ii, count) += 1
                        end if
                        if squares (i, ii, count) = 0 then
                            squares (i, ii, state) := 1
                        else
                            squares (i, ii, state) := 1
                        end if
                    end if
                end for
            end for
        end if
    end for
end for
loop
    for i : 1 .. 18
        for ii : 1 .. 18
            drawfillbox (i * 25, ii * 25, i * 25 + 25, ii * 25 + 25, 29)
            drawbox (i * 25, ii * 25, i * 25 + 25, ii * 25 + 25, 7)
            if squares (i, ii, state) = 2 then
                if squares (i, ii, typ) = 2 then
                    Font.Draw (intstr (squares (i, ii, count)), i * 25 + 5, ii * 25 + 2, font, 12)
                else
                    drawfill (i * 25 + 5, ii * 25 + 5, 42, 7)
                end if
            end if
            if squares (i, ii, state) = 3 then
                drawfillbox (i * 25 + 5, ii * 25 + 5, i * 25 + 20, ii * 25 + 20, 42)
            end if
        end for
    end for
    buttonwait ("down", x, y, btn, bud)
    if x >= 25 and x <= 18 * 25 + 25 and y >= 25 and y <= 18 * 25 + 25 and btn = 1 then
        if squares (x div 25, y div 25, state) = 1 then
            floodfill (x div 25, y div 25)
        end if
    end if
    if x >= 25 and x <= 18 * 25 + 25 and y >= 25 and y <= 18 * 25 + 25 and btn = 3 then
        if squares (x div 25, y div 25, state) = 1 then
            squares (x div 25, y div 25, state) := 3
        elsif squares (x div 25, y div 25, state) = 3 then
            squares (x div 25, y div 25, state) := 1
        end if
    end if
end loop


Again I apologize for the messy code.
Author:  Aziz [ Fri Jul 27, 2007 2:56 pm ]
Post subject:  RE:Minesweeper help
I understand know. The third dimension represent what aspect you're trying to access of a certain square

Declare your constants with CAPS, it is a good style and helps determining that they're constants rather than variables.

So, to set the type it would be squares(x, y, TYPE) := type

to set state: squares(x, y, STATE) := state

to set count: squares(x, y, COUNT) := count

At first look, it seems it should work, though I haven't gone into it deep. As I don't have Turing at work (as my copy may be less than legal, not sure if I am still a student or not Razz), would you mind describing what does happen?

PS. Comment-as-you-go. Works wonders.
Author:  CodeMonkey2000 [ Fri Jul 27, 2007 3:25 pm ]
Post subject:  RE:Minesweeper help
I didn't look at your code, but your procedure doesn't do anything. All the variables are local, therefore you aren't making any changes to the variables outside of the procedure. Anything you do within the procedure, doesn't affect your main program.
Author:  Aziz [ Fri Jul 27, 2007 3:27 pm ]
Post subject:  RE:Minesweeper help
I believe the 5th line sets the state of the square to 2
Author:  CodeMonkey2000 [ Fri Jul 27, 2007 3:30 pm ]
Post subject:  RE:Minesweeper help
Opps. Silly me I overlooked that Razz
Author:  CodeMonkey2000 [ Fri Jul 27, 2007 4:11 pm ]
Post subject:  Re: Minesweeper help
I managed to make it even more messy!!!!!!
I'm too lazy to clean it up myself, but you should be able to.
Turing:


buttonchoose ("multibutton")
setscreen ("graphics:550,550")
const typ : int := 1
const count : int := 2
const state : int := 3
var xback, xfor, yback, yfor : int := 0
var font : int := Font.New ("Arial:20")
var mines : int := 0
var squares : array 1 .. 18, 1 .. 18, 1 .. 3 of int
var x, y, bud, btn : int

%checks if the next square is onscreen
fcn onScreen (x, y : int) : boolean
    result x > 0 and x < 19 and y > 0 and y < 19
end onScreen

proc floodfill (nodex : int, nodey : int)
    %this is where it gets ugly
    if squares (nodex, nodey, typ) = 2 then
        squares (nodex, nodey, state) := 2
    else
        squares (nodex, nodey, state) := 2
        %check to the right
        if onScreen (nodex + 1, nodey) then
            if squares (nodex + 1, nodey, typ) = 3 and squares (nodex + 1, nodey, state) not= 2 then
                floodfill (nodex + 1, nodey)
            end if
        end if
        %check to the left
        if onScreen (nodex - 1, nodey) then
            if squares (nodex - 1, nodey, typ) = 3 and squares (nodex - 1, nodey, state) not= 2 then
                floodfill (nodex - 1, nodey)
            end if
        end if
        %check to the up
        if onScreen (nodex, nodey + 1) then
            if squares (nodex, nodey + 1, typ) = 3 and squares (nodex, nodey + 1, state) not= 2 then
                floodfill (nodex, nodey + 1)
            end if
        end if
        %check to the down
        if onScreen (nodex, nodey - 1) then
            if squares (nodex, nodey - 1, typ) = 3 and squares (nodex, nodey - 1, state) not= 2 then
                floodfill (nodex, nodey - 1)
            end if
        end if
    end if
end floodfill

loop
    mines := 0
    for i : 1 .. 18
        for ii : 1 .. 18
            squares (i, ii, count) := 0
            if mines = 75 then
                squares (i, ii, typ) := 2
            else
                %it can be open,mine or a number
                squares (i, ii, typ) := Rand.Int (1, 3)
            end if
            if squares (i, ii, typ) = 1 then
                mines += 1
            end if
            squares (i, ii, state) := 1
        end for
    end for
    exit when mines = 75
end loop
for i : 1 .. 18
    for ii : 1 .. 18
        if squares (i, ii, typ) = 2 then
            for t : -1 .. 1
                for tt : -1 .. 1
                    if i + t > 0 and i + t < 19 and ii + tt > 0 and ii + tt < 19 then
                        if squares (i + t, ii + tt, typ) = 1 then
                            squares (i, ii, count) += 1
                        end if
                        if squares (i, ii, count) = 0 then
                            squares (i, ii, state) := 1
                        else
                            squares (i, ii, state) := 1
                        end if
                    end if
                end for
            end for
        end if
    end for
end for
loop
    for i : 1 .. 18
        for ii : 1 .. 18
            drawfillbox (i * 25, ii * 25, i * 25 + 25, ii * 25 + 25, 29)
            drawbox (i * 25, ii * 25, i * 25 + 25, ii * 25 + 25, 7)
            if squares (i, ii, state) = 2 then
                if squares (i, ii, typ) = 2 then
                    Font.Draw (intstr (squares (i, ii, count)), i * 25 + 5, ii * 25 + 2, font, 12)
                end if
            end if
            %an open square
            if squares (i, ii, typ) = 3 and squares (i, ii, state) = 2 then
                drawfillbox (i * 25 + 5, ii * 25 + 5, i * 25 + 20, ii * 25 + 20, 42)
            end if
            %a mine
            if squares (i, ii, typ) = 1 and squares (i, ii, state) = 2 then
                drawfillbox (i * 25 + 5, ii * 25 + 5, i * 25 + 20, ii * 25 + 20, red)
            end if
        end for
    end for
    buttonwait ("down", x, y, btn, bud)
    if x >= 25 and x <= 18 * 25 + 25 and y >= 25 and y <= 18 * 25 + 25 and btn = 1 then
        if squares (x div 25, y div 25, state) = 1 then
            floodfill (x div 25, y div 25)
        end if
    end if
    if x >= 25 and x <= 18 * 25 + 25 and y >= 25 and y <= 18 * 25 + 25 and btn = 3 then
        if squares (x div 25, y div 25, state) = 1 then
            squares (x div 25, y div 25, state) := 3
        elsif squares (x div 25, y div 25, state) = 3 then
            squares (x div 25, y div 25, state) := 1
        end if
    end if
end loop

Author:  Saad [ Fri Jul 27, 2007 4:12 pm ]
Post subject:  RE:Minesweeper help
Get rid of the 3rd dimension, and have a type for cell which contains the number of mines around it and its click status
Author:  CodeMonkey2000 [ Fri Jul 27, 2007 4:22 pm ]
Post subject:  RE:Minesweeper help
I basically redid your procedure. I'm not familiar with this algorithm ( or any path finding algorithm) but wikipedia is a great resource Very Happy . Anyway, you didn't have any open squares. All of them were either mines or numbers. I fixed that. I assumed typ 1 (red square) to be mine typ 2 to be a number and typ 3 to be an open space (orange square /which we search for in the the floodfill procedure)
Author:  Aziz [ Sat Jul 28, 2007 7:49 am ]
Post subject:  RE:Minesweeper help
a100: that would be the preferred route. perhaps he does not have experience with types though. Great tutorials to learn here however.

Anyways, I'm in Niagara Falls so I'm not wasting my time this weekend on the computer, Peace
Author:  Ultrahex [ Sun Jul 29, 2007 12:29 am ]
Post subject:  Re: Minesweeper help
I created a little short way to do it by command (so basically no GUI, just an engine) just to show how you would implement something like it...
only reason i did it that way cause i was really confused by your code because it was so messy and the lack of comments!
hopefully this will help you out a bit.


Turing:
type block :
    record
        value : int
        shown : boolean
        mine : boolean
    end record


var font : int := Font.New ("Arial:9")


% Create Array of Blocks
var squares : array 1 .. 10, 1 .. 10 of block

% Create Default Grid with all value of 0 and none shown and none are mines
for x : 1 .. 10
    for y : 1 .. 10
        squares (x, y).value := 0
        squares (x, y).shown := false
        squares (x, y).mine := false
    end for
end for

proc showSquare (x : int, y : int)
    % Verify Square Within Range Of Array
    if (x > 0 and x < 11 and y > 0 and y < 11) then
        % Check if Already Shown, If Already Shown does not need to check ones around it Again
        if (~squares (x, y).shown) then
            % Show Square, Because it Hasn't Been Shown
            squares (x, y).shown := true
            if (squares (x, y).value = 0) then
                % Check all Squares around Newly Shown Square to see if any around should be Shown Also
                showSquare (x + 1, y + 1)
                showSquare (x - 1, y + 1)
                showSquare (x + 1, y - 1)
                showSquare (x - 1, y - 1)
                showSquare (x + 1, y)
                showSquare (x - 1, y)
                showSquare (x, y + 1)
                showSquare (x, y - 1)
            end if
        end if
    end if
end showSquare

proc createMine (x : int, y : int)
    squares (x, y).mine := true
    squares (x, y).value := -1

    % Increase Value of all Squares Around Mine
    squares (x + 1, y + 1).value += 1
    squares (x - 1, y + 1).value += 1
    squares (x + 1, y - 1).value += 1
    squares (x - 1, y - 1).value += 1
    squares (x + 1, y).value += 1
    squares (x - 1, y).value += 1
    squares (x, y + 1).value += 1
    squares (x, y - 1).value += 1
end createMine

proc drawboard (x : int, y : int)
    for i : 1 .. 10
        for j : 1 .. 10
            if (squares (i, j).shown) then
                drawfillbox (x + i * 20, y + j * 20, x + i * 20 + 20, y + j * 20 + 20, darkgrey)
                drawbox (x + i * 20, y + j * 20, x + i * 20 + 20, y + j * 20 + 20, black)

                if (squares (i, j).value > 0) then
                    Font.Draw (intstr (squares (i, j).value), i * 20 + x + 5, j * 20 + y + 5, font, red)
                end if
            else
                drawfillbox (x + i * 20, y + j * 20, x + i * 20 + 20, y + j * 20 + 20, grey)
                drawbox (x + i * 20, y + j * 20, x + i * 20 + 20, y + j * 20 + 20, black)
            end if
        end for
    end for
end drawboard


% Create Mines
createMine (3, 3)
createMine (3, 4)
createMine (2, 3)
createMine (7,8)
createMine(7,7)
createMine(6,9)
createMine(5,8)
createMine(8,9)

% Equivalent to Click on square at (x,y) => (5,5)
showSquare (5, 5)

% Draw Board After Clicked
drawboard (50, 50)
Author:  cavetroll [ Mon Jul 30, 2007 7:35 pm ]
Post subject:  Re: Minesweeper help
Thanks for all your help, I got it working. Here is the finished procedure.

code:
proc floodfill (nodex : int, nodey : int)
    if squares (nodex, nodey, state) = 1 then
        if squares (nodex, nodey, typ) not= 2 then
            return
        elsif squares (nodex, nodey, count) > 0 then
            squares (nodex, nodey, state) := 2
            return
        else
            squares (nodex, nodey, state) := 2
            for decreasing i : 1 .. -1
                for ii : -1 .. 1
                    if nodex - i > 0 and nodex - i < sizex + 1 and nodey - ii > 0 and nodey - ii < sizey + 1 then
                        if i = 0 and ii = 0 then
                        else
                            floodfill (nodex - i, nodey - ii)
                        end if
                    end if
                end for
            end for
        end if
    end if
end floodfill

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy