Storing Minesweeper Games efficiently

Storing the game

To store the game, a balance between storage and CPU time has to be found. Here I choose to focus on less storage used and therefor more CPU time while reading / parsing the data.

Therefore, storing the mines seems like the most reasonable solution, since by just using the mines it's possible to calculate all needed fields around them with two simple loops. Of course, a field also always has an attached height (Y) and width (X). These meta information about the field will be stored too.

All of this here has been written with two assumptions:

1. That the game has to be stored with a small storage footprint and

2. That the game will be stored and transmitted via a string with ASCII chars only

Before we can start with the storing of actual Minesweeper Data, we first have to look into how to encode the coordinates efficient, since they will be the most utilized.

The first Idea that comes to mind is doing something like [X]x[Y] combined with a special char as a separator. This, however, does contain more chars and therefor unnecessary data than we require, at least for the most cases. To reduce the data used, we first can use a different base for our numbering system. Instead of base 10 we can use base62, that leaves us with all the special chars to use for other things but also allows us to reduce all numbers between 10 and 62 to just a single character.

Nevertheless, we still have a separator at the end of each coordinate and a char in between the x and y value. However, if we just have a single char for most fields and the most common sizes, we can just drop these two special chars and just keep the two chars from our base62. Most coordinates can then just be stored with two chars. An example would be the following:

Let's assume we want to encode the coordinates: 2×10 3×5 5×7 10×15 and 15×23,

With the first idea, we would encode them like the following: 2x10;3x5;5x7;10x15;15x23 which seems quite wasteful. The optimized design allows us to reduce it to just 2A3557AFFN.

Of course, this will not work for coordinates bigger than 62. What to do in a case like that?

Just come back to the original idea and optimize as far as we can. So, we will store these coordinates with a char in between the X and Y values. So even though it uses an additional char, it is okay since this encoding will exclusively be used for coordinates above 62 and can be combined with the other coordinates.

(We could also use a higher and higher base with more chars to use, but here I want to focus on ASCII only.)

Both These coordinates' storage ideas, we can now combine by using a separator. I decided on a semicolon for this case.

An extended example of the above-mentioned coordinates would therefor look like this:

2A3557AFFN;12|1B;20|BB;Fzg3;11|13

As you can see, we can combine these too ideas thanks to the separator, and it is also infinity scalable, we don't have to worry about larger fields anytime. Furthermore, note that a | was used instead of an x. This is the case since all the letters are already in use for the possible coordinates, which might result in a problem if we do not replace it with a special character.

A single (mine) coordinate will therefor be stored like the following

If the X and Y coordinate can be encoded in just a single char:

[X Cord][Y Cord]

If, however, just one of the coordinates is longer than one char, we use the following:

;[X Cord]|[Y Cord];

(Replace the square brackets with the corresponding value)

These can be stringed together indefinitely. The last semicolon (;) has to be removed, as well as all double semicolons (;;) if two coordinates with the second format are back to back.

Meta information about the minesweeper field are only the X and Y size, so we can simply combine them via a single char and put them into the meta section of the string.

Sorting the meta information will be done in the following way

[X Size]x[Y Size]

(Replace the square brackets with the corresponding number)

Only one meta information block is allowed, and that has to be at the start of the string.

To allow for further refinements in the future, we might also want to add a versions number that allows us to know how we have to parse a string. These version number can be any char or sequence of chars. It will be at the very start of every string and has to be separated by the rest of the sting with an equals char (=).

Combining the mines and the meta information and the version

1=[Meta Information]+[Mines]

(Replace the square brackets with the corresponding string from above)

Notice the plus, (+) which we use to separate any block of data from another.

At the end, a small Minesweeper Game might look like this in this storage format:

1=5x6+2223444554

Storing the player interactions

Coming up next, we want to store a) the fields the player opened and b) the flags the player placed / removed.

Let's start with storing the fields the player opened. Of course, we do not need to store every field that opened up after a player clicked on a field. It's more than enough to just store the coordinates of the field the player clicked on. Since we already have the whole board (We can generate it from the metadata and the mine coordinates from above) we can then also simulate the field after each click on the board.

Storing the player interactions

If the player opened a field, we foremost store the coordinates of it. To accomplish that, we will use the same coordinate system from above, which we also used for storing mines. However, we will also include the time delta since the last action of the player. This will just be added behind the coordinates:

[Coordinates][Time Delta]; OR [Coordinates]:[Time Delta];

Notice how there is no divider between both values, for the first example, this is because we can safely ignore it in case the coordinates are just two characters longs. We can easily parse the data without it, since the only variable length is the end. If, however, the coordinates are longer than two characters, there has to be a colon (:) as a divider.

I should also mention that the coordinates used here do NOT contain a semicolon. They closely follow the format from above, but this is a crucial difference. E.g. ;[X Cord]|[Y Cord]; would equal [X Cord]|[Y Cord] for storing player interactions.

And we now also want to store the player flag interactions similarly. For that, we just copy the click interaction format and add one letter at then end to indicate a placed or removed flag. Let's see how our example from above would change:

[Coordinates][Time Delta][Flag Action]; OR [Coordinates]:[Time Delta][Flag Action];

Again, we can omit the divider between the flag action and the time delta for the first type since we can first parse the coordinates and the flag action which all have a fixed length and then parse the time afterward without any issue.

Example

If all of this is applied to an actual game, it might look something like this at the end:

1=15x15+90E2E3A445556575D506C65797D71848D89A0B1BAB5CAD4E7EBEEE+000;5840;594;5A7;5B5;5C7;6B1;698;685;674;7A14;795+5419P;554P;563P;574P;4A16P

From the metadata, we can see it's a 15×15 game board.

We can split it at the plus to see that the first part is the whole game board: 90E2E3A445556575D506C65797D71848D89A0B1BAB5CAD4E7EBEEE

Split it at the second plus to view all player click actions:

000;5840;594;5A7;5B5;5C7;6B1;698;685;674;7A14;795

And split it at the plus to see all placed and removed flags:

5419P;554P;563P;574P;4A16P

All of this put together, it can generate a recording of the game like the following: https://i.imgur.com/AuAd4en.gif

Possible optimizations for version 2

• Allow for a flexible base in the metadata.

  • This would allow for considerable saving of data if boards larger than 62 are stored. It, however, could also lead to problems since the encoding scheme has to be specified beforehand.

• Remove the letter when placing a flag, and only keep the one for removing a flag.

  • Relatively easy to do, however, since the saving is miniscule in comparison to the whole data stored, and it would complicate the parsing of the data I decided against this – for now.

• Allow just storing the field and omitting the player interactions.

  • Well, for this, it can already kind of be done with the current version since it doesn't require the player interactions. Nevertheless, it leaves two trailing pluses at the end of the text, which isn't too desirable.