They got this cool new thing on Windows 3.11, it's called MineSweeper and it's absolutely crazy. MineSweeper is a logic game in which you are tasked with revealing all the tiles of a mine field without ever stepping on a landmine.

The setup

The field is a collection of cells organized in a two-dimensional grid. Each cell has two attributes: a numeric value that holds the number of mines located nearby (if any) or a special code that signifies the cell is a mine. The second attribute is sort of a display setting we'll call "cell status" (or "cStat" for short.) It tells us whether or not the cell has been revealed, or if the player put a flag (if he thinks there's a mine there) or question mark (to remember there could be a mine) on it.

To keep things tightly packed, we're going to place both attributes into one INTEGER and use some masking to access the data. The low nibble (4 bits) will contain 0 if there are no mines nearby, a number between 1 and 8 if there are some mines nearby, or 9 if the cell itself is a mine (since we cannot reveal mines, there's no point in keeping track of the number of neighboring mines.) The high nibble will just contain a series a bitflags so we know how it should be displayed on screen.

Let's setup some shared variables for the field dimensions (in cells,) as well as the total number of mines, and of course a simple one-dimensional array to hold the whole field:

CONST CellCounterMask = &HF  ' Cell counter mask.

CONST CellIsMine = 9         ' Counter code for "mine."

CONST cStatClear = &H10      ' Player put a flag on this cell.
CONST cStatMaybe = &H20      ' Player put a question mark on this cell.
CONST cStatReveal = &H40     ' This cell is uncovered.

CONST MaxFieldSize = 256     ' Maximum field size, in cells.

DIM SHARED gField(MaxFieldSize - 1) AS INTEGER ' Field data.
DIM SHARED gFieldW AS INTEGER                  ' Field width, in cells.
DIM SHARED gFieldH AS INTEGER                  ' Field height, in cells.
DIM SHARED gNumCells AS INTEGER                ' Total number of cells (gFieldW * gFieldH.)
DIM SHARED gNumMines AS INTEGER                ' Number of mines.
DIM SHARED gNumClear AS INTEGER                ' Number of cells cleared.

Accessing the cell's status (in the high nibble) is straighforward: we simply use the AND boolean operator with one of the bitflags we defined (let's say "cStatReveal") and see if the result is not NULL:

IF (gField(16) AND cStatReveal) THEN
  PRINT "Cell number 16 is revealed"
ELSE
  PRINT "Cell number 16 is still covered"
END IF

We can also use the OR boolean operator to set a bitflag. For instance, if we want to reveal the entirety of the field, we just:

DECLARE SUB fieldRevealAll ()

''
'' REVEAL THE WHOLE FIELD
''
SUB fieldRevealAll
  FOR i% = 0 TO gNumCells - 1
    gField(i%) = gField(i%) OR cStatReveal
  NEXT i%
END SUB

To determine the number of mines nearby (or if the cell itself is a mine,) we mask the 4 least significant bits with CellCounterMask:

counter% = (gField(t%) AND CellCounterMask)
SELECT CASE counter%
CASE 0
  PRINT "There no mine nearby"; t%
CASE 1 TO 8
  PRINT "There is/are"; counter%; "mine(s) near cell"; t%
CASE CellIsMine
  PRINT "Cell"; t%; "is a mine!"
END SELECT

We're off to a good start.

Rendering the field

It may seem a little premature to write the drawing routine, but Minesweeper is not a complex game and we already have all the data we need to display the field... so let's do it!

First, we're going to reserve an array to store DRAW instructions we can use to write the number of mines nearby, then we go through each cell, one by one, and draw a rectangle at the proper place. Depending on the cell's status, we either write the number of mines nearby, a mine, or an emboss if the cell is still covered.

We're going to use Mode 13 (320x200 and 256 colors) for this. If you want to use a high resolution mode like Mode 13 (640x480 and 16 colors,) modify the constants "cellW" and "cellH" to draw bigger cells ("cellHalfW" and "cellHalfH" will automatically adjust themselves.)

CONST cellW = 10             ' Width of a cell, in pixels
CONST cellH = 10             ' Height of a cell, in pixels
CONST cellHalfW = cellW \ 2  ' Half the width, in pixels
CONST cellHalfH = cellH \ 2  ' Half the height, in pixels

DECLARE SUB renderField (x AS INTEGER, y AS INTEGER)

SCREEN 13

