Lag, we hate it, it is the bane of every video gamer and it causes some really unusual effects. For example during a game of Halo 3 I was riding with my friend on a warthog and the turret, usually connected to the warthog, simply slipped off with me still on it, rolling around the map (followed by a disconnect). Another noticeable example is playing Call of Duty: World at War on a low bandwidth dongle with high latency only to find an enemy running without any legs followed by a crash that simply stated "Error: Model burly_soldier_02 doesn't have enough bones".
The point is lag causes some weird effects and I was curious why these effects occur and it turns out these are caused by certain counter measures games use to try and hide lag and it was really interesting because it explained all these effects. And so I thought I'd explain how these effects come about (partly to test my own understanding) and propose some different ideas for lag compensation (however these are just crazy ideas). So lets discuss.
Extrapolation: One of the most common symptoms of lag is randomly teleporting enemies or objects, you see someone walk into a wall for about a second and then suddenly teleport to somewhere else. The reason this can happens is due to a lag counter measure called extrapolation and it's when your computer attempts to predict what the world is doing in the absence of any information. When the computer is waiting for a packet it realises it still has to render the next frame so it will just guess what the next frame should be. It will continue guessing until the packet finally arrives, in which case it will update to the new location.
The predictions aren't usually that good and are very basic, for example if an enemy is moving in one direction the computer will usually guess that it will move in the same direction even if there are objects in its way. I wonder if lag would become a lot less noticeable if we used better predictive algorithms to judge what a human would reasonable do in a given situation, maybe render a game AI in place of a human. Sure, we would still expect there to be error because humans are fundamentally unpredictable, but maybe we could at least reduce the error.
Interpolation: This is a little bit more complicated. First we need to introduce the concept of a time-step, when a server talks to a player the server is not always sending information to the player and the player isn't always sending information to the server, if we had to wait for the world to update from the server every time we clicked a button lag would become an even larger issue. Instead, the server and player sends data once every "time-step", which is usually once every 10-100 ms, in this the server tells the player what the world looks like at "time-step 2 (T=2)" and the player sends to the server everything it did since "time-step 1 (T=1)". But what do we do we do in between these time steps?
We do something called interpolation, interpolation in the usual form basically means given an object at two different points at two different times, create a path for that object so it has a smooth transition between those two points. An example would be suppose a player is at a box at T=1 and then is at a wall at T=2 then instead of showing the player teleport between the box and the wall, we interpolate the players position so that it appears he moves smoothly between the box and the wall. It turns out, if you're willing to make a few assumptions, you can calculate an entire path of an object just with a few points.
So what does interpolation mean in the server sense? Well because the player only receives updates from the server once every time step it can still render what happens in between each time step by interpolating the data. If at T = 1 an enemy is seen at position 1, and then at T = 2 the enemy is at position 2, we can interpolate those two points to make the enemy look like its walking between position 1 and 2 between T=1 and T=2. But wait, there's a huge problem with this, in order to interpolate between T=1 and T=2 we need the data for T=1 and T=2. If we're at T=1.5 we still don't have the data for T=2 so how can we interpolate where the enemy is? If we guess that's just extrapolation once again, so what can we do?
The solution is rather genius, what if we render everything a time step behind. So if you see an enemy doing something at T=2, you will actually be at T=3, so you (the player) are always one time step ahead of the server. If the time steps are relatively close together then usually you won't notice the fact that the game you're seeing is actually in the past. Most games use interpolation so it means what you see your enemies do on the server is actually what the enemy has already done in the past, not necessarily at the moment you were playing. It's cool!
Interpolation is nice but it does give a resolution of lag, lag will be mostly unnoticeable if it is smaller than the distance between two time-steps (and the distance is appropriately chosen). If it becomes larger than the time-step will update an enemies location further back in time than you expect, you will see enemies moving faster than they should be moving as the game frantically attempts to update the game state to a more appropriate level. I expect for a very high lag the game will eventually begin resorting to extrapolation or at least have extrapolation-like effects.
More time travel: Here is a scenario, you have a server and two players (Player A and Player B), Player A is trying to shoot Player B before Player B runs behind cover. At T=0, Player A shoots at Player B and hits Player B's head, killing him, before he can get into cover. Player A however has a laggy connection and Player A can't tell the server that it shot and killed Player B until T=10. Player B on the other hand has a better connection and tells the server it got behind the box at T=1 and thus did not get shot. What is the server to do?
Well, from T=1 to T=9 the server only got messages from Player B saying it was behind the box and did not get a message from Player A that it shot at Player B. So the server declares Player B is safe because, in its eyes, no one shot at him. However at T=10 Player A now indicates it shot at Player B, and the server now has to make a decision. One thing it could do is to just find the location that Player A shot at, if Player A shot at a position that Player B is at now, then Player B will die, otherwise Player B is safe. This is unfair on Player A because it took 10 time steps for the bullet to hit its target (on the server side), so despite Player A shooting Player B on his end, Player B will be safe because the server will only see the bullet hit where Player B used to be, not where he is now.
But the server can (and in modern games often does) use a different approach. Even though we only got the packet at T=10, information in the packet can tell us that Player A actually shot the bullet at T=0, so the server can rewind time and see what the game state was like at T=0. It can then see where the player shot at and see that, indeed, at T=0 Player B was actually in the way of incoming fire. So the server, after looking backwards in time, can declare that Player A actually did shoot Player B and can then declare Player B... dead. This seems more fair because if there was NO lag at all, Player B would have been shot and killed by Player A, so even with lag the same thing happens. The only problem is (and you would have noticed this in game), in player B's perspective they escaped Player A's shooting, hid behind cover for 9 time steps and then suddenly died. That's right, if you've died behind cover before this is what's happening, they are not shooting you through cover or hitting a hit box that's behind you, the server is going back in time and seeing if the player ACTUALLY shot you.
The situation gets more complicated when both Player A and Player B have lag, also the server can only go back in time so much before it becomes too computationally expensive to do. But its still an interesting and rather effective technique for having more fair games, even if it does frustrate people from time to time.
The best/worst option: One thing that all these lag compensation techniques have in common is the idea that the server makes decisions on the game state. Players have to tell the server everything they've done and the server decides what the players are actually doing in the game world, then tells the players the effects of their actions. This means lag is very important because the player can't really now what's happening in the game without input from the server. So what if instead of the server telling the player what the game world is like.... the player tells the server what the game world is like.
You're running around and you see an enemy, you shoot the enemy and it appears the enemy dies. Normally you'd tell the server where you shot, the enemy would tell the server where he was and the server decides whether you actually shot the enemy. But you CLEARLY shot the enemy, so what if you just told the server "I shot this enemy, trust me". Well now, guess what, you have made lag a lot less important because what happens on your screen is what happens in the game. You don't have to wait for everyone to connect, you play your game and events happen as you see them, if someone is lagging and you shoot and kill them then you can still kill them even though they're being laggy. Sometimes the server will need to step in when clients have conflicting ideas on what actually happened in the game, but in general this makes lag a LOT less noticeable. So what's the problem?
Well I think you should be able to see it, you are now telling the server what happens in the game. Well, you also have full control of the game so what if you just told the server "Oh yeah I just killed everyone", the server would be forced to trust you and so BOOM, everyone would die. The problem is the server can't know which request is real and which is fake so it means you can just goof any command you want (which is trivially easy) and the server has to trust you. This isn't good which is why almost no games running today use this method even though it offers the least intrusive lag.
Maybe though we can combine the approaches of an authoritative server to detect a malicious client. Basically we have the client send information to the server, the server renders the game state based on the client information and starts re-enacting the events that happened. It might then be able to verify whether some events shouldn't be possible (like killing every person in the game instantly) and be able to flag that as invalid behaviour, ignoring the data the client sends. This has already been investigated with some proposed ideas on how this would work: https://www.cs.unc.edu/~reiter/papers/2011/TISSEC3.pdf
In terms of lag reduction though I suppose we still have problems. The server has to authorise a players actions, but if the server authorises every player action then it becomes just a normal authoritative server, where the client has to wait for the servers authorisation before updating its own game world. A potential solution for this is to back-peddle authorisation, so if the player does an action it can just assume the action is authorised by the server, then if the server rejects the action the it sends that information to the player after the fact and the player updates its game state as if the action never happened. This would be jarring (Cause in your screen everyone would die then suddenly, some time later, everyone would be alive again) but it would only effect players that are doing something the server deemed cheating (as the other players never received the "you're dead signal").
Either way lag is really interesting, and maybe some of these things explained why you get some weird effects with lag. Hope you found this an interesting read!
