Now that the game is out, I can finally talk about this!
My magnum opus:
Poop Sweeper is a faithful clone of Minesweeper1 in the pause menu of Goodboy Galaxy.
It has the following features:
- Persistent state (board remains intact when you navigate away from the app)
- Extremely low memory footprint (96 bytes of RAM while the app is closed)
- Supports flagging and 'chording'
- Status bar w/ cute animations
- Saves the player's best time and number of wins
This was really fun to make and I got to take a deep dive into Minesweeper mechanics while doing so, so I wanted to talk a bit about how I did it!
Recap!
Minesweeper is a game of logic and probability. There are a number of mines hidden on the board. The goal is to reveal all squares that don't have mines.
All the while, there's a timer counting up. The faster you win, the better!
You're doin' it! You're winnin' the video game!
Each turn, you reveal a square of your choice:
- If the square contains a mine, then you lose!
- If the square is touching one or more mines, it tells you how many mines it's touching.
- If the square isn't touching any mines, then all squares around it are revealed too.
- This happens recursively, so revealing a safe square in an ocean of safe squares can cause a large portion of the board to be revealed, akin to using the 'floodfill' tool in a painting program.
You can also 'flag' a square if you believe it contains a mine. The game then won't let you reveal it by accident. You can unflag it at any time.
If you lose, the game will reveal all the other mines on the field. The mine that killed you will be marked in red. Additionally, any incorrectly flagged squares will be marked by an 'X'.
Finally, there's a lesser-known technique known as chording. If you click an already-revealed numbered square and it's touching the correct number of flags, then the game will reveal all squares neighbouring it (except for the ones that were flagged). This is a neat time-saver, but it can kill you if you flagged any of the neighbours incorrectly.
Me losing by chording near a falsely flagged cell.
On PC versions of Minesweeper, chording requires you to click with both mouse buttons at the same time, which is probably why it's not well-known by casual players.
Data representation
The trick to having a small global memory footprint is to cram the state for each square into 1 byte.
To do this I used Nim's bitsize pragma, which corresponds to C's bitfield structs. I don't actually like these anymore2, would rather do bitwise ops on integers. But oh well, here we are.
type Square = object isMine {.bitsize:1.}: bool # there's a mine here isRevealed {.bitsize:1.}: bool # this square has been revealed isFlagged {.bitsize:1.}: bool # this square is flagged isDetonated {.bitsize:1.}: bool # colour us red (we killed the player) mineNeighbours {.bitsize:4.}: uint8 # how many mines are we touching GameState = enum gsFresh gsPlaying gsDead gsWon gsResetting MinesweeperBoard = object squares: array[BoardWidth * BoardHeight, Square] gameState: GameState gotNewRecord: bool gameTime: uint16 cursorPoint: Vec2i # position on the board of squares var board {.ewdata.}: MinesweeperBoard # declare the board (always in memory)
Each Square holds everything needed to draw itself correctly, which happens to be almost everything needed by the game logic too.
There's also a load of data used only while the app is actually open (dw about it too much!):
type SquarePos = object x {.bitsize:4.}: uint8 y {.bitsize:4.}: uint8 MinesweeperState = enum psInactive psBegin psCopyPopupTiles psReady psAnimateIn psShowing psAnimateOut psDone MinesweeperVars = object shouldHide: bool state: MinesweeperState nextTid: int transition: AppTransition squaresFlagged: int squaresRevealed: int pointsToCheck: List[BoardWidth * BoardHeight, SquarePos] # a stack for the floodfill squareObj: ObjAttr maxwell: Sprite cursor: Sprite timerWidget: TimerWidget cursorPressed: bool cursorPressRangeX: Slice[int] cursorPressRangeY: Slice[int] timeUntilReset: int resetWipeX: int resetWipeTicker: int messageTid: int messageTextBuffer: array[64, char] messageTextDirty: bool var vars: ptr MinesweeperVars # heap-allocated, uses no memory while app is closed
Ugly macro usage
To save keystrokes while working with all this game state, I use a macro called extract which I stole from PHP (my enemy!!). PHP's version takes a hash table and magically turns all the fields into local variables (at runtime! disgusting!)
My version is a bit different, and can be reasoned about statically:
extract(board) # now, let's pretend these fields extract(vars) # are all top-level variables!
It aliases all fields of an object, allowing e.g. squares as a shorthand for board.squares. Neatly this means I can heap-allocate MinesweeperVars without making the code any less readable.
The downside is I have to remember that vars could be nil, and the danger is hidden3 because it doesn't look like anything is being dereferenced.
Personally I think the footgun is worth it for the productivty boost, but ymmv. Rust programmers please don't kill me :')
Board utilities
squares is a 1D array that's intended to be treated as 2D, like squares[x + y*w]. I made some convenience procs to access a square by vector or by individual coordinates. These have a var return value, so you can mutate the board with them like get(x,y).isMine = true.
proc get(p: Vec2i): var Square = squares[p.x + p.y*BoardWidth] proc get(x, y: int): var Square = squares[x + y*BoardWidth]
Also, I commonly needed to act on all 8 neighbours of a square. This is more annoying than it sounds, because you have to consider the edges of the board too. I ended up with a template which substitutes the body of code 8 times...
While writing this post I realised an iterator would be a more idiomatic way to achieve the exact same thing, so let's pretend I did that instead:
iterator neighbours(x, y: int): tuple[nx, ny: int] = if x > 0: yield (x-1, y) if y > 0: yield (x, y-1) if x < BoardWidth-1: yield (x+1, y) if y < BoardHeight-1: yield (x, y+1) if x > 0 and y > 0: yield (x-1, y-1) if x < BoardWidth-1 and y > 0: yield (x+1, y-1) if x > 0 and y < BoardHeight-1: yield (x-1, y+1) if x < BoardWidth-1 and y < BoardHeight-1: yield (x+1, y+1)
Populating the board
When the player reveals their first square, it would suck if they immediately got a mine and game-overed. Also it'd be unfair if the first square was already neighbouring a mine.
Wow, this sucks!
For this reason, we wait for the player to make their first move before populating the board with mines. While placing mines, we pick random coordinates, but re-roll if we landed within the 3x3 area surrounding the first square. On later iterations it's also possible to pick a square that already has a mine, so we have to re-roll in that case too.
proc startGame(p: Vec2i) = reset(squares) # setup board: var count = 0 while count < NumMines: let x = rand(0, BoardWidth-1) let y = rand(0, BoardHeight-1) if not (x in p.x-1..p.x+1 and y in p.y-1..p.y+1) and not get(x, y).isMine: # Put a mine only if not near the starting square and not already a mine. get(x, y).isMine = true for nx, ny in neighbours(x, y): inc get(nx, ny).mineNeighbours inc count gameTime = 0 gameState = gsPlaying gotNewRecord = false squaresFlagged = 0 squaresRevealed = 0
The floodfill algorithm
When you reveal a square in Minesweeper, as long as that square is not neighbouring any mines, the game should recursively reveal all neighbouring squares.
Recursion is kinda expensive though! Fortunately, we have our 1st year Computer Science knowledge to fall back on: any time you have a recursive algorithm, you can rewrite it without recursion by using a loop and a stack4.
Here's it working in slow motion!
So first up, the stack, which I named pointsToCheck. It holds the coordinates of squares to be revealed (whose neighbours will then be added, and so on). As the board is only 14x6, you can use 4 bits per coordinate (see SquarePos further up), so it ends up very compact!
proc pushPoint(x, y: int) = var sp: SquarePos sp.x = x.uint8 sp.y = y.uint8 pointsToCheck.add(sp) proc pushPoint(p: Vec2i) = pushPoint(p.x, p.y) proc popPoint(): Vec2i = let sp = pointsToCheck[pointsToCheck.len-1] result.x = sp.x.int result.y = sp.y.int dec pointsToCheck.len
If you process all neighbours of a square, then all the neighbours' neighbours, you'll find many of them overlap. This is a problem! If you allow squares to be processed more than once, the algorithm will never end (until you eventually run out of stack space).
So a strategy is needed to ensure each square is only checked once. In my case I noticed isDetonated is never true for any square at this moment in the game5, so I aliased it to checking for this code only.
# repurpose `isDetonated` as a way to prevent a square # from being added twice to the floodfill. template checking(s: var Square | ptr Square): var bool = s.isDetonated template `checking=`(s: var Square | ptr Square, v: bool) = (s.isDetonated = v)
With that out the way, here's the code to reveal a square!
proc revealSquare(pos: Vec2i) = if get(pos).isMine: get(pos).isDetonated = true gameOver() else: # Floodfill pushPoint(pos) while pointsToCheck.len > 0: let p = popPoint() let s = addr get(p) if (not s.isMine) and (s.mineNeighbours == 0): for nx, ny in neighbours(p.x, p.y): let neighbour = addr get(nx, ny) if (not neighbour.isRevealed) and (not neighbour.checking): neighbour.checking = true pushPoint(nx, ny) if not s.isRevealed: inc squaresRevealed s.isRevealed = true # auto-remove false flags (this behaviour is like GNOME Mines) if s.isFlagged: s.isFlagged = false dec squaresFlagged for s in mitems(squares): if s.isMine: discard # keep mines marked as "detonated" else: s.checking = false
It basically just reveals whatever square is at the top of the stack, and if it's a blank square, adds all its neighbours to the stack. This is repeated until the stack is empty.
There are two discrepancies which I'll now explain.
Detonation hack
Right at the end, the checking flags are cleared in preparation for the next move.
I said isDetonated will never be true during a floodfill, but that turned out to be not quite right! Chording can cause more cells to be revealed after a mine was detonated.
Since checking uses the same bit as isDetonated, this meant there was a subtle visual bug where mines could become un-detonated. Luckily a mine can never be checking, so we can just not clear that bit for mines.
Auto-removal of false flags
Something not mentioned in any of my reading material was how the floodfill algorithm should interact with falsely-flagged squares. I tested in a few Minesweeper clones, and got different results in each:
I figured this would be worth asking a Minesweeper veteran about. I stumbled across the minesweepergame.com IRC channel on NewNet. Would anyone still be there?
exelotl (quassel@newnet-iis.p62.16.154.IP) has joined #minesweeper
Mode #minesweeper +nt by nyc.newnet.net
Channel #minesweeper created on 2022-05-29 17:54:30 UTC
<exelotl> hi!
<exelotl> I'm making a minesweeper clone, and was wondering if falsely flagged tiles are
supposed to become automatically unflagged if they get uncovered by the flood-
fill algorithm?
<exelotl> I've played 2 different games and each seems to handle this case differently
<aradesh> hi
<aradesh> they remain flagged and unopened
<aradesh> but the squares around it open
<aradesh> if you go to the minesweeper rankings website and to official clones
<aradesh> you'll see they all behave the same way
<exelotl> ah, thanks! yep that seems to be the most common behaviour by far
Yes, it turns out! There were people, and I got an answer within a couple of hours! Yay for IRC!
The verdict is, official Minesweeper games will never remove your flags, even if the flags are clearly wrong.
Ultimately I decided to ignore this rule and let the floodfill un-flag them, because spotting and removing them yourself is just busywork. Your speed is already hindered when playing on a GBA with a d-pad, so I figured it won't hurt to cut the player some slack here.
This behaviour also matches the Mines app available in my system package manager, so there you have it. Poop Sweeper may not be a 100% faithful Minesweeper clone but it is a faithful GNOME Mines clone. ;)
Player input
There's some nuance to the controls, the code isn't all that interesting but basically you have to wait until the player releases (A) before making the move. While (A) is held, the avatar in the top displays a 'thinking' face. If another button is pressed while holding (A), it cancels the move, so releasing (A) then does nothing.
For chording, I thought about requiring the player to press both (A)+(B), like on PC, but this felt unnecessarily obtuse.
Therefore, releasing (A) can cause 3 things to happen:
- if this is the first move, populate the board then reveal the square
- if the square is already revealed, attempt chording
- otherwise, just reveal the square
if gameState == gsFresh: startGame(cursorPoint) revealSquare(cursorPoint) else: let c = get(cursorPoint) if c.isRevealed: tryChording(cursorPoint) elif not get(cursorPoint).isFlagged: revealSquare(cursorPoint)
Rendering the board
I just used a hundred sprites, keep it simple. x)
Ok I'll elaborate: The GBA supports tilemaps, which could in principle work for a game like this. We use one for the backing board:
However, we can't easily use tiles for mines, numbers, etc. as GBA tiles are 8x8px, but our squares are 12x12px. There's a trick you can do with layering two maps slightly offset from each other to construct a map with 12x12px tiles. Puyo Pop does this (amazing game btw!), but it seemed like an overcomplicated solution here.
The GBA supports up to 128 sprites. Rendering the entire board requires 84 sprites, and a few more are needed for text labels and some other UI elements. It's tight, but we have just enough resources to pull it off!
Screenshot from NO$GBA showing the contents of OAM.
Each box corresponds to a single sprite on-screen.
Tile arrangement
in Obj-VRAM.
Finally, rendering the title and status bar text is done with Tonc Text Engine which expects you to prepare regions of the map to hold unique tiles. Here's an illustration of how the tiles are arranged:
How tile IDs are arranged for rendering text. (the unlabeled tiles have IDs too, but for
them it's ok if the same tile is reused multiple times, and their order doesn't matter)
Later in Goodboy development I made it possible to define these tile regions during asset conversion, so you don't have to deal with preparing the map at runtime (and can save a bit of VRAM in the process!). Unfortunately Poop Sweeper was too early to benefit from this change, but it's no big deal.
Chording
Aw yeah, finally the secret technique to becoming a Minesweeper pro.
Nothing happens, because we didn't put down the right number of flags...
Let's review the rules on chording:
- When you click a square with a number on it...
- If the number of flagged neighbours matches the number on the square
- Then the game should reveal all neighbouring squares (except for those flagged)
proc tryChording(p: Vec2i) = let c = addr get(p.x, p.y) # 1. Check that the tile is revealed and has a number on it. if c.isRevealed and c.mineNeighbours > 0: # 2. Verify number of flags == number of neighbours displayed. var numFlags = 0 for nx, ny in neighbours(p.x, p.y): if get(nx, ny).isFlagged: inc numFlags if numFlags == c.mineNeighbours.int: # 3. For each neighbour, force reveal it, as long as it's not flagged. for nx, ny in neighbours(p.x, p.y): if not get(nx, ny).isFlagged: revealSquare(vec2i(nx, ny))
There was another small bug here. As mentioned, I allowed the floodfill to uncover false flags. But you actually don't want that, if the false flag was the reason you lost - you wanna see where you went wrong!
To fix this, before revealing the neighbours, I record the positions of any neighbours that are flagged. Afterwards, if we lost, I set them to flagged just in case their flag got removed:
# Small workaround to preserve falsely-flagged tiles if we lost. var falseFlags: List[8, SquarePos] for nx, ny in neighbours(p.x, p.y): if get(nx, ny).isFlagged and not get(nx, ny).isMine: falseFlags.add SquarePos(x: nx.uint8, y: ny.uint8) # 3. For each neighbour, force reveal it, as long as it's not flagged. for nx, ny in neighbours(p.x, p.y): if not get(nx, ny).isFlagged: revealSquare(vec2i(nx, ny)) # Apply aforementioned workaround. if gameState == gsDead: for sp in falseFlags: get(sp.x.int, sp.y.int).isFlagged = true
One could argue I shouldn't allow any flags to be uncovered on the losing move. But this solution was good enough for me, so that's how it is!
Conclusion
I hope you enjoyed this deep dive into 1% of Goodboy Galaxy!
For the most part it's a game about exploring, shooting beasties and making friends, but we did our best to fill it with little surprises like this along the way x)
If that sounds like your cup of tea then please buy the game, tell your friends, and wishlist it on Steam, so we can keep doing more stuff like this!
Testimonials
Comment on the GBAdev Forums!
Footnotes
| [1] | Actually a faithful clone of GNOME Mines due to one subtlety which I'll explain later. |
| [2] | Compared to bitwise operators, C compilers aren't very good at optimising bitfields. Also, Nim has trouble getting the size of a bitfield struct at compile time. I could achieve readable code without these problems by using distinct types with getters/setters for each bit. |
| [3] | If you think this is terrible, maybe you wanna try Zig or Hare which go out of their way to ensure such spooky-action-at-a-distance is impossible. |
| [4] | After all, that's what recursion is — running the same code repeatedly while using the call stack to retain state from previous invocations. |
| [5] | The purpose of isDetonated is only to colour a mine red, to indicate it was the one that killed you. |