Verzögerungen in Online-Spielen durch Client-Side Prediction kompensieren

29.08.2014 09:13 Uhr Christian Oeing

Viele Online-Spiele setzen auf schnelle Interaktionen. Hinter den Kulissen sind dafür große Datenmengen zu befördern, was zu Verzögerungen führen kann. Damit sie Spieler nicht um den Sieg bringen, gibt es Mechanismen, die Latenzen verbergen.

Verzögerungen in Online-Spielen durch Client-Side Prediction kompensieren

In Multiplayer-Spielen kommt es durch die verteilte Ausführung der Spiele auf Clients und einem zentralen Server gezwungenermaßen zu Verzögerungen (engl. "Lags"), die durch die Datenübertragung zwischen den Rechnern entstehen. Während das bei den meisten Anwendungen und Spielen nicht groß ins Gewicht fällt, können sie die Spielerfahrung bei aktionsgeladenen Multiplayer-Titeln negativ beeinflussen.

Da sich diese Verzögerungen nicht verhindern lassen, wurden Methoden entwickelt, um sie zu kompensieren, sodass sie dem Spieler weniger auffallen und ein flüssigeres Spielen möglich ist. Die Methoden werden unter dem Begriff "Lag Compensation" zusammengefasst.

MMOG unter der Haube

Nahezu alle Multiplayer-Spiele nutzen heutzutage Client-Server-Systeme, um Spieler gegeneinander antreten zu lassen. In ihnen fallen den Clients und den Servern sehr unterschiedliche Aufgaben zu.

Client:

Annahme der Eingaben des Spielers
Senden der Eingaben an den Server
Darstellung der Spielwelt

Ausführen der Eingaben, die die Clients senden
Simulation der Spielwelt
Übertragung der Zustandsdaten der Spielwelt an die Clients, die sie zur Darstellung benötigen

Die Clients sind somit nur für die Ein- und Ausgabe zuständig, sie können die Spielwelt nicht direkt verändern. Das obliegt einzig dem zentralen (sogenannten autoritativen) Server. Wird den Clients das Recht gewährt [1], dem Server Änderungen an der Spielwelt mitzuteilen, wird dies über kurz oder lang (meistens eher kurz) zu Cheatern führen, die gefälschte Änderungsmeldungen an den Server übertragen, um sich so einen Vorteil gegenüber den anderen Spielern zu verschaffen ("I'm now at position x and, by the way, I just shot player 2 in the head."). "Der Client ist in den Händen des Feindes" hat sich, was Multiplayer-Spiele betrifft, als guter Leitspruch für Netzwerkprogrammierung erwiesen [2].

Das Problem mit der Latenz

Aus den getrennten Zuständigkeiten sowie der Verzögerung bei der Datenübertragung ergibt sich nun für den Spieler eines schnellen, aktionsreichen Titels ein durchaus spürbares Problem: Seine Eingaben haben keine direkten Auswirkungen auf die Spielwelt, sondern werden erst verzögert ausgeführt.

Verzögerte Darstellung der Spieleraktion (Abb. 1)

