There are several approaches to implementing multiplayer in a game. The approaches can also be mixed/matched to precisely satisfy your requirements.

Basics

The central idea behind multiplayer is that all players should have the same game state at all times. This is what we mean when we say that all clients should be synced.

Furthermore, you should prevent any client from cheating by messing with packets sent over the network.

These are the two main goals of multiplayer.

Basic Naive Approach

Let’s just take a stab at how we would approach this, and then iteratively refine it.

Let’s make the server be the official (source of truth) game state. The clients simply collect inputs and send them to the server, and they always render the current state of the server.

sequenceDiagram
    participant Client
    participant Server
    
    loop Every frame
        Client->>Server: Send inputs
        Client->>Client: Render current game state
    end
    loop Every frame
        Server->>Server: Process inputs and update game state
        Server->>Client: Send updated game state
    end

The good thing about this approach is that since the server is the ultimate source of game state truth, even if clients try to cheat by sending fake inputs, the server can just ignore them or kick them out. So this “authoritative server” approach is a good way to prevent cheating.

However, we currently have some major performance issues.

  • First, there is a large amount of latency from when the client takes an action, to when it gets to the server, to when the server sends back the updated game state. That means there could be ~100-200ms of lag from when you press a button to when you see your character move.
  • Second, the server is sending back the entire game state every frame. This is a lot of data to send over the network, and the larger your game state, the worse it gets.

Don’t Send Entire Game State

Instead of sending the entire game state every frame, we can just send the changes (deltas) in the game state since the last update. This means that the server now has to keep track of what has changed since the last update. A simple approach is to mark an entity/component as dirty whenever it changes, and only re-send the dirty entities/components. You can even go further and only send the changes in the components that have changed. After you send an update, mark all entities/components as clean. You can have this dirty flag be part of the component itself, or you can have a separate dirty list.

flowchart TD
    C[Update game state]
    C --> D{Entity/Component changed?}
    D -- Yes --> E[Move to dirty list]
    D -- No --> F[Do nothing]
    E --> G[Send dirty list to client]
    G --> I[Clear dirty list]

Client Side Prediction/Server Reconciliation

The latency issue (time from when client takes an action to when he/she sees the result) can be mitigated by using what is known as client-side prediction. The idea is that the client can predict what the server will do, and update its local game state accordingly. So from the perspective of the player, it is responsive because he/she can see the result of his/her actions immediately. The server will eventually send the authoritative game state, and the client can “reconcile”.

Now we must discuss the concept of a tick. Our game/simulation runs at a certain number of ticks per second. This is different from the rendering frames per second. A simulation tick consists of:

  • Processing inputs queued for that tick
  • Updating the game state

When the client gets game state from the server, the game state will have a timestamp in the for of a tick number. The client will compare that game state, for say tick t, with its own game state at tick t (at tick t, not currently). If the client’s game state at tick t was the same as the server’s game state at tick t, then the client’s prediction was correct. If not, the client needs to roll back game state to tick t, and reapply all the inputs from tick t to the current tick. Note, this means the client needs to store a couple of previous game states, as well as the inputs for a couple of previous ticks.

Here’s a sequence diagram showing client-side prediction and server reconciliation:

sequenceDiagram
    participant Client
    participant Server

    loop Every Frame (Client Rendering)
        Client->>Client: Render current game state
    end

    loop On Input (Client)
        Client->>Client: Predict local game state based on input
        Client->>Server: Send input to server (immediately)
    end

    loop Periodically (Server)
        Server->>Server: Process inputs and update authoritative game state
        Server->>Client: Send delta (changes) in authoritative game state (with tick number t)
    end

    Client->>Client: Compare state predicted at tick t with authoritative state
    alt Predicted state matches authoritative state
        Client->>Client: No reconciliation needed
    else Predicted state does not match authoritative state
        Client->>Client: Rollback to authoritative state (tick t)
        Client->>Client: Reapply inputs from tick t to current tick
    end

And here’s a state diagram depicting the client reconciliation process:

stateDiagram
    [*] --> Current
    Current --> Reconciled: Predicted state at t did match authoritative state at t
    Current --> Rollback: Predicted state at t did not match authoritative state at t
    Rollback --> Reconciled: Reapplied inputs from tick t to current tick
    Reconciled --> [*]

Deterministic Simulation

So, what this means is that the game/simulation is deterministic. A deterministic simulation means that if you start at some state at tick t, and you apply a certain set of inputs, you will always end up at the same state at tick t+1.

This means that as long as you record inputs for ticks (just a few past ticks), you can go back to the previous state associated with a tick, apply all the inputs of ticks since then, and you will end up back at the current state.

So, the state is only a function of a tick. A tick is just a number and a sequence of inputs.

Where:

  • is the state at tick t+1
  • is the state at tick t
  • is the input at tick t
graph LR
    A[State at tick t] --> B[Apply inputs I_t]
    B --> C[State at tick t+1]

Lag Compensation

When you have a deterministic simulation, you can do some cool things. For example, if the server knows that at some tick in the past, tick t-3, the player shot in a particular direction, the server can rewind the game state to tick t-3, and see what the bullet hit at that time. If it was another player, the server can then apply the change to the current game state. This is known as lag compensation.

graph TD
    A[Player shoots at tick t-3] --> B[Server gets the event at tick t]
    B --> C[Server rewinds game state to tick t-3]
    C --> D[Server sees what the bullet hit at tick t-3]
    D --> E[Server goes back to tick t]
    E --> F[Server applies change to current game state]

Here’s a state diagram of the server when the client shoots at tick t-3:

stateDiagram
    [*] --> TickT
    TickT --> RewindToTMinus3: Server gets the t-3 event
    RewindToTMinus3 --> TickT: Server checks what the bullet hit at tick t-3

    note right of TickT
        Server applies change to current game state
    end note

Interpolation

Often, the server only sends game states at a certain rate, say 20 times per second. In order to prevent a choppy experience, clients have to save a few previous game states, and interpolate between them constantly.

Lockstep

The lockstep approach is a way to ensure that all clients are in sync. The idea is that all clients must agree on the game state at tick t before they can move on to tick t+1. This means that if one client is lagging behind, all clients must wait for that client to catch up.

For ever tick, all clients must receive the inputs of all other clients before they can process the tick and move on to the next tick.

You can put in a server as one of the clients and use that as an “authority” of some sorts to prevent cheating. It is the source of truth for the game state.

The kind of inputs you send in lockstep are such as:

  • Player 1 built a barracks at position x,y
  • Player 2 moved unit 3 to position x,y
  • etc

Every player gets all the inputs from all other players, and every client processes the inputs in the same order. Since all clients are running the same simulation, and they process the same inputs in the same order, they will end up in the same state at the end of the tick!

sequenceDiagram
    participant Client1
    participant Client2
    participant Client3
    participant Server

    loop Every Tick
        Client1->>Server: Send input
        Client2->>Server: Send input
        Client3->>Server: Send input
        Server->>Client1: Send all inputs
        Server->>Client2: Send all inputs
        Server->>Client3: Send all inputs
        Client1->>Client1: Process inputs
        Client2->>Client2: Process inputs
        Client3->>Client3: Process inputs
    end