''
'' DRAW THE WHOLE FIELD AT X,Y
''
SUB renderField (x AS INTEGER, y AS INTEGER)
  DIM ofsX AS INTEGER, ofsY AS INTEGER
  DIM cellOfs AS INTEGER, cellIndex AS INTEGER
  DIM digit(7) AS STRING

  ' Digit drawing codes (there can be up to 8 mines around)
  digit(0) = "c1 bm+0,1ed3gr2"     ' 1: blue
  digit(1) = "c2 rfg2dr2"          ' 2: green
  digit(2) = "c4 rfgfgl"           ' 3: red
  digit(3) = "c1 d2r2gd"           ' 4: blue
  digit(4) = "c4 bm+2,0l2d2rfgl"   ' 5: red
  digit(5) = "c3 bm+2,0lgd3r2u2l"  ' 6: cyan
  digit(6) = "c0 r2dgd2"           ' 7: black
  digit(7) = "c8 r2dg2dr2uh2"      ' 8: gray

  ' Draw tiles surface (light gray)
  LINE (x, y)-STEP(gFieldW * cellW - 1, gFieldH * cellH - 1), 7, BF

  ' For each row...
  FOR r% = 0 TO gFieldH - 1
    ' Get the drawing offset
    ofsY = y + r% * cellH
    ' Get the index of the 1st cell of the row
    cellOfs = r% * gFieldW
    ' For each column...
    FOR c% = 0 TO gFieldW - 1
      ' Get the drawing offset
      ofsX = x + c% * cellW
      ' Compute the full cell index
      cellIndex = cellOfs + c%
      ' If the cell is revealed...
      IF (gField(cellIndex) AND cStatReveal) THEN
        ' Get the counter value
        cnt = gField(cellIndex) AND CellCounterMask
        SELECT CASE cnt
        ' There are between 1 and 8 mines nearby, draw number
        CASE 1 TO 8
          DRAW "bm" + STR$(ofsX + cellHalfW - 2) + _
               "," + STR$(ofsY + cellHalfH - 3) + digit(cnt - 1)
        ' The cell itself is a mine
        CASE 9
          CIRCLE (ofsX + cellHalfW - 1, ofsY + cellHalfH - 1), cellH \ 3, 0
          PAINT (ofsX + cellHalfW - 1, ofsY + cellHalfH - 1), 0
        END SELECT
      ' The cell is still covered...
      ELSE
        ' Draw emboss
        LINE (ofsX, ofsY + (cellH - 2))-STEP(0, -(cellH - 2)), 15
        LINE -STEP((cellW - 2), 0), 15
        LINE (ofsX + (cellW - 1), ofsY + 1)-STEP(0, (cellH - 2)), 8
        LINE -STEP(-(cellW - 2), 0), 8
        ' The player put a flag on it
        IF (gField(cellIndex) AND cStatClear) THEN
          draw "bm " + str$(ofsX + 3) + "," + str$(ofsY + 7) + " c0r2h1u4r1 c4r1h-1l2d1r1"
        ' The player put a question mark on it
        ELSEIF (gField(cellIndex) AND cStatMaybe) THEN
          draw "bm " + str$(ofsX + 3) + "," + str$(ofsY + 3) + " c0u1r3d1g2 bm+0,+2 r0"
        END IF
      END IF
    NEXT c%
  NEXT r%
END SUB

You'll notice that the routine takes two INTEGERs to place the top-left corner of the field on the screen; I thought it would be handy if we want to center the field:

DIM scrX AS INTEGER, scrY AS INTEGER

' Compute on-screen vertical and horizontal
' position, center the field on the screen.
scrX = ((320 - cellW * gFieldW) \ 2) ' Set to 640 for mode 12
scrY = ((200 - cellH * gFieldH) \ 2) ' Set to 480 for mode 12

renderField scrX, scrY

It's just super handy. Speaking of handy...

Hello Neighbor

We need a routine to get the address of adjacent cells! It's going to be useful when we count neighboring mines but also when we start revealing tiles after a click.

Computing the index of neighbors is trivial (decrease the index of the master cell by the width of the board and you get the cell directly on top, increase the value to get the cell below, etc...) but making sure that the index is actually valid is something else. For instance, if we compute the index of cells located above the very 1st row, we'll get invalid values reaching outside the boundaries of the field. So how do we determine which indices are correct and which are not? We could use a few conditional branchings with SELECT CASE or IF, but we could also go for something slightly fancier.

You may remember that the 16-bit INTEGER value -1 is represented as 11111111 11111111 in binary. The opposite value, 0, is represented as 00000000 00000000. So far so good. Now, you may also remember that the OR boolean operator returns a value that includes all the bits that are set in either operands:

   00000100 00001111
OR 11110010 11110011
 = 11110110 11111111

It means that "-1 OR 0" returns -1:

   11111111 11111111
OR 00000000 00000000
 = 11111111 11111111

In fact, "-1 OR anything" always return -1. Do you also remember that when evaluating an expression, QuickBASIC returns either -1 for TRUE or 0 for FALSE? I think we're onto something here:

If we evaluate the expression "y <= 0" and Y is indeed 0 or less (that is, Y points to the topmost row of the field,) then we'll obtain -1 (or TRUE.) But if Y is greater than 0 (which implies there IS a row located above that Y location,) then we'll obtain 0 (or FALSE.) If we do the same for "y >= gFieldH - 1," "x <= 0," and "x >= gFieldW - 1," then we obtain masks that can turn any value into -1 if the index is out of reach, or do absolutely nothing if the index is located inside the field.

From there, all we have to do is calculate the cell index and use the boolean operator OR. The result is returned in an easy-to-manage 8-INTEGER long array:

DECLARE SUB getNearbyCells (x AS INTEGER, y AS INTEGER, adrLst() AS INTEGER)

