Videogames and Blockchains: Thoughts on performant state transition for multiplayer environments.

marco
marco
May 31 · 7 min read

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.

Image for post
Image for post
round based state transition with loads of time to finalise / https://unsplash.com/photos/w7lIbEtmE9c

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?

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.

Image for post
Image for post
state transition of a moon / https://unsplash.com/photos/NbgQfUvKFE0

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.

Image for post
Image for post
hypergraph / wolfram research

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.

Image for post
Image for post

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.

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.

Image for post
Image for post
building a Matryoshka blockchain with autonomous subchains

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

Image for post
Image for post

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?

Image for post
Image for post

Two separate states would not help much, therefore we need to match them in a way. Or just keep all in the same shard?

Image for post
Image for post
this looks like trouble ahead of time: PSI to the resque!

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 Yanais Decentralized Thoughts: Private Set Intersections article.

Further Reading

[1] https://www.sciencenews.org/article/stephen-wolfram-hypergraph-project-fundamental-theory-physics
[2]
https://en.wikipedia.org/wiki/Zero-knowledge_proof
[3]
https://substrate.dev/
[4]
https://medium.com/@edward.thomson/preventing-cheaters-in-fog-of-war-games-69f202fbe107
[5]
https://en.wikipedia.org/wiki/Intersection_(set_theory)
[6]
https://decentralizedthoughts.github.io/2020-03-29-private-set-intersection-a-soft-introduction/

marco

Written by

marco

strategy. technology + product architecture. future design + engineering. systems thinking. token economics. neuroscience. ceo lab75.jp one.io gamedao.co dfy.io

marco

Written by

marco

strategy. technology + product architecture. future design + engineering. systems thinking. token economics. neuroscience. ceo lab75.jp one.io gamedao.co dfy.io

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store