A concurrent minesweeper web game
A web based minesweeper game. It can create boards of n x m sizes (n and m are integers larger then 0 and smaller or equal than 100). A player can create private or public games and solve the mine sweeping with a friend. Games are saved upon interaction and can be resumed.
Using a unique name and a password, the user can start creating games or join public games.
A game defines whether a game is public or not, when it was started, which player is the creator and whether it has finished or not and what was the end result. Also it contains the amount of mines and the board size.
A game board 2D points (game map) contains all the points in space for a game and a mine_proximity value associated.
The mine_proximity value is an integer that describes the state of a point in space. To interpret that number there are certain rules:
With this in mind you can define the minesweep algebra:
Let:
mine_proximity.By defining the minesweep algebra, you can define a minesweep game as a game state that has been applied a finite amount of operations that can be composed until you calculate the current game state.
The minesweep algebra has several advantages:
It only has one disadvantage
The application is basically a REST API that validates and executes operations of the minesweep algebra on a game state, such validations are:
If the operation is valid it will always result in a board change unless the reveal operation is performed on an already revealed field. This is important when taking into account multiple users.
Upon connecting to a game, the player receives the game state and starts receiving operations to update the local game state.
The synchronization strategy between players is optimistic, applying OT to keep the local and server game state synchronized. The operations to be transformed are the defined in the minesweep algebra.
For each operation sent and received there is an operation id attached. Such id increases with each operation and it allows the client and the server to know whether they are synchronized, if the server notices that there is a client sending an operation with an already taken operation id, it can send back all the operations that the client has missed plus it can apply the operation without forcing the client to re-send the operation.
The server must not give away any more information than the revealed 2D points, the board size, the amount of mines and the first operation date (this last value is used to calculate the time spent playing). The whole board cannot be stored in the client because it would allow cheaters to read the board and know where the mines are, that is why clients only receive the points already revealed. Only when the game has finished the server can send all the board to the clients.
Clients are authenticated using a JWT token that expires on 15 minutes (without any token blacklist). Client’s Passwords are hashed using bcrypt.
Clients will send operations to the server via websockets or a REST API.
One of the aims of this project is to benchmark which data modeling approach works best. There are two ways of modeling the game board, normalized and denormalized.
The normalized approach stores every 2D point of the game board as a row in the game_board_points table. This is standard relational modeling and it is guarantee to work.
The denormalized approach stores every 2D point of the game board in a matrix inside the games table. No subquery is needed to retrieve the game board and the data is easily mapped into the application.
I have certain hypothesis:
mine_proximity of a single point.Are my hypothesis correct? I don’t know, but I can quickly benchmark this.
Chech the full benchmarks in the branch jl/game-benchmark
Storing the game board with array
10000 3775875 ns/op 546135 B/op 281 allocs/op
Storing the game board in the normalized structure
10 190661383 ns/op 3972940 B/op 50126 allocs/op
Storing the game board denormalized significantly improves storing the game board for the first time (game creation).
Retrieving a single game board row column with the denormalized approach
1000 2034873 ns/op 1227521 B/op 10101 allocs/op
Retrieving a single game row column with the normalized approach
10000 177058 ns/op 3324 B/op 68 allocs/op
It is clear that accessing a single row, column is way faster and requires much less allocations than the denormalized approach.
Updating a single row column in the denormalized approach
300 4154761 ns/op 1226859 B/op 9955 allocs/op
Updating a single row column in the normalized approach
1000 1636261 ns/op 2326 B/op 54 allocs/op
Updating a single row column in the normalized approach is way faster as well and requires much less allocations than the denormalized approach.
While game creation is incredibly fast with the array approach, retrieving and updating a single value is significantly slower and performs too much allocations. Even though the allocations issue could be improved, it would require to start making weird queries that would be more error prone and (obviosly) would mean leaving relational rules behind.
If I have to choose between faster game creations or faster game update, I choose the later thus concluding that the denormalized approach is discarded and I don’t think that attempting to improve updates with arrays is going to pay off.