(Bild: Gabriel Gambetta, http://www.gabrielgambetta.com)

Was passiert? Zunächst nimmt der Client die Eingaben auf und schickt sie an den Server. Die Übertragung dauert, wie bereits erwähnt, eine gewisse Zeit. Sobald die Eingaben beim Server eintreffen, werden sie ausgeführt und verändern den Zustand der Spielwelt.

Doch damit nicht genug: Bevor der Spieler überhaupt die ersten Auswirkungen seiner Aktionen sieht, greift noch einmal dieselbe Verzögerung, da der neue Zustand der Spielwelt noch zum Spieler zurückzusenden ist, bevor er die Änderungen angezeigt bekommt. Der Zeitraum von der Eingabe bis zu deren Sichtbarwerden wird als Ping oder Round Trip Time (RTT) bezeichnet. Ein typischer Ping liegt etwa im Bereich von 100 ms.

Gerade was die Reaktion auf Eingaben angeht, sind Spieler (und Anwender im Allgemeinen) sehr anspruchsvoll. Bereits vor Jahrzehnten wurde festgestellt [3], dass eine Reaktion eines Computers auf eine Eingabe, die länger als 100ms benötigt, als Verzögerung wahrgenommen wird. Speziell bei Spielen, die eine schnelle Reaktion erfordern, liegt diese Schwelle oft noch niedriger.

Man sollte also versuchen, dem Spieler eine unmittelbare Reaktion auf seine Eingaben zu geben. Und was wäre als Reaktion besser geeignet, als die Bewegung, die der Spieler ausführen möchte?

Taten statt warten

Die im Folgenden vorgestellte Methode zum Reduzieren der gefühlten Verzögerung nennt sich Client-Side Prediction (ein begleitendes Codebeispiel ist auf GitHub [4] zu finden). Die Verantwortlichkeiten bleiben bei diesem Ansatz unangetastet, die Clients haben also weiterhin keine direkte Kontrolle über die Spielwelt. Dennoch müssen sie mehr Arbeit erledigen. Wie der Name bereits andeutet, werden auf Clientseite Vorausberechnungen durchgeführt. Sie beziehen sich auf die Eingaben der Spieler.

Statt zu warten bis der Server die veränderten Zustandsdaten der Spielwelt sendet, werden die Eingaben des Spielers, nachdem sie zum Server geschickt wurden, lokal bereits verarbeitet und dargestellt. Es wird davon ausgegangen, dass der Server die Eingaben nach der Verzögerung durch die Datenübertragung akzeptiert und ebenfalls ausführt. Voraussetzung dafür ist, dass die Bewegung möglichst deterministisch ist, das heißt aus einem Bewegungszustand und einer Eingabe ergibt sich jedes mal derselbe Folgezustand.

Nachdem die durch die Eingaben veränderte Spielwelt beim Client angekommen ist, muss er prüfen, ob die tatsächlichen Änderungen mit den vorausgesagten übereinstimmen, um synchron zum Server zu bleiben. Wurden die Eingabedaten etwa nicht in der angenommenen Zeit zum Server übertragen, berücksichtigt der Server sie zu einem anderen Zeitpunkt als auf dem Client.

Daraus ergeben sich zwei Vorteile:

Das Spiel reagiert ohne Verzögerung auf Spielereingaben.
Der Server ist weiterhin autoritativ und bietet damit keine zusätzliche Angriffsfläche für Cheater.

Bewegungssimulation

Neue Herausforderungen

Aus den Änderungen ergeben sich allerdings einige neue Umstände:

Der Client zeigt die Figur des Spielers in der Zukunft, da die Eingaben direkt angewandt werden.
Der Client muss die Bewegungssimulation ausführen können und Ergebnisse erzeugen, die möglichst identisch zu denen auf dem Server sind.
Die Zeit, die die Eingabedaten zum Server brauchen, kann schwanken.

Punkt 3 lässt sich technisch einfach beheben, wenn die Client-Side Prediction bereits von Beginn an eingeplant wurde. Dazu muss die Bewegungssimulation folgende Voraussetzungen erfüllen [5]:

Die Bewegung wird ausschließlich von den Eingabedaten des Spielers gesteuert.
Der gesamte Bewegungszustand (z.B. Position, Rotation, Geschwindigkeit,...) ist in einer Datenstruktur gekapselt.
Die Bewegungssimulation ist deterministisch bei gleichem initialen Zustand und gleichen Eingabedaten.

Der letzte Punkt lässt sich dadurch erreichen, dass sich Client und Server eine Codebasis teilen. Die beiden anderen betreffen den Aufbau der zustandslosen Simulation, die für ein gegebenes Paar an Bewegungszustand und Eingabedaten einen neuen Bewegungszustand ermittelt:

MoveState TickSimulation(MoveState state, 
Input input, float deltaTime);

Anhand einer einfachen Bewegungssimulation sollte der Implementierungsaufbau klar werden. Erstellt hat das Beispiel Gabriel Gambetta [6], der in seiner Live Demo den Aufbau auf das Wesentliche beschränkt. Die Spielfigur hat in ihr lediglich die Möglichkeit, sich auf der Horizontalen nach links oder rechts zu bewegen. Selbst eine Beschleunigung besitzt sie nicht, stattdessen bewegt sie sich sofort mit voller Geschwindigkeit in die gewünschte Richtung. Der MoveState besteht somit nur aus der x-Position und einer festgelegten Geschwindigkeit:

public class MoveState
{
    // Position.
    public float X;
}

In einer komplexeren Simulation hätte der Bewegungszustand höchstwahrscheinlich neben einer Position in weiteren Dimensionen noch eine derzeitige Geschwindigkeit sowie eine Rotation in einer oder mehreren Dimensionen.

Die Eingabedaten sind durch die eingeschränkten Bewegungsmöglichkeiten ähnlich einfach.

public class Input
{
    // -1 (left), 0, 1 (right)
    public int HorizontalAxis;
}

Danach fehlt noch die Simulation, die lediglich die Position anhand der Eingabedaten und der verstrichenen Zeit verändert.

public class MovePhysics
{    
    // Fixed speed if moved.
    public const float Speed = 2.0f;
    
    public MoveState TickSimulation(MoveState state, Input input, 
    float deltaTime)
    {
        MoveState newState = new MoveState();
        newState.X = state.X + deltaTime * input.HorizontalAxis *
        this.Speed;
        return newState;
    }
}

Reguläres Client- und Serververhalten

Ohne Client-Side Prediction holt der Client zunächst regelmäßig die Eingabedaten und schickt sie an den Server. Dabei vergibt er eine InputNumber, die es ermöglicht, die einzelen Eingabedaten eindeutig zu identifizieren:

public class ClientInput
{
    public int InputNumber;
    
    public Input Input;
}

public class Client
{    
    private int inputCounter;
        
    public int ClientId { get; set; }

    public void FixedUpdate(float deltaTime)
    {
        // Get input.
        Input input = this.FetchInput();
        
        // Send to server.
        ClientInput clientInput = new ClientInput
        {
            InputNumber = this.inputCounter++,
            Input = input,
            ClientId = this.ClientId
        };
        this.network.SendToServer(clientInput);
    }
}

Der Server empfängt die Eingabedaten seiner Clients und wendet sie auf die Figuren in der Spielwelt an. Außerdem übermittelt er den Zustand der Spielwelt regelmäßig an die Clients:

public class ConnectedClient
{
    public MoveState MoveState { get; set; }

    public int ClientId { get; set; }

    public Input Input { get; set; }

    public int InputNumber { get; set; }
}
    
public class Server
{
    private readonly List<ConnectedClient> clients = new
            List<ConnectedClient>();
        
    public void OnClientInputReceived(ClientInput clientInput)
    {
        // Get client this input is for.
        ConnectedClient client =
            this.clients.FirstOrDefault(connectedClient =>
            connectedClient.ClientId == clientInput.ClientId);
        if (client == null)
        {
            return;
        }
        client.Input = clientInput.Input;
        client.InputNumber = clientInput.InputNumber;
    }
    
    public void UpdateWorld(float updateInterval)
    {
        // Update all clients.
        foreach (var client in this.clients)
        {
            client.MoveState = this.physics.TickSimulation(
            client.MoveState, client.Input, updateInterval);
        }

        // Send world state to clients.
        this.SendWorldState();        
    }
}

Vorhersagemechanismen

Zurück auf dem Client

Der Client wiederum wartet auf die Zustands-Updates vom Server, um seinen Bewegungszustand zu aktualisieren:

public class Client
{    

...

    private void OnStateReceived(WorldState state)
    {
        // Get own state.
        ClientState clientState = state.GetClientState(this.ClientId);
        if (clientState == null)
        {
            return;
        }

        MoveState newMoveState = clientState.MoveState;

        // Set new move state.
        this.MoveState = newMoveState;
    }
    
...

}

Soweit, so standardmäßig. Wie bereits erwähnt, verhindert diese Architektur, dass ein Spieler sich durch eine Manipulation des Clients einen unfairen Vorteil verschaffen kann, da die gesamte Spiellogik auf dem Server stattfindet.

Setzte man den Client in solch einem Zustand ein, würden im lokalen Netzwerk kaum Probleme auftreten. Kritisch wird es erst, wenn Spieler übers Internet gegeneinander antreten oder man ein künstliches Lag erzeugt, wie es im Beispielprogramm möglich ist. Dann fällt sofort auf, dass sich die Spielfigur nach einer Eingabe erst verzögert in Bewegung setzt.

Auftritt der Vorhersagemechanismen

An der Stelle kommt nun der erste Teil der Client-Side Prediction ins Spiel. Statt nur die Eingaben zum Server zu senden, wendet der Client sie ebenfalls sofort lokal auf seinen Bewegungszustand an. Zusätzlich speichert er die gesendeten Eingabedaten, da sie später für einen Abgleich nötig sind:

private void FixedUpdate(float updateInterval)
{
    ... 

    if (this.Prediction)
    {
        // Apply input to state.
        this.MoveState = this.physics.TickSimulation(this.MoveState,
        input, updateInterval);
        this.sentInputs.Enqueue(clientInput);
    }
}

Durch diesen simplen Trick bewegt sich die Figur im Spiel, sobald das Programm die Eingabe erfasst hat. Es ergibt sich allerdings ein neues Problem: Sie bewegt sich zwar sofort, fängt allerdings kurz danach an zu "ruckeln". Das ist den Korrekturen durch den Server geschuldet, die den lokalen Zustand überschreiben, sobald ein Zustands-Update den Client erreicht. Um das zu umgehen, wird der zweite Teil der Client-Side Prediction, die sogenannte Reconciliation, benötigt.

Trotz der Änderungen handelt es sich bei der Architektur immer noch um einen autoritativen Server. Daher sind die Zustandsdaten, die der Client vom Server empfängt, zu nutzen, um die Figuren auf die richtigen Positionen zu bewegen. Momentan erledigt das die Methode OnStateReceived. Weil das Programm die Eingabedaten bereits bevor sie zum Server gesendet wurden zum Bewegen der Spielfigur genutzt hat, befindet sich letztere danach sozusagen in der Zukunft. In dem Moment, in dem die Eingabedaten auf dem Server eintreffen beziehungsweise die aktualisierten Zustandsdaten den Client erreichen, hat die Spielfigur womöglich schon weitere Eingaben verarbeitet. Im jetzigen Zustand überschreiben die vom Server empfangenen Zustandsdaten einfach die auf dem Client, was zu dem beobachteten Ruckeln oder Zurücksetzen der Figur führt.

Korrekturmöglichkeiten

Den Server im Blick

Nicht ohne Hintergedanken wurden bei der Einführung der Client-Side Prediction die gesendeten Eingabedaten auf dem Client gespeichert. Mit ihrer Hilfe lassen sich die eingegangenen Zustandsdaten auf denselben Zeitpunkt überführen, auf dem sich die Spielfigur befindet. Dazu sind alle Eingabedaten, die seit dem Absenden der Clienteingaben eingegangen sind, auf die Zustandsdaten anzuwenden, bevor man sie der Figur des Spielers zuweist:

private void OnStateReceived(WorldState state)
{
    // Get own state.
    ClientState clientState = state.GetClientState(this.ClientId);
    if (clientState == null)
    {
        return;
    }

    // Remove inputs which arrived at server.
    while (this.sentInputs.Count > 0 && this.sentInputs.Peek()
           .InputNumber <= clientState.InputNumber)
    {
        this.sentInputs.Dequeue();
    }

    MoveState newMoveState = clientState.MoveState;

    if (this.Reconciliation)
    {
        // Re-apply unacknowledged inputs.
        foreach (var clientInput in this.sentInputs)
        {
            newMoveState = this.physics.TickSimulation(
                newMoveState, clientInput.Input, 
                this.PhysicsUpdateInterval);
        }
    }

    // Set new move state.
    this.MoveState = newMoveState;
}

Auf die Weise lassen sich die Serverzustandsdaten berücksichtigen, die ja auf jeden Fall korrekt sind, und der Spieler kann gleichzeitig seine Spielfigur unmittelbar steuern.

Tim Sweeney, verantwortlich für die Integration der Client-Side Prediction in Unreals Networking Model, beschreibt den Ansatz wie folgt [7]:

"This approach is purely predictive, and it gives one the best of both worlds: In all cases, the server remains completely authoritative. Nearly all the time, the client movement simulation exactly mirrors the client movement carried out by the server, so the client's position is seldom corrected. Only in the rare case, such as a player getting hit by a rocket, or bumping into an enemy, will the client's location need to be corrected."

Falls Korrekturen nötig sind

Eine der Voraussetzungen der Client-Side Prediction war: "Die Bewegung wird ausschließlich von den Eingabedaten des Spielers gesteuert." Daher sind, wie auch Sweeney erwähnt, Korrekturen unvermeidbar, wenn die Spielfigur durch äußere Einwirkungen beeinflusst wird -- etwa durch eine Explosion, die sie trifft. Ein weiterer Grund kann sein, dass Eingabedaten nicht oder mit veränderter Verzögerung angekommen sind (z.B. durch einen temporären Peak). In dem Fall wurde die Eingabe auf dem Client zu einem anderen Zeitpunkt in die Bewegungssimulation einbezogen als auf dem Server, wodurch eine veränderte Bewegung zustande kommt.

Angenommen, die Figur bewegt sich momentan nach links und der Spieler wechselt die Richtung. Die Eingabedaten erreichen den Server nicht wie bislang nach 100 ms, was zwei Updates der Simulation entspricht, sondern ausnahmsweise erst nach 150 ms, also drei Updates. Da der Server die Autorität über den Weltzustand hat, wurde die Eingabe auf dem Client des Spielers somit ein Update zu früh einbezogen. Dies fällt allerdings auf dem Client 250 ms zu spät auf, nämlich erst, wenn das Zustands-Update vom Server eintrifft. Es sollte laut der Vorhersage die Eingabedaten enthalten, allerdings arbeitet es tatsächlich noch mit den vorherigen Eingabedaten.

Ohne gesonderte Behandlung würde die Figur nun abrupt auf die vom Server vorgegebene Position springen, was der Spieler in den meisten Fällen bemerkt. Eine einfache Behandlung wäre, den Bewegungszustand lediglich teilweise zu korrigieren, sodass die Nachbesserung weniger offensichtlich geschieht. In späteren Updates ist häufig eine erneute Korrektur nötig, aber solange Fehler nicht allzu oft auftreten, sollte der Zustand innerhalb einiger Updates wieder synchronisiert sein.

Da die gesamte Bewegungssimulation auf dem Client zur Verfügung steht, bietet sich allerdings noch eine weitaus subtilere Korrekturmöglichkeit an. Die Idee ist, sowohl die Bewegungssimulation auf dem Client inklusive des Fehlers weiterzuberechnen, als auch die korrekte Variante, die auf den Daten des Servers beruht. Die Korrektur findet nun anhand von linearer Interpolation über mehrere Updates zwischen den beiden berechneten Zuständen statt.

Die Methode ähnelt stark der direkten Korrektur bei der nur eine teilweise Korrektur vorgenommen wird. Allerdings hat sie den Vorteil, dass hierbei nicht nach jedem Update der Weltzustand zu den Clients zu schicken ist. Es würde stattdessen genügen, nur ein Zustands-Update zu schicken, wenn sich die Eingabedaten geändert haben. Auf der anderen Seite sind dem Server auch modifizierte Eingabedaten zu senden. Solange keine neuen Daten den Server erreichen, nutzt er die vorhandenen für die weitere Simulation. Die Implementierungsdetails dieser Optimierungen sowie der Korrektur durch lineare Interpolation würden allerdings den Rahmen dieses Artikels und des Beispielprogramms [8] sprengen.

Fazit

Die Client-Side Prediction mindert das Problem von Latenz in Multiplayer-Spielen, indem es dem Spieler das Gefühl vermittelt, dass seine Eingaben direkt die Spielfigur beeinflussen. Durch das direkte Feedback kann er seine Figur einfacher steuern.

Der Server hat dabei allerdings weiterhin die Autorität über den Weltzustand, wodurch sich Cheatern keine weiteren Zugriffspunkte präsentieren, um sich einen unfairen Vorteil zu verschaffen. Die verschiedenen Zustände auf den Clients und dem Server haben aber eine Reihe von Konsequenzen, die bei der Umsetzung zu beachten sind. Das größte Problem stellt die Korrektur auf den Clients dar, die nötig ist, sobald der Zustand der Figur von dem auf dem Server hinterlegten abweicht. Hier besteht die Herausforderung darin, eine Korrektur vorzunehmen, ohne dass es der Spieler merkt.

Bei Kartuga, einem Multi-Player-Action-Spiel bei dem der Spieler ein Schiff steuert, wurde erfolgreich lineare Interpolation zwischen dem Client- und dem berechneten Serverzustand eingesetzt, um die Korrektur so subtil wie möglich vorzunehmen.

Daneben haben die unterschiedlichen Zustände auf den Clients durchaus geringe spielerische Auswirkungen, wie ein Vergleich in Call of Duty Black Ops [9] aus der Sicht des Spielers und der des Zuschauers zeigt. So ärgerlich derartige Auswirkungen sind, wenn sie zum Beispiel zu einem verpassten Treffer auf einen Gegner führen, muss man sich immer die Alternative vor Augen halten. Eine verzögerte Ausführung der Eingaben auf der eigenen Spielfigur würde zu einem wesentlich schlechterem Spielerlebnis führen.

Daher ist Client-Side Prediction seit langem De-facto-Standard in aktionsreichen Multiplayer-Spielen. Auch wenn die Steuerung der Figuren das Kernproblem darstellt, so lassen sich die Methoden ebenfalls in anderen Bereichen einsetzen. So können Projektile beim Feuern einer Waffe bereits beim Abdrücken losfliegen; Einheiten in einem Echtzeitstrategiespiel direkt loslaufen; eine Kampfanimation lässt sich abspielen, bevor die Bestätigung der Aktion erhalten wurde, und so weiter.

Sehr gute englische Artikel zu den Grundlagen der genannten Techniken finden sich auch im Internet (z.B. Gabriel Gambettas Client-Side Prediction and Server Reconciliation [10] und Glen Fiedlers What every programmer needs to know about game-networking) [11]. Außerdem steht der Autor bei weiteren Fragen gerne zur Verfügung [12].

Christian Oeing [13]
hat sich nach seinen Stationen bei Spellbound (ArcaniA - Gothic 4) und Ticking Bomb Games (Kartuga) mit Slash Games [14] selbstständig gemacht. Dort entwickelt er gemeinsam mit Nick Prühs eigene [15] und beauftragte Browser- und Mobile Games. (jul [16])

URL dieses Artikels:
https://www.heise.de/-2301773

Links in diesem Artikel:
[1] http://developer.valvesoftware.com/wiki/Latency_Compensating_Methods_in_Client/Server_In-game_Protocol_Design_and_Optimization
[2] http://raphkoster.com/2008/04/17/how-to-hack-an-mmo/
[3] http://nngroup.com/articles/response-times-3-important-limits/
[4] https://github.com/coeing/client-side-prediction
[5] http://gafferongames.com/game-physics/networked-physics/
[6] http://gabrielgambetta.com/fpm2.html
[7] http://docs.google.com/document/d/1KGLbEfHsWANTTgUqfK6rkpFYDGvnZYj-BN18sxq6LPY
[8] https://github.com/coeing/client-side-prediction
[9] http://youtube.com/watch?v=0HRtdHmXEjs
[10] http://gabrielgambetta.com/fpm2.html
[11] http://gafferongames.com/networking-for-game-programmers/what-every-programmer-needs-to-know-about-game-networking
[12] mailto:christian.oeing@slashgames.org?subject=Frage%20zu%20Artikel%20%22Verz%C3%B6gerungen%20in%20Online-Spielen%20durch%20Client-Side%20Prediction%20kompensieren%22
[13] mailto:christian.oeing@slashgames.org?subject=Frage%20zu%20%22Client-Side%20Prediction%22
[14] http://www.slashgames.org
[15] http://www.freudbot.net/
[16] mailto:jul@heise.de