If you don’t know what Calliope is, please read this other post before continuing on.
Understanding the game
The first step I took in building the data model for Calliope was trying to figure out how a game was structured, keeping in mind that a game is meant to be played in real time by different persons on different machines, and that the whole state of the game must be persisted in order for a player to be able to shut the game and go back to it anytime.
Obviously there are two or more players taking part in a game, and the game itself can be split into turns in which players interact. But what are the building blocks of a turn? During a turn a player can pick letters from the sack to put them on his/her rack, move letters around (between his/her rack and the board), chat with the opponents, and pass the turn. Each of these steps must be recorded by the system in the current player’s machine, in order to be reproducible on the other connected machines. I decided to threat the above steps all in the same way and to call them actions.
A fundamentally right choice would have been to forget the turns separation, and to model a game just by a single stream of actions. By following and re-executing the actions from start to end, the current game state could have always been reconstructed. Performance-wise anyway, that would have been an error. Imagine a very long game, build up of several turns: that would mean tons of actions (thousands, maybe), tons of actions to reproduce in order to be able to reconstruct the game’s state. In the scenario we are considering this is not acceptable.
In order to avoid an eccessive accumulation of actions I decided to introduce in the model the ability to take snapshots of the game’s state along the way, to allow for a snappier state reconstruction (that is, the state itself can be persisted at a given time, so that only the actions taken after the snapshot must be re-executed to reach the current game state). I thought that the best way to model the game’s state was by means of the letters involved: every game is played using 128 letter tiles; at the beginning all letters are in the sack and from then on – after each action of the game – they move:
- on the board, in a specific position (which can be modelled as a 2D point);
- on someone’s rack.
By saving the position of every letter in the game I can take an exact snapshot of the game’s state. From this point of view even actions can be rethought: every action – except from chat messages and turn passing, which are threatened apart – can be thought of as a movement of a letter from one location to another (from sack to rack, from rack to board, etc.).
Now that I have a way to represent snapshots I just have to decide when to take them. I decided to go for the simplest solution, and to take one snapshot per turn.
To summarize:
A game is split into turns and played by two or more players; every turn is associated with a snapshot – which contains the position of letters at the beginning of the turn itself – and a set of actions – which tell what happened in the turn after the initial snapshot. To reconstruct the current game’s state one has to:
- fetch the last turn;
- read the snapshot and position letters accordingly;
- read the actions and re-execute them.
In a similar way, one can “travel” through the game starting from the first turn and reconstruct every single step that was taken.
The data model
After the game structure has been made clear, it was time to translate it to database tables. Here is an E/R showing the model:
The game entity is linked may-to-many to the players by a middle entity called game_player, which add the information of the play order (and other less important stuff). The relation between turn_letter and turn implements the snapshot feature seen in the description above: every turn has 128 associated turn_letters, specifying the location (attribute container) and ownership (attribute player_id) of every letter in the game, effectively saving the state of the game at the beginning of the turn.
The action entity has a reference to the turn it was executed in, as expected, and is also linked directly to the game.
The additional reference to the game has been added to account for what I call game-wide actions, that is: actions that are executed by a player during a game but are not related to any turn in particular. Chat messages are an example of game-wide actions.
In order to account for the maximum possible flexibility, an action has been modelled using a type – that can be any string describing the kind of action – and an attributes field. The attributes field is a CLOB, in which the system can store additional information necessary for the re-execution of the action, in whatever format (at current state attributes are stored as JSON).
There is another additional field in action: the pivot flag. The pivot flag has been added in order to identify those actions that must absolutely be re-executed in order to properly reconstruct the game state; the identification of pivotal actions adds a little awareness to the system that can be useful in certain situations (e.g. if a game is reloaded while a turn was in progress a large set of actions must be re-executed, to boost performance the system can discard all non-pivotal actions and execute only relevant ones).
Just to give you a more concrete view on this stuff, here are the type of actions that I’ve defined:
- “message” – a chat message, attributes contains just the string that was typed;
- “letter_drag_*” – letter drag related actions; there’s an action type for the beginning of the drag, one for the movement of the letter while dragging, one for successful drop and one for unsuccessfull drop; attributes contains the identifier of the letter that was dragged, its initial location (before the drag) and the current one;
- “turn_end” – issued when a player passes his/her turn, there’s always an action of this kind at the end of every turn.