''
'' THIS ROUTINE TAKES AN 8-INTEGER ARRAY AND FILLS IT
'' WITH THE INDICES OF NEIGHBORING CELLS. IF THE CELL
'' DOES NOT EXIST (LOCATED OUTSIDE THE AREA,) THEN ITS
'' INDEX NUMBER IS SET TO -1.
''
SUB getNearbyCells (x AS INTEGER, y AS INTEGER, adrLst() AS INTEGER)
  DIM maskLf AS INTEGER, maskRt AS INTEGER
  DIM maskUp AS INTEGER, maskDn AS INTEGER
  DIM index AS INTEGER, baseId AS INTEGER

  ' Get the vertical and horizontal masks. If the coordinate is located on the
  ' first or last row/column, then the mask is set to -1. Next, we're going to
  ' compute the index of the cell and apply the mask with the OR operator. If
  ' the mask is -1, the end result is -1. If the mask is 0, the end result is
  ' the index of the cell. In other words, any cell index that falls outside
  ' the field is represented as -1.
  maskLf = (x <= 0): maskRt = (x >= gFieldW - 1)
  maskUp = (y <= 0): maskDn = (y >= gFieldH - 1)

  ' Get the index of the selected cell
  baseId = x + y * gFieldW

  ' Top row
  index = baseId - gFieldW
  adrLst(0) = (index - 1) OR maskUp OR maskLf
  adrLst(1) = index OR maskUp
  adrLst(2) = (index + 1) OR maskUp OR maskRt

  ' Center row
  adrLst(3) = (baseId - 1) OR maskLf
  adrLst(4) = (baseId + 1) OR maskRt
 
  ' Bottom row
  index = baseId + gFieldW
  adrLst(5) = (index - 1) OR maskDn OR maskLf
  adrLst(6) = index OR maskDn
  adrLst(7) = (index + 1) OR maskDn OR maskRt
END SUB

No man's land

Don't you hate it when you click a random cell on a 20x20 board and step on the only mine on the board? Some Minesweeper games prevent that by moving the mine to the first empty cell available (usually in the top left corner of the field.) While it's a nice touch, I'd like to go further and make a 3x3 mine-free zone centered on the first click, so that the player can get some information about possible mines nearby.

First, let's write a routine to initialize the field, place the mines (while making sure the player did not trigger one on his first turn,) and update the counter of each cell so we know how many mines are adjacent. This routine only needs to be called ONCE right after the VERY FIRST click of the game (at that point, gNumClear equals 0.)

DECLARE SUB fieldInit (cellId AS INTEGER)

''
'' INITIALIZE FIELD, CALLED ONCE BEFORE PROCESSING THE 1ST CLICK.
'' "CELLID" IS THE INDEX OF THE CELL THE PLAYER CLICKED.
''
SUB fieldInit (cellId AS INTEGER)
  ' Place mines at random
  fieldPopulate
  ' Move mines triggered by the player
  fieldSafeClick cellId
  ' Reset mine counter of each cell
  fieldNearMines
END SUB

Alright. So, how do we place mines in the field? We could (and I do mean "could") loop indefinitely, picking cells at random and adding mines (if the cell doesn't contain one already) until we got the requested number. Let's call that technique "Method A:"

DECLARE SUB fieldPopulate ()

''
'' PLACE MINES AT RANDOM, THE WORST WAY POSSIBLE
''
SUB fieldPopulate
  DIM count AS INTEGER, index AS INTEGER

  count = gNumMines
  DO
    ' Take a cell at random
    index = INT(RND * gNumCells)
    ' If the cell doesn't contain a mine...
    IF ((gField(index) AND CellCounterMask) <> CellIsMine) then
      ' ... add it now.
      gField(index) = gField(index) OR CellIsMine
      ' Decrease mine counter.
      count = count - 1
    END IF
  LOOP WHILE (count)
END SUB

...it works but it's a bit clumsy. Here are two other options I like better.

Method B: first, we reset all cells, and then fill the first gNumMines cells with mines. Then we go through each cell again and swap them at random. It's easy to understand, but we can do better.

DECLARE SUB fieldPopulate ()

''
'' PLACE MINES AT RANDOM
''
SUB fieldPopulate
  ' Insert mines
  FOR t% = 0 TO gNumMines - 1
    gField(t%) = CellIsMine
  NEXT t%

  ' Clear the rest of the field
  FOR t% = gNumMines TO gNumCells - 1
    gField(t%) = 0
  NEXT t%

  ' Shuffle at random
  FOR t% = 0 TO gNumCells - 1
    SWAP gField(t%), gField(INT(RND * gNumCells))
  NEXT t%
END SUB

Method C: this time, we're going to do it in a single pass! We compute the ratio between the number of mines remaining and the number of cells left in the field. That value is 0 when there is no mine left to place, 1 when the number of mines to place is equal to the number of cells left in the field, or anything in-between if there are some mines left to place. We then compare this ratio to RND (this function returns a pseudo-random decimal value between 0 included and 1 excluded) to determine whether or not a mine should be placed.

DECLARE SUB fieldPopulate ()

''
'' PLACE MINES AT RANDOM
''
SUB fieldPopulate
  DIM remain AS INTEGER

  ' Number of mines left to place
  remain = gNumMines

  ' Go through the whole field
  FOR t% = 0 TO gNumCells - 1

    ' The ratio system balances the odds itself. It's pretty neat.
    IF (RND < (remain / (gNumCells - t%))) THEN
      gField(t%) = CellIsMine
      remain = remain - 1
    ELSE
      gField(t%) = 0
    END IF

  NEXT t%
END SUB

For the most skeptical out there, here's how it works: if we get God-awful RNG and the loop consistently fails to place mines, eventually the number of mines left to place equals the number of cells left to parse, producing a ratio of 1. Since RNG is always less than 1, it is guaranteed that all remaining cells are mines. But what if we have such RNG that the loop has been continuously placing mines? It will run out of mines, produce a ratio of 0, and because RNG is never less than 0, no more mine will be added.

TL;DR: it is mathematically impossible for this formula to place too many or too few mines, and thus it's bound to provide just the right amount every time.

Safety dance

Now is the time to move mines that the player has unearthed on the very first click. It's pretty straightforward: we test the cell that was clicked by the player and its direct neighbors. For each cell containing a mine, we remove it and increase a counter. We also tag those cells as a "safe zone" so we don't put the mines back there (just in case the player clicked the top left cell for instance.) Then we go back to the very first cell in the top left. If the cell doesn't already contain a mine and it is not tagged as "safe," insert the mine, decrease the counter and move to the next cell. Keep going until the counter reaches zero.

CONST cStatIsSafe = &H80 ' Can't move mine here.

DECLARE SUB fieldSafeClick (cellId AS INTEGER)

''
'' MOVE MINES ADJACENT TO THE PROVIDED CELL INDEX ELSEWEHRE.
''
SUB fieldSafeClick (cellId AS INTEGER)
  DIM x AS INTEGER, y AS INTEGER, near(7) AS INTEGER
  DIM index AS INTEGER, move AS INTEGER

  ' Get list of nearby cells
  x = cellId MOD gFieldW
  y = cellId \ gFieldW
  getNearbyCells x, y, near()

  ' There's a mine in the master cell (the one the player just clicked)
  IF ((gField(cellId) AND CellCounterMask) = CellIsMine) then
    ' Remove it
    gField(cellId) = 0
    ' Increment the number of mines we have to move
    move = move + 1
  END IF
  ' We cannot place a mine on this cell
  gField(cellId) = gField(cellId) OR cStatIsSafe

  ' Parse every neighbor
  FOR i% = 0 TO 7
    index = near(i%)
    ' This tile exists
    IF (index <> -1) THEN
      ' It contains a mine
      IF ((gField(index) AND CellCounterMask) = CellIsMine) THEN
        ' Remove it
        gField(index) = 0
        ' Increment the number of mines we have to move
        move = move + 1
      END IF
      ' We cannot place a mine on this cell
      gField(index) = gField(index) OR cStatIsSafe
    END IF
  NEXT i%

  ' Move mines top the top left corner of the board
  index = 0
  WHILE (move)
    ' The cell is not locked and doesn't have any mine, move one here
    IF (((gField(index) AND cStatIsSafe) = 0) AND (gField(index) = 0)) THEN
      gField(index) = CellIsMine
      move = move - 1
    END IF
    ' Test the next tile
    index = index + 1
  WEND
END SUB

Warning: mine ahead

The field has been initialized, all mines are placed and a safe zone has been defined... however, we're not done just yet. Before going for the big reveal we have to initialize the "nearby mines" counter of each cell.

Rather than checking all 8 neighbors of every cell for mines, we're going to look for mines only, and then increment by 1 the counter of each adjacent cell that doesn't contain a mine.

DECLARE SUB fieldNearMines ()

''
'' UPDATE NEARBY MINES COUNTERS
''
SUB fieldNearMines
  DIM rowId AS INTEGER, near(7) AS INTEGER

  ' For each row, ...
  FOR r% = 0 TO gFieldH - 1
    ' Get the address of the 1st cell of the row
    rowId = r% * gFieldW

    ' For each column, ...
    FOR c% = 0 TO gFieldW - 1

      ' This cell contains a mine, update neighbors mine counter
      IF ((gField(rowId + c%) AND CellCounterMask) = CellIsMine) THEN

        ' Get list of nearby cells
        getNearbyCells c%, r%, near()
        ' Go through the neighbor list
        FOR i% = 0 TO 7
          ' This is a valid cell index
          IF (near(i%) <> -1) THEN
            ' Increment the mine counter if the cell doesn't contain a mine
            gField(near(i%)) = gField(near(i%)) - (gField(near(i%)) <> CellIsMine)
          END IF
        NEXT i%

      END IF
    NEXT c%
  NEXT r%
END SUB

The mine behind the curtain

We don't really need to use a span-filling Flood fill algorithm but we should, in the very least, try to come up with a non-recursive (iterative) routine. For those who arrived late, a recursive routine is a routine that invokes itself ("I like my coffee like I like my coffee: recursive.")

Recursions are easy to write (because they don't actually need any adjustement to the routine,) but they're slower to process because function/routine calls are not cheap. They also consume much more memory than non-recursive routines and in this specific case, they may crash the application with a "out of stack space" error when processing large boards.

The iterative function we're going to write will maintain a list of cells that must be processed. At first, the list only contains one cell (the one the player clicked.) Then we enter a loop that reads the last entry of the list and discards it (by simply decreasing the list length.) The code inside the loop tests nearby cells and may append them to the list if they satisfy two conditions:

1. They are not yet part of the list.
2. They are not tagged for reveal.

The loop ends when the list is empty.

CONST cStatQueued = &H100 ' Cell queued for reveal.

DECLARE FUNCTION fieldReveal% (x AS INTEGER, y AS INTEGER)

''
'' REVEAL CELLS STARTING WITH THE ONE LOCATED AT X,Y. THIS
'' FUNCTION RETURNS THE TOTAL NUMBER OF CELLS REVEALED OR
'' -1 IF THE PLAYER DUG UP A MINE. THE ROUTINE IS ITERATIVE
'' RATHER THAN RECURSIVE (IT MAINTAINS A LIST OF CELLS TO
'' PROCESS RATHER THAN CALL ITSELF OVER AND OVER AGAIN.)
''
FUNCTION fieldReveal% (x AS INTEGER, y AS INTEGER)
  DIM cell(MaxFieldSize - 1) AS INTEGER ' Reveal queue
  DIM numCells AS INTEGER               ' Reveal queue size
  DIM index AS INTEGER                  ' Convenience variable: cell index
  DIM near(7) AS INTEGER                ' Indices of adjacent cells

  ' Get cell index
  index = x + y * gFieldW

  ' Cell is revealed or is protected by a flag/question mark, abort.
  IF (gField(index) AND (cStatClear OR cStatMaybe OR cStatReveal)) THEN
    fieldReveal% = 0
    EXIT FUNCTION
  END IF

  ' Cell is a mine, game over.
  IF ((gField(index) AND CellCounterMask) = CellIsMine) THEN
    fieldReveal% = -1
    EXIT FUNCTION
  END IF

  ' Push cell into list and set "queued" flag. The queued flag is used to
  ' prevent cells that have not been processed yet to be inserted into the
  ' list again. The flag is cleared as soon as the cell has been processed
  ' and its content is revealed. Cells that are already visible cannot enter
  ' the queue.
  cell(numCells) = index
  numCells = numCells + 1
  gField(index) = gField(index) OR cStatQueued

  ' The queue is not empty, keep going.
  DO WHILE (numCells)

    ' This function returns the number of cells that have been
    ' successfuly revealed after each click, and we're just about
    ' to reveal one more cell, so let's update the counter now!
    revealCount = revealCount + 1

    ' Pop cell from queue, ...
    numCells = numCells - 1
    index = cell(numCells)

    ' ... and clear its "queued" flag.
    gField(index) = gField(index) XOR cStatQueued

    ' Tag as "revealed."
    gField(index) = gField(index) OR cStatReveal

    ' If there's no mine nearby, get all adjacent cells and
    ' push them into the queue so we can process them later.
    IF ((gField(index) AND CellCounterMask) = 0) THEN

      ' Get neighbors list.
      getNearbyCells index MOD gFieldW, index \ gFieldW, near()

      ' Go through the list.
      FOR i% = 0 TO 7
        index = near(i%)

        ' This neighbor exists!
        IF (index <> -1) THEN

          ' If the neighbor has not been queued yet and is not revealed...
          IF ((gField(index) AND (cStatReveal OR cStatQueued)) = 0) THEN

            ' Push neighbor cell to queue!
            cell(numCells) = index
            numCells = numCells + 1

            ' ... and set its "queued" flag so we don't
            ' attempt to push it into the queue again later.
            gField(index) = gField(index) OR cStatQueued

          END IF
        END IF
      NEXT i%
    END IF

    ' One cell has been revealed and all its neighbors have been added to the
    ' the queue so they can be processed. Keep going until the whole queue is
    ' depleted (see the DO statement earlier.)
  LOOP

  ' Return the number of cells revealed.
  fieldReveal% = revealCount
END FUNCTION

All we have to do now is catch the value returned by fieldReveal%(): if it is -1, the player found a mine and it's game over. If it's 0, the player clicked a cell that's already revealed and nothing happens. If it's anything else, we take the value and add it to the general counter gNumClear. Finally, if gNumCells = gNumClear + gNumMines, the player won.

Dig it!

We have all the pieces we need, now we just have to take user inputs and redraw the screen as we go. To limit the amount of code, we'll go with simple keyboard controls: arrow keys to move the cursor around, space/enter to reveal cells, plus to place a flag or question mark, and escape to quit.

Here's what the full code looks like:

DECLARE SUB main (w AS INTEGER, h AS INTEGER, m AS INTEGER)
DECLARE SUB getNearbyCells (x AS INTEGER, y AS INTEGER, adrLst() AS INTEGER)
DECLARE SUB renderField (x AS INTEGER, y AS INTEGER)
DECLARE SUB fieldInit (cellId AS INTEGER)
DECLARE SUB fieldPopulate ()
DECLARE SUB fieldSafeClick (cellId AS INTEGER)
DECLARE SUB fieldNearMines ()
DECLARE SUB fieldRevealAll ()
DECLARE SUB fieldFlag (cellId AS INTEGER)
DECLARE FUNCTION fieldReveal% (x AS INTEGER, y AS INTEGER)

CONST MaxFieldSize = 256     ' Maximum field size, in cells.

CONST CellCounterMask = &HF  ' Cell counter mask.
CONST CellIsMine = 9         ' Counter code for "mine."
CONST cStatClear = &H10      ' Player put a flag on this cell.
CONST cStatMaybe = &H20      ' Player put a question mark on this cell.
CONST cStatReveal = &H40     ' This cell is uncovered.
CONST cStatIsSafe = &H80     ' Can't move mine here.
CONST cStatQueued = &H100    ' Cell queued for reveal.

CONST cellW = 10             ' Width of a cell, in pixels
CONST cellH = 10             ' Height of a cell, in pixels
CONST cellHalfW = cellW \ 2  ' Half the width, in pixels
CONST cellHalfH = cellH \ 2  ' Half the height, in pixels

DIM SHARED gField(MaxFieldSize - 1) AS INTEGER ' Field data.
DIM SHARED gFieldW AS INTEGER                  ' Field width, in cells.
DIM SHARED gFieldH AS INTEGER                  ' Field height, in cells.
DIM SHARED gNumCells AS INTEGER                ' Total number of cells (gFieldW * gFieldH.)
DIM SHARED gNumMines AS INTEGER                ' Number of mines.
DIM SHARED gNumClear AS INTEGER                ' Number of cells cleared.

' Set graphic mode 13 (320x200, 256 colors)
SCREEN 13

' Start a new game with a 10x10 field and 8 mines
main 10, 10, 8

''
'' TOGGLE FLAG AND QUESTION MARK.
''
SUB fieldFlag (cellId AS INTEGER)
  ' Replace flag by question mark
  IF (gField(cellId) AND cStatClear) THEN
    gField(cellId) = (gField(cellId) XOR cStatClear) OR cStatMaybe
  ' Remove question mark
  ELSEIF (gField(cellId) AND cStatMaybe) THEN
    gField(cellId) = gField(cellId) XOR cStatMaybe
  ' Place flag
  ELSE
    gField(cellId) = gField(cellId) OR cStatClear
  END IF
END SUB

''
'' INITIALIZE FIELD, CALLED ONCE BEFORE PROCESSING THE 1ST CLICK.
'' "CELLID" IS THE INDEX OF THE CELL THE PLAYER CLICKED.
''
SUB fieldInit (cellId AS INTEGER)
  ' Place mines at random
  fieldPopulate
  ' Move mines triggered by the player
  fieldSafeClick cellId
  ' Reset mine counter of each cell
  fieldNearMines
END SUB

''
'' UPDATE NEARBY MINES COUNTERS
''
SUB fieldNearMines
  DIM rowId AS INTEGER, near(7) AS INTEGER

  ' For each row, ...
  FOR r% = 0 TO gFieldH - 1
    ' Get the address of the 1st cell of the row
    rowId = r% * gFieldW

    ' For each column, ...
    FOR c% = 0 TO gFieldW - 1

      ' This cell contains a mine, update neighbors mine counter
      IF ((gField(rowId + c%) AND CellCounterMask) = CellIsMine) THEN

        ' Get list of nearby cells
        getNearbyCells c%, r%, near()
        ' Go through the neighbor list
        FOR i% = 0 TO 7
          ' This is a valid cell index
          IF (near(i%) <> -1) THEN
            ' Increment the mine counter if the cell doesn't contain a mine
            gField(near(i%)) = gField(near(i%)) - (gField(near(i%)) <> CellIsMine)
          END IF
        NEXT i%

      END IF
    NEXT c%
  NEXT r%
END SUB

''
'' PLACE MINES AT RANDOM
''
SUB fieldPopulate
  DIM remain AS INTEGER

  ' Number of mines left to place
  remain = gNumMines

  ' Go through the whole field
  FOR t% = 0 TO gNumCells - 1

    ' The ratio system balances the odds itself. It's pretty neat.
    IF (RND < (remain / (gNumCells - t%))) THEN
      gField(t%) = CellIsMine
      remain = remain - 1
    ELSE
      gField(t%) = 0
    END IF

  NEXT t%
END SUB

''
'' REVEAL CELLS STARTING WITH THE ONE LOCATED AT X,Y. THIS
'' FUNCTION RETURNS THE TOTAL NUMBER OF CELLS REVEALED OR
'' -1 IF THE PLAYER DUG UP A MINE. THE ROUTINE IS ITERATIVE
'' RATHER THAN RECURSIVE (IT MAINTAINS A LIST OF CELLS TO
'' PROCESS RATHER THAN CALL ITSELF OVER AND OVER AGAIN.)
''
FUNCTION fieldReveal% (x AS INTEGER, y AS INTEGER)
  DIM cell(MaxFieldSize - 1) AS INTEGER ' Reveal queue
  DIM numCells AS INTEGER               ' Reveal queue size
  DIM index AS INTEGER                  ' Convenience variable: cell index
  DIM near(7) AS INTEGER                ' Indices of adjacent cells

  ' Get cell index
  index = x + y * gFieldW

  ' Cell is revealed or is protected by a flag/question mark, abort.
  IF (gField(index) AND (cStatClear OR cStatMaybe OR cStatReveal)) THEN
    fieldReveal% = 0
    EXIT FUNCTION
  END IF

  ' Cell is a mine, game over.
  IF ((gField(index) AND CellCounterMask) = CellIsMine) THEN
    fieldReveal% = -1
    EXIT FUNCTION
  END IF

  ' Push cell into list and set "queued" flag. The queued flag is used to
  ' prevent cells that have not been processed yet to be inserted into the
  ' list again. The flag is cleared as soon as the cell has been processed
  ' and its content is revealed. Cells that are already visible cannot enter
  ' the queue.
  cell(numCells) = index
  numCells = numCells + 1
  gField(index) = gField(index) OR cStatQueued

  ' The queue is not empty, keep going.
  DO WHILE (numCells)

    ' This function returns the number of cells that have been
    ' successfuly revealed after each click, and we're just about
    ' to reveal one more cell, so let's update the counter now!
    revealCount = revealCount + 1

    ' Pop cell from queue, ...
    numCells = numCells - 1
    index = cell(numCells)

    ' ... and clear its "queued" flag.
    gField(index) = gField(index) XOR cStatQueued

    ' Tag as "revealed."
    gField(index) = gField(index) OR cStatReveal

    ' If there's no mine nearby, get all adjacent cells and
    ' push them into the queue so we can process them later.
    IF ((gField(index) AND CellCounterMask) = 0) THEN

      ' Get neighbors list.
      getNearbyCells index MOD gFieldW, index \ gFieldW, near()

      ' Go through the list.
      FOR i% = 0 TO 7
        index = near(i%)

        ' This neighbor exists!
        IF (index <> -1) THEN

          ' If the neighbor has not been queued yet and is not revealed...
          IF ((gField(index) AND (cStatReveal OR cStatQueued)) = 0) THEN

            ' Push neighbor cell to queue!
            cell(numCells) = index
            numCells = numCells + 1

            ' ... and set its "queued" flag so we don't
            ' attempt to push it into the queue again later.
            gField(index) = gField(index) OR cStatQueued

          END IF
        END IF
      NEXT i%
    END IF

    ' One cell has been revealed and all its neighbors have been added to the
    ' the queue so they can be processed. Keep going until the whole queue is
    ' depleted (see the DO statement earlier.)
  LOOP

  ' Return the number of cells revealed.
  fieldReveal% = revealCount
END FUNCTION

''
'' REVEAL THE WHOLE FIELD
''
SUB fieldRevealAll
  FOR i% = 0 TO gNumCells - 1
    gField(i%) = gField(i%) OR cStatReveal
  NEXT i%
END SUB

''
'' MOVE MINES ADJACENT TO THE PROVIDED CELL INDEX ELSEWEHRE.
''
SUB fieldSafeClick (cellId AS INTEGER)
  DIM x AS INTEGER, y AS INTEGER, near(7) AS INTEGER
  DIM index AS INTEGER, move AS INTEGER

  ' Get list of nearby cells
  x = cellId MOD gFieldW
  y = cellId \ gFieldW
  getNearbyCells x, y, near()

  ' There's a mine in the master cell (the one the player just clicked)
  IF ((gField(cellId) AND CellCounterMask) = CellIsMine) THEN
    ' Remove it
    gField(cellId) = 0
    ' Increment the number of mines we have to move
    move = move + 1
  END IF
  ' We cannot place a mine on this cell
  gField(cellId) = gField(cellId) OR cStatIsSafe

  ' Parse every neighbor
  FOR i% = 0 TO 7
    index = near(i%)
    ' This tile exists
    IF (index <> -1) THEN
      ' It contains a mine
      IF ((gField(index) AND CellCounterMask) = CellIsMine) THEN
        ' Remove it
        gField(index) = 0
        ' Increment the number of mines we have to move
        move = move + 1
      END IF
      ' We cannot place a mine on this cell
      gField(index) = gField(index) OR cStatIsSafe
    END IF
  NEXT i%

  ' Move mines top the top left corner of the board
  index = 0
  WHILE (move)
    ' The cell is not locked and doesn't have any mine, move one here
    IF (((gField(index) AND cStatIsSafe) = 0) AND (gField(index) = 0)) THEN
      gField(index) = CellIsMine
      move = move - 1
    END IF
    ' Test the next tile
    index = index + 1
  WEND
END SUB

''
'' THIS ROUTINE TAKES AN 8-INTEGER ARRAY AND FILLS IT
'' WITH THE INDICES OF NEIGHBORING CELLS. IF THE CELL
'' DOES NOT EXIST (LOCATED OUTSIDE THE AREA,) THEN ITS
'' INDEX NUMBER IS SET TO -1.
''
SUB getNearbyCells (x AS INTEGER, y AS INTEGER, adrLst() AS INTEGER)
  DIM maskLf AS INTEGER, maskRt AS INTEGER
  DIM maskUp AS INTEGER, maskDn AS INTEGER
  DIM index AS INTEGER, baseId AS INTEGER

  ' Get the vertical and horizontal masks. If the coordinate is located on the
  ' first or last row/column, then the mask is set to -1. Next, we're going to
  ' compute the index of the cell and apply the mask with the OR operator. If
  ' the mask is -1, the end result is -1. If the mask is 0, the end result is
  ' the index of the cell. In other words, any cell index that falls outside
  ' the field is represented as -1.
  maskLf = (x <= 0): maskRt = (x >= gFieldW - 1)
  maskUp = (y <= 0): maskDn = (y >= gFieldH - 1)

  ' Get the index of the selected cell
  baseId = x + y * gFieldW

  ' Top row
  index = baseId - gFieldW
  adrLst(0) = (index - 1) OR maskUp OR maskLf
  adrLst(1) = index OR maskUp
  adrLst(2) = (index + 1) OR maskUp OR maskRt

  ' Center row
  adrLst(3) = (baseId - 1) OR maskLf
  adrLst(4) = (baseId + 1) OR maskRt
 
  ' Bottom row
  index = baseId + gFieldW
  adrLst(5) = (index - 1) OR maskDn OR maskLf
  adrLst(6) = index OR maskDn
  adrLst(7) = (index + 1) OR maskDn OR maskRt
END SUB

''
'' MAIN LOOP, WHERE THE MAGIC HAPPENS
''
SUB main (w AS INTEGER, h AS INTEGER, m AS INTEGER)
  DIM scrX AS INTEGER, scrY AS INTEGER        ' on-screen position
  DIM userStr AS STRING, userInt AS INTEGER   ' user inputs
  DIM plX AS INTEGER, plY AS INTEGER          ' player cursor (column and row)
  DIM cleared AS INTEGER, gameOver AS INTEGER ' tiles cleared, game over status

  ' Setup field variables
  gFieldW = w
  gFieldH = h
  gNumCells = w * h
  gNumMines = m

  ' Compute on-screen vertical and horizontal position,
  ' center the field on the screen.
  scrX = ((320 - cellW * gFieldW) \ 2)
  scrY = ((200 - cellH * gFieldH) \ 2)

  ' Number of mines and field size
  LOCATE 1, 1
  PRINT "  MINES:"; gNumMines
  PRINT "  CELLS:"; gNumCells

  ' Main loop
  DO
    ' Redraw whole field
    renderField scrX, scrY
    ' Redraw player cursor
    LINE (scrX + plX * cellW, scrY + plY * cellH)-STEP(cellW - 1, cellH - 1), 4, B
    ' Percentage of the field revealed
    LOCATE 3, 1
    PRINT "CLEARED:"; STR$((gNumClear * 100) \ (gNumCells - gNumMines)); "%"

    ' Game status: everything has been revealed
    IF (gNumClear + gNumMines = gNumCells) THEN
      PRINT "ALL DONE!"
      EXIT SUB
    ' Game status: player found a mine
    ELSEIF (gameOver) THEN
      PRINT "YOU BLEW IT!"
      EXIT SUB
    END IF

    ' User input, etc.
    DO
      userStr = INKEY$
      IF (LEN(userStr) = 1) THEN
        userInt = ASC(userStr)
      ELSEIF (LEN(userStr) = 2) THEN
        userInt = CVI(userStr)
      END IF

      IF (userInt) THEN
        SELECT CASE userInt
        CASE &H1B ' escape, abort game
          EXIT SUB
        CASE &H2B ' plus, place a flag or question mark
          IF (gNumClear) THEN
            fieldFlag plX + plY * gFieldW
          END IF
        CASE &H20, &HD  ' space (or enter,) reveal a tile
          ' First click, initialize mine field now
          IF (gNumClear = 0) THEN fieldInit plX + plY * gFieldW
          ' Reveal cells
          cleared = fieldReveal%(plX, plY)
          IF (cleared = -1) THEN
            gameOver = -1
            fieldRevealAll
          ELSE
            gNumClear = gNumClear + cleared
          END IF
        CASE &H4800 ' up arrow, move cursor up
          plY = plY + (plY > 0)
        CASE &H5000 ' down arrow, move cursor down
          plY = plY - (plY < gFieldH - 1)
        CASE &H4B00 ' left arrow, move cursor left
          plX = plX + (plX > 0)
        CASE &H4D00 ' right arrow, move cursor right
          plX = plX - (plX < gFieldW - 1)
        END SELECT

        ' Clear user input
        userInt = 0
        EXIT DO
      END IF
    LOOP
  LOOP
END SUB

''
'' DRAW THE WHOLE FIELD AT X,Y
''
SUB renderField (x AS INTEGER, y AS INTEGER)
  DIM ofsX AS INTEGER, ofsY AS INTEGER
  DIM cellOfs AS INTEGER, cellIndex AS INTEGER
  DIM digit(7) AS STRING

  ' Digit drawing codes (there can be up to 8 mines around)
  digit(0) = "c1 bm+0,1ed3gr2"     ' 1: blue
  digit(1) = "c2 rfg2dr2"          ' 2: green
  digit(2) = "c4 rfgfgl"           ' 3: red
  digit(3) = "c1 d2r2gd"           ' 4: blue
  digit(4) = "c4 bm+2,0l2d2rfgl"   ' 5: red
  digit(5) = "c3 bm+2,0lgd3r2u2l"  ' 6: cyan
  digit(6) = "c0 r2dgd2"           ' 7: black
  digit(7) = "c8 r2dg2dr2uh2"      ' 8: gray

  ' Draw tiles surface (light gray)
  LINE (x, y)-STEP(gFieldW * cellW - 1, gFieldH * cellH - 1), 7, BF

  ' For each row...
  FOR r% = 0 TO gFieldH - 1
    ' Get the drawing offset
    ofsY = y + r% * cellH
    ' Get the index of the 1st cell of the row
    cellOfs = r% * gFieldW
    ' For each column...
    FOR c% = 0 TO gFieldW - 1
      ' Get the drawing offset
      ofsX = x + c% * cellW
      ' Compute the full cell index
      cellIndex = cellOfs + c%
      ' If the cell is revealed...
      IF (gField(cellIndex) AND cStatReveal) THEN
        ' Get the counter value
        cnt = gField(cellIndex) AND CellCounterMask
        SELECT CASE cnt
        ' There are between 1 and 8 mines nearby, draw number
        CASE 1 TO 8
          DRAW "bm" + STR$(ofsX + cellHalfW - 2) + "," + STR$(ofsY + cellHalfH - 3) + digit(cnt - 1)
        ' The cell itself is a mine
        CASE 9
          CIRCLE (ofsX + cellHalfW - 1, ofsY + cellHalfH - 1), cellH \ 3, 0
          PAINT (ofsX + cellHalfW - 1, ofsY + cellHalfH - 1), 0
        END SELECT
      ' The cell is still covered...
      ELSE
        ' Draw emboss
        LINE (ofsX, ofsY + (cellH - 2))-STEP(0, -(cellH - 2)), 15
        LINE -STEP((cellW - 2), 0), 15
        LINE (ofsX + (cellW - 1), ofsY + 1)-STEP(0, (cellH - 2)), 8
        LINE -STEP(-(cellW - 2), 0), 8
        ' The player put a flag on it
        IF (gField(cellIndex) AND cStatClear) THEN
          DRAW "bm " + STR$(ofsX + 3) + "," + STR$(ofsY + 7) + " c0r2h1u4r1 c4r1h-1l2d1r1"
        ' The player put a question mark on it
        ELSEIF (gField(cellIndex) AND cStatMaybe) THEN
          DRAW "bm " + STR$(ofsX + 3) + "," + STR$(ofsY + 3) + " c0u1r3d1g2 bm+0,+2 r0"
        END IF
      END IF
    NEXT c%
  NEXT r%
END SUB

Have fun!

- Mike Hawk