0

Let's say you have a multiplayer game where different player threads are constantly updating the same game state. How do you best update this state without suffering locking bottlenecks or corrupting the game state?

I'm thinking non-blocking data structures like AtomicInteger, AtomicReference, etc. Would that be correct and if so am I leaving anything out? If not, then what? Thanks!

  • 8
    You could strongly consider a message passing design where all incoming changes are submitted via a queue. Otherwise, even with Atomics, there will be a lot of criss-crossed state changes. – user949300 Oct 29 '17 at 5:53
  • @user949300 Couldn't that lead to delays in changing the state though? – Wes Oct 29 '17 at 15:46
  • 4
    @Wes - in a distributed system that undergoes mutation you can never assume that all nodes will have the same state. When building such an application, you must start from that expectation and design the system to compensate for imperfect knowledge. – kdgregory Oct 29 '17 at 18:01
  • @kdgregory I agree with this. Ideally you would never, say, communicate to the server that you shot a player, but rather, that you shot in a particular direction. The server then communicates to the client that that player was hit. Of course sometimes a client will make reasonable assumptions to show immediate updates, but it may not always be correct. – Neil Dec 21 '17 at 14:24
2

The problem you'll have using things like AtomicInteger is that the game state is going to require multiple values, many of which could need updating as a result of a given player action.

So while you can be confident that each individual state value won't be corrupted, it's still possible for the overall state of the game to get completely fouled up if several threads are updating multiple state variables at the same time.

0

Let's say you have a multiplayer game where different player threads are constantly updating the same game state. How do you best update this state without suffering locking bottlenecks or corrupting the game state?

One possible answer is to treat the updates from the competing players as events, rather than directly manipulations of the game state. The player events get appended into a queue, and the "game state" thread pulls the events off the queue in order to determine the state of the game.

Trisha Gee wrote a bunch of essays about Disruptor and the LMAX architecture; disruptor being a lock free design for a queue that might be used in this way. An interesting design choice in disruptor is that it supports reading events in batches.

If the shared work approach isn't satisfactory, then an alternative to consider is AtomicReference, which gives you compare and swap semantics on a root object, and therefore on the references reach able from that root reference. The core pattern looks like

V currentState = reference.get()
V nextState = computeNewState(currentState)

if (reference.compareAndSet(currentState, nextState) {
    // Success: you have updated the shared state!
} else {
    // you lost the data race
}
  • Using a queue of game events is a very common approach in multiplayer games. You also get a few speedups for free that might be helpful, e.g. if a player starts moving in one direction and then changes their mind before the original event is processed, you can just drop it from the queue and replace it with the new one. You can also use queue length as a trigger to reduce accuracy in simulations, etc. See, for example, the architecture used by EVE Online, which has servers running on single machines, not distributed, that are able to support battles involving over 5,000 players. – Jules Dec 22 '17 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.