Videogames and Blockchains: Thoughts on performant state transition for multiplayer environments.
These are more or less notes from the past which I recompiled and want to use to encourage discussion. Feel free to give it some roasting, it is not meant to stand like this forever ever.
In traditional multiplayer network games, a certain amount of players can compete with each other as well as interact with the environment. Central databases serve the single source of truth to clients and depending on the type of game this results in games being hard on the client, the server, the network or all of them.
For example a “turn based” game is not only perceived different but also has different implications to networking and state updates in comparison to a shooter, like Battlefield, Call of Duty or Fortnite with 100 players competing in realtime.
Talking decentralisation, people might ask, how good ( fast / safe ) can a blockchain protocol become, where does it make sense to use it, or what kind of new game models and economies can be invented based on a distributed state?
Obviously fungibility of assets is one intriguing aspect, representing scarce items as NFT (non fungible token) or an in game credit system with an internal token based currency. Good topics for a future discussion.
Distributed state can offer a lot of advantages when done right. A perfect notary system to collect a record of ingame actions. Tamper proof results. Or similar aspects to our perceived reality can be represented, as well: If you die you die. A perfect simulation?
Our universe is a big state machine, too.
If you walk across the street you are moving in an environment with more or less complex features. Trees. The road. Birds. Pedestrians walking around. A car passing by. In this perceived state you experience continuous transition of uncountable changes, as you are part of it. But your perception is usually focussed on something. A task you want to complete, or something you saw yesterday which gave you food for thought.
Depending on your task, a lot of parameters vary. Perceived space, audio, field of vision, your neighbour passing by and you don’t recognise him at first as your mind is drifting away.
You can describe this, getting into more details, or the opposite: Come to a meta top down perspective which gives you room to see different things in relation on a macro level.
“A computer visualization depicts a “hypergraph” consisting of relationships between points constructed by repeatedly applying a simple rule for expanding, or “updating,” the network. Stephen Wolfram believes a massively complex hypergraph could represent all of physical space and its contents, a clue to finding the fundamental theory of physics.” — sciencenews.org
In Computer Science there are many ways to represent parts of all of this perception in one way or the other. What I am trying to discuss here, with you, is, the question:
To what extent can a blockchain or a distributed statemachine be used to efficiently represent state and its dynamics, based on typical tasks in videogames?
Let us jump straight into the first two aspects.
Time and Complexity of State: Turn based vs Realtime Games
From my point of view, there is no such thing as Realtime, there is no real differentiation to turn based models, besides the tick size: The available time to finalise a block on chain.
This depends on efficiency of the state transition function applied to the complexity of state being mutated. Or the other way around: What information is neccessary to represent your game environment in an adequate amount of time.
At the end you can think of it as a graph structure and individual actors mutate the state through their behaviour. Of course state for a multiplayer shooter has other implications than a game of Poker.
With n=1024 concurrent players ( actors ) x 1KB payload (state) would require a blocksize of roughly 1MB,
in sync over n nodes participating.
For true decentralisation an actor would also provide a peer to peer node syncing, representing state and distributing mutations. Somebody would have to validate, sync and render all of this — yes, mostly random numbers — in 0.01s. Not for the faint of heart.
Transaction and computation speed with a level over 9000 will be hard to chew for the average blockchain.
Therefore the required state needs to be super efficient. That is, why they use e.g. UDP streams in HFT, but how to reflect this with a state of variable density and async state transition?
Into the Realm
How can we balance pressure on state transition, manage complexity, improve speed? If you look at existing MMO games, a variety of methods help overcome bandwith issues, easier things like loadbalancing with clusters, routing users to certain geolocations and optimising matchmaking to cluster IPs in the neighbourhood.
These simple tools do not really apply if you go full decentralised, as you are not in possession and control of the machines providing the single source of truth: It is a distributed state. The truth is reflected by network consensus.
So what are the possibilities to reduce the individual state to update? Usually it is not necessary for all players to persist the complete gamestate of all players currently active in the respective universe / battlefield / level.
A common technique is, to split larger spaces into smaller ones, so individual players only need to sync the state of the sector they are currently active in. This helps us in improving on block time and size at the same time, nice.
Depending on the activity of the player, we are able to cache or preload surrounding sectors. We have to decide, though, what kind of precision is necessary for e.g. coordinates in space.
Items closer to a player need higher precision and shorter tick sizes. Imagine a projectile flying over various sectors towards the battery of player P. Do we need e.g. high precision when the projectile is three tiles away? No. Only when close to the player. But when the projectile is close and e.g. ticksize and precision are too big, you might miss the battery even though the shot was perfectly fine.
Fog of War and the Enemy
Another concept tying in to the previous thoughts is Fog of War. Limiting the field of view of a player not only reduces bandwidth manifold but even helps to improve the game experience: Imagine a party of Chess with Fog of War :).
While the player is not moving, the visible area could look like this. Darker areas equal less precision.
For the Player and his respective enemies it might look something like the following. Bonus question: Could they live in separate shards or is this too inefficient?
Two separate states would not help much, therefore we need to match them in a way. Or just keep all in the same shard?
Fog of War and Encryption
With all of this comes another problem along the road: How can we know, if there is another state in our shard which might interact with ours, without exposing all individual states?
Through FoW and FoV we already know neighbouring shards and fields in the area, therefore we are able to calculate proofs automagically in each area, reflecting either a probability or a cryptographic proof of existence (maybe Zero Knowledge Proof) of a select entity. Like this, the state transition function could merge relevant state and make mutations accessible to the player state.
Good introductory reads are Edward A Thomson’s Preventing cheaters in Fog of War Games, where he discusses the concept of Private Set Intersections (PSI) which are one solution to identify intersecting state without exposure of non related, critical state and Avishay Yanai’s Decentralized Thoughts: Private Set Intersections article.