Before starting this project i had a quick sparring session with one of my best friends. He’s an incredible smart guy and i love just talking about random technical problems with him because he always has some insights for me that i hadn’t considered yet.

Check him out Here

During this sparring session we listed up some of the initial obvious issues i’d run into.

Chunking

The initial idea of chunking the field so we can load localized section of the infinite field seems like a good idea. We can then use bitpacking techniques to store the actual field information

We discussed the option of storing the infinite plane as a bitmap and allow us to index the field by layering a quadtree on top of the bitmap. This seemed like a good idea but after some though it seemed like this would not improve upon the initial more naive implementation.

A simpler option is to create a bitmap per chunk on disk and fetch and process the image file that corresponds with the currently accessed chunk. Something along the lines of chunk_12_73.bmp When accessing the chunk on coordinates x=12, y=73.

Alternatively we could assign the bitstring associated with the field in the database record of the chunk.

Bitmaps

Since each value of the field is a value between 0 and 8 we can store the full chunk in a grayscaled bitmap where each pixel value indicates the number in that cell. This would make each cell a 4 bit number The only think we are missing from the chunk are the flags, mines and the state of each individual cell.

Flags

We can’t really add the flag positions in the bitmap because we have a potential large amount of players placing down flags, and we would like to denote which player placed a flag. So instead of putting the flags in cell positions we would keep a list of all flag positions with a reference to the user that placed it.

Mines

Here are the ratios of mines in the classic Microsoft minesweeper
| | x | y | mines | ratio |
|————–|—-|—-|——-|——-|
| beginner | 9 | 9 | 10 | 0.12 |
| intermediate | 16 | 16 | 40 | 0.15 |
| expert | 30 | 16 | 99 | 0.20 |
On a field of 128x128 cells we would have about 3500 mines. Storing the position of a single mine would cost 14 bits (7 for x and 7 for y position) storing them all would require roughly 46000 bits. = 5735 bytes = 6Kb just to store the bomb positions in the chunk

Alternatively we can store the positions in a single bitstring 128x128 bits long. This would require 16384 bits = 2048 bytes = 2Kb This improves storage slightly

Open state

Since open or closed is a simple binary flag we could store a single bitstring in the chunk model denoting which cells have been opened

Similar to the mines we could store a single bitstring of 128x128 long requiring an additional 2Kb

In total this would yield a 4bit number per cell To indicate the value of each cell (0-8) = 65536bits = 8192Bytes = 8Kb
An additional bitstring for the mines = 2Kb
An additional bitstring for the opened states = 2Kb

In total storing a full 128x128 chunk with all data would require 12Kb of data.

If we store everything as stated here we have all flag positions (and their owners), the state and actual number in each cell. To render the full chunk we could first load the bitmap and fill in all numbers. Then find all flags relevant to the positions in the chunk and add them to the field. Then get the open state and make the necessary visual changes.

Active vs inactive chunks

Although the bitmap makes the lookup of a certain cell’s value O(1) storing the complete bitmap for each visited chunk is a lot more information than is needed. We can simply store the position of each of the mines in a chunk and calculate the values of each cell on the fly. This would reduce the total space needed for each chunk to a list of mine positions and opened cell positions. Going from 14KB per chunk to 4Kb. A significant improvement

However calculating the number of a given cell each time a user clicks it puts a lot of computational stress on the server. So instead we could keep a flag on each of the chunks to determine if this chunk is active, (there is a user nearby playing around it) or inactive (there are no users playing in this chunk’s vicinity.

If we have an active chunk we could generate the full bitmap and store it. Then calculating the value of a cell would be a simple lookup. If the chunk is inactive there is no need to keep the full bitmap stored and we can remove this data keeping only the mine positions instead.