# A Game FIFO
Make sure you have all you need before proceeding:
In the previous step you added a way for players to reject a game. There are two ways for a game to advance through its lifecycle until its resolution, win or draw: play and reject.
# The why
What if a player never shows up again? Should a game remain in limbo forever?
You eventually want to let players wager on the outcome of games especially if value is tied up in games. You need to add a way for games to be forcibly resolved if a player stops responding.
The simplest mechanism to expire a game is to use a deadline. If the deadline is reached, then the game is forcibly terminated and expires. The deadline is pushed further back every time a game is played.
To enforce the termination it is a good idea to use the
EndBlock part of the ABCI protocol. The call
EndBlock is triggered when all transactions of the block are delivered and gives you a chance to do some tidying up before the block is sealed. In your case, all games that have reached their deadline will be terminated.
How do you find all the games that reached their deadline? Maybe with a pseudo-code like:
This approach is expensive in terms of computation. The
EndBlock code should not have to pull up all games out of the storage just to find the dozen that are relevant. Doing a
O(n) (opens new window), where
n is the total number of games.
# The how
You need another data structure. The simplest one is a First-In-First-Out (FIFO) that is constantly updated so that:
- The just played games are taken out of where they are and sent to the tail.
- The games that have not been played for the longest time eventually end up at the head.
You keep dealing with the expired games that are at the head of the FIFO when terminating expired games in
EndBlock. Do not stop until the head includes an ongoing game. The cost is:
O(1)on each game creation and gameplay.
kis the number of expired games on each block.
k <= n
k still is an unbounded number of operations. But if you use the same expiration duration on each game, for
k games to expire together in a block, these
k games would all have to have had a move in the same previous block. Give or take the block before or after. The largest
EndBlock computation will be proportional to the largest regular block in the past in the worst case. This is a reasonable risk to take.
Remember this only works if the expiration duration is the same for all games instead of being a parameter left to a potentially malicious game creator.
# New information
How do you implement a FIFO from which you extract elements at random positions? Choose a doubly-linked list for that:
You need to remember the game ID at the head, to pick expired games, and at the tail, to send back fresh games. The existing
NextGameobject is a good place for this as it is already an object and expandable. Just add a bit to its Protobuf declaration:
To make extraction possible each game needs to know which other game takes place before it in the FIFO, and which after. The right place to store this double link information is
StoredGame. Thus, you add them in the game's Protobuf declaration:
There needs to be an "ID" that indicates no game. Let's use
"-1", which you save as a constant:
Adjust the default genesis values, so that it has proper head and tail:
To have Starport and Protobuf recompile the files:
# FIFO management
Now that the new fields are created, you need to update them accordingly to keep your FIFO always up-to-date. It's better to create a separate file that encapsulates this knowledge. Create
A function to remove from the FIFO:
The game passed as an argument is not saved in storage here, even if it was updated. Only its fields in memory are adjusted. The before and after games are saved in storage. It is advised to do a
SetStoredGameafter calling this function to avoid having a mix of saves and memory states. The same applies to
A function to send to the tail:
# Use it
With these functions ready, it is time to use them in the message handlers.
In the handler when creating a new game, send the new game to the tail because it is freshly created:
In the handler when playing a move, send the game back to the tail because it was freshly updated:
In the handler when rejecting a game, remove the game from the FIFO:
You implemented a FIFO that is updated but never really used.
# Next up
Now you need to add an expiry date on the games. That's the goal of the next section.