Interpolation

Kellen Evan

2019/12/01

Categories: Technology Writing

Anyone familiar with first-person shooters knows the cold and unfair reality of global networking. But what if there is a deeper lesson within these split second interactions?

On my screen I was safe behind a wall. Yet on my adversaries screen I was vulnerable, out in the open, and so I was killed. That is the story the server told, the one it took to formal consensus shared by all other players. My adversary is now understood as the winner and I – stuck somewhere in the purgatory of lag – am marked as the loser.

“The introduction of lag compensation allows for each player to run on his or her own clock with no apparent latency. In this respect, it is important to understand that certain paradoxes or inconsistencies can occur.” - Yahn Bernier, Valve Software, Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization

A networked computer can be known in general as a client. A client connects to a central server. Modern servers accept connections from clients of all type: your browser is a client, your apps are clients, your workstation is a client.

Gaming – with its deep requirement for fluidity and fairness – is a prime example of the rigours of the client/server relationship. Games are fast and competitive and so a server must be extra diligent. It must build a seamless consensus so that each client can experience a shared state, a shared reality, in near real time. It does this thousands of times every second – across the nations – and there is little room for error.

In games, players move in nondeterministic patterns. In other words, when observed by the server each player will act as an input source that exhibits differing, unpredictable behaviour patterns. A server must then decide how events will unfold based on these chaotic variations of micro-expressions. It uses two key methods to do so: interpolation and extrapolation.

Extrapolation is best understood through the framework of ballistics. An object going to a certain location at a certain speed will – in all likelihood – wind up at a given location with a very high degree of probablity. Extrapolation is effective, for bullets. But on the Internet and in games, a server can never be quite sure.

If a sever were to extrapolate a state given only where it thinks everything is going, it would wind up in disarray because of latency. It does not know for certain “the speed” or “the location” and so it cannot generate the “destination”. To make matters more dubious, the client’s – the player’s – latency is never guaranteed even if their input is, and so a server can never extrapolate a stable course with so many unknowns. What is latency?

Latency is represented in milliseconds (ms). It shows up as a well known number: a ping! A ping! such as 100ms means it took 100 milliseconds for data to make a round-trip between a client and a server. That seems fast! But it is not, not when you consider the hyper-acute requirements of precision gaming and the limitations of the speed of light at which the information travels. Even 100ms is far too slow to extrapolate cohesion. And the nature of latency is that it can be any number, at any time, up to seconds in extreme cases.

If extrapolation were to be the only method used to build consensus, latency would make things appear to be warping from place to place! And that wouldn’t do as that would break the illusion of an organized and cohesive virtual reality. It would not make for an enjoyable game. Extrapolation is not enough. It is but one computational axis of a required many. Enter interpolation.

Interpolation is where algorithmic predictability meets introspection. It places people into the past, confirming their most recent, valid position, and it waits. Or rather it makes the client wait.

The server renders a notion of truth and sends an update containing it to each client every second. After delivery, it will pause for a fraction of that second and interpolate. During that time it will look at what occurred between the last reported position of each client and the position just prior to that. It will then use the “extra padding” of the second to place each client somewhere with it in the past, aligning them all within the flow of their shared existence.

After the second has passed, the clients will then receive their rendering, their instruction, and each will know that it can continue on its path over the next fraction of a second. All of the data received from each client, its orientation, timing and movement, are then evaluated in reverse, thousands of time per second, to ensure a fluid and graceful experience. It is a dizzying feat of split-second engineering.

"from state" <- state after last user command acknowledged by the server;
"command" <- first command after last command acknowledged by server;

while (true)
{
    run "command" on "from state" to generate "to state";
    if (this was the most up to date "command")
        break;

    "from state" = "to state";
    "command" = next "command";
};

// By Yahn Bernier

All of this relies on the integrity of the connection. It assumes that each packet will arrive on-time and in optimal condition. We expect this knowing how far it must have travelled and how fraught with peril the wires running through the Earth and over the ocean must be at any given moment. And that’s not to mention the packets in the air, traveling through even flesh and bone to arrive intact at your computer.

Naturally network packets get lost from time to time. Yet each bit is vital in conjuring a believable reality, the slightest glitch and we feel it through our fingertips.

“If one of the update packets fails to arrive, then there are two choices: We can start extrapolating the player position as noted above (with the large potential errors noted) or we can simply have the player rest at the position in the last update until a new update arrives…”

Extrapolation alone is risky. The server is never quite sure what a latent client will do, but together with interpolation, it is more resilient. Even together, there is still ample opportunity for oddities.

In the event of missing data such as if the client has a poor connection, interpolation will ask a client to wait. It will hang the client – a player – in the ether until it receives a new update from which the server can then render it a new picture and produce it a clear path. But if the connection never resolves into a healthy state, that player may stay lost in limbo or even disconnected.

On reflection, perhaps this goes far deeper than computer networking. In the end, people are like clients. I am like a client and so are you. Which is to say: we connect to a central server and need to generate a cohesive, consensus reality in real time. We sit next to other clients each of whom go about their own business. And the server sits… somewhere, everywhere, waiting for updates. How many updates – and what we update – varies and we each have a differing ping!

As it would do, our grand server interpolates, it extrapolates, and it conjures all possible outcomes through an intelligence that we can never comprehend, that no code no matter how elegant can ever replicate. For it works much deeper than algorithm.

Should you lower your ping enough through meditation or disconnect through death, the boundaries of your client disappear and the server need no longer guess where it will put you. The distinction becomes meaningless. For the client is – and always has been – a part of the server, yet it forgot.

It forgot because it knew its self as separate. Even as the shared laws of electric light governed the speed at which it could send its messages and even as both of them were born of the same source code, it went on acting as an “other”, a mere module of a server and all of its greatness: it forgot. But they are the same.

Clients feel separate because they each send signals to the server and they each want to have the deepest impact on its rendered reality. The server, the infinite processor humming at the core of existence, needs to thread all of this data into one coherent tapestry – into a Universe – and it does so without complaint and it never ceases and it makes no errors. It is perfect.

Yet many clients becme lost in the ether, waiting for a server to tell them what to do. and it is all too easy to become disconnected. I was there once, hanging alone, waiting and wondering for someone or something to tell me what to do. To know this disconnection is to know anger and depression, to know fear. But fear not.

Your network layer can be optimized and your ping can be improved. Return your attention to the moment, breathe and meditate. The server is with you, here and now. The world you feel blossoms from its centre with your awareness at its core. Live with it, surrender to it and the server need never guess at where to put you.

"from state" <- state after last user command acknowledged by the server;
"command" <- first command after last command acknowledged by server;

  run "command" to set "from state" and "to state" to null;
  if (this was the most up to date "command")
    break;
};
>> Home