Solutions to lag and lag compensation methods
There are various methods for reducing or disguising delays, though many of these have their drawbacks and may not be applicable in all cases. If synchronization is not possible by the game itself, the clients may be able to choose to play on servers in geographical proximity to themselves in order to reduce latencies, or the servers may simply opt to drop clients with high latencies in order to avoid having to deal with the resulting problems. However, these are hardly optimal solutions. Instead, games will often be designed with lag compensation in mind.
Many problems can be solved simply by allowing the clients to keep track of their own state and send absolute states to the server or directly to other clients. For example, the client can state exactly at what position a player's character is or who the character shot. This solution works and will all but eliminate most problems related to lag. Unfortunately, it also relies on the assumption that the client is honest. There is nothing that prevents a player from modifying the data they send, directly at the client or indirectly via a proxy, in order to ensure they will always hit their targets. In online games, the risk of cheating may make this solution unfeasible, and clients will be limited to sending relative states (i.e. which vector it moved on or shot in).
As clients are normally not allowed to define the main game state, but rather receive it from the server, the main task of the client-side compensation is to render the virtual world as accurately as possible. As updates come with a delay and may even be dropped, it is sometimes necessary for the client to predict the flow of the game. Since the state is updated in discrete steps, the client must be able to estimate a movement based on available samples. Two basic methods can be used to accomplish this; extrapolation and interpolation.
Extrapolation is an attempt to estimate a future game state. As soon as a packet from the server is received, the position of an object is updated to the new position. Awaiting the next update, the next position is extrapolated based on the current position and the movement at the time of the update. Essentially, the client will assume that a moving object will continue in the same direction. When a new packet is received, the position may be corrected slightly.
Interpolation works by essentially buffering a game state and rendering the game state to the player with a slight, constant delay. When a packet from the server arrives, instead of updating the position of an object immediately, the client will start to interpolate the position, starting from the last known position. Over an interpolation interval, the object will be rendered moving smoothly between the two positions. Ideally, this interval should exactly match the delay between packets, but due to loss and variable delay, this is rarely the case.
Both methods have advantages and drawbacks.
Interpolation ensures that objects will move between valid positions only and will produce good results with constant delay and no loss. Should dropped or out-of-order packets overflow the interpolation buffer the client will have to either freeze the object in position until a new packet arrives, or fall back on extrapolation instead. The downside of interpolation is that it causes the world to be rendered with additional latency, increasing the need for some form of lag compensation to be implemented.
The problem with extrapolating positions is fairly obvious: it is impossible to accurately predict the future. It will render movement correctly only if the movement is constant, but this will not always be the case. Players may change both speed and direction at random. This may result in a small amount of "warping" as new updates arrive and the estimated positions are corrected, and also cause problems for hit detection as players may be rendered in positions they are not actually in.
Often, in order to allow smooth gameplay, the client is allowed to do soft changes to the game state. While the server may ultimately keep track of ammunition, health, position, etc., the client may be allowed to predict the new server-side game state based on the player's actions, such as allowing a player to start moving before the server has responded to the command. These changes will generally be accepted under normal conditions and make delay mostly transparent. Problems will arise only in the case of high delays or losses, when the client's predictions are very noticeably undone by the server. Sometimes, in the case of minor differences, the server may even allow "incorrect" changes to the state based on updates from the client.
Unlike clients, the server knows the exact current game state, and as such prediction is unnecessary. The main purpose of server-side lag compensation is instead to provide accurate effects of client actions. This is important because by the time a player's command has arrived time will have moved on, and the world will no longer be in the state that the player saw when issuing their command. A very explicit example of this is hit detection for weapons fired in first-person shooters, where margins are small and can potentially cause significant problems if not properly handled.
Another way to address the issue is to store past game states for a certain length of time, then rewind player locations when processing a command. The server uses the latency of the player (including any inherent delay due to interpolation; see above) to rewind time by an appropriate amount in order to determine what the shooting client saw at the time the shot was fired. This will usually result in the server seeing the client firing at the target's old position and thus hitting. In the worst case, a player will be so far behind that the server runs out of historical data and they have to start leading their targets.
This is a WYSIWYG solution that allows players to aim directly at what they are seeing. But the price is an aggravation of the effects of latency when a player is under fire: not only does their own latency play a part, but their attacker's too. In many situations, this is not noticeable, but players who have just taken cover will notice that they carry on receiving damage/death messages from the server for longer than their own latency can justify. This can lead more often to the (false) impression that they were shot through cover and the (not entirely inaccurate) impression of "laggy hitboxes".
One design issue that arises from rewinding is whether to stop rewinding a dead player's lagged commands as soon as they die on the server, or to continue running them until they "catch up" to the time of death. Cutting compensation off immediately prevents victims from posthumously attacking their killers, which meets expectations, but preserves the natural advantage of moving players who round a corner, acquire a target and kill them in less time than a round trip to the stationary victim's client.
Rewinding can be criticised for allowing the high latency of one player to negatively affect the experience of low-latency players. Servers with lag compensation will sometimes reduce the length of player history stored, or enforce ping limits, to reduce this problem.
It is possible for clients to tell the server what they are doing and for the server to trust the data it receives. This method is avoided if at all possible due to its susceptibility to cheating: it is a simple matter to route network data through a second computer which inserts fabricated hit messages or modifies existing ones, a technique which cannot be detected by anti-cheat tools.
However, the sheer scale of some games makes computationally expensive solutions like rewinding impossible. In Battlefield 3, for example, a "hybrid hit detection" system is used where clients tell the server that they hit and the server performs only a vague test of plausibility before accepting the claim.
Trusting a client's results otherwise has the same advantages and disadvantages as rewinding.
Make clients extrapolate
A less common lag solution is to do nothing on the server and to have each client extrapolate (see above) to cover its latency. This produces incorrect results unless remote players maintain a constant velocity, granting an advantage to those who dodge back and forth or simply start/stop moving.
Extended extrapolation also results in remote players becoming visible (though not vulnerable) when they should not be: for example if a remote player sprints up to a corner then stops abruptly at the edge, other clients will render them sprinting onward, into the open, for the duration of their own latency. On the other side of this problem, clients have to give remote players who just started moving an extra burst of speed in order to push them into a theoretically-accurate predicted location.
It is possible to reduce the perception of lag through game design. Techniques include playing client-side animations as if the action took place immediately, reducing/removing built-in timers on the host machine, and using camera transitions to hide warping.