Multiplayer Game Programming: Architecting Networked Games (2016)
Chapter 8. Improved Latency Handling
As a multiplayer game programmer, latency is your enemy. Your job is to make your players feel like they’re playing on a server across the street, when it may really be across the country. This chapter explores some of the ways to make that happen.
The Dumb Terminal Client
On the topic of client-server network topology, Tim Sweeney famously once wrote, “The server is the man!” He was referring to the fact that in Unreal’s networking system, the server itself is the only host that necessarily has a true and correct game state. This is a traditional requirement of any cheat-resistant client-server setup: The server is the only host running a simulation that matters. That means there is always some delay between the time when a player takes an action and the time when the player can observe the true game state that results from that action. Figure 8.1illustrates this by showing the round trip of a packet.
Figure 8.1 Packet round trip
In this example, the round trip time (RTT) between Client A and the server is 100 ms. At time 0, Player A’s avatar on Client A is at rest, with a Z position of 0. Player A then pushes the jump button. Assuming roughly symmetric latency, it takes about 50 ms, or 1/2 RTT, for the packet carrying Player A’s input to reach the server. When it receives the input, the server begins the player’s jump, and sets her avatar’s Z position to 1. It sends out new state, which reaches Client A another 50 ms, or 1/2 RTT, later. Client A updates Player A’s avatar’s Z position based on the state sent from the server and displays the results on screen. So finally, a full 100 ms after pushing the jump button, Player A gets to see the effect of the jump action.
From this demonstration, you can extract a useful conclusion: The true simulation running on the server is always 1/2 RTT ahead of the true simulation a remote player perceives. Put another way, if a player observes only the true simulation state replicated to the client, the player’s perception of the state of the world is always at least 1/2 RTT older than the current true world state on the server. Depending on network traffic, physical distance and intermediate hardware, this can be as high as 100 ms or more.
Despite the noticeable lag between input and response, there were early multiplayer games that shipped with just this implementation. The original Quake was one game that endured despite its input latency. In Quake, and many of the other client-server games of the time, clients sent input to the server, and then the server ran the simulation and sent results back to the client for display. Clients in these games were referred to as dumb terminals because they didn’t need to understand anything about the simulation; their only purpose was to transmit input, receive the resulting state, and display it to the user. Because they showed only the state the server dictated, they never showed the user incorrect state. Although it might be delayed, whatever state a dumb terminal showed to a user was definitely a correct state at some recent point in time. Because the state throughout the system was always consistent and never incorrect, this method of networking can be classified as a conservative algorithm. At the expense of subjecting the user to noticeable latency, the conservative algorithm is at least never incorrect.
Besides just a feeling of latency, there is another problem with a pure dumb terminal. Figure 8.2 continues the example of Player A’s jump.
Figure 8.2 Jumping with 15 packets per second
Due to a high-powered GPU, Client A can run at 60 frames per second. The server can also run at 60 frames per second. However, due to bandwidth constraints on the connection between the server and Client A, the server can only send state updates 15 times per second. Assuming the player travels upward at 60 units per second at the start of her jump, the server smoothly increases her Z position by 1 unit each frame. However, it only sends state to the client every four frames. When Client A receives the state, it updates Player A’s avatar’s Z location, but then must render her at that Z location for four frames until new state from the server arrives. This means Player A sees the same picture on screen four frames in a row. Even though she spent good money on a GPU that can render at 60 frames per second, she only gets the experience of playing at 15 frames per second due to network limitations. This would probably make her unhappy.
There is a third problem. Besides just causing a general feeling of unresponsiveness, this type of latency in a first-person shooter makes it difficult to aim at other players. Without an up-to-date representation of where players are, it can become an unpleasant challenge to figure out where to aim. It can be frustrating for players to think they are pulling off headshots, only to miss because their enemies were actually 100 ms ahead of where they were rendered. Too many experiences like that can cause players to switch to another game.
When building a client-server game, you cannot escape the issue of latency. However, you can reduce its impact on the player experience, and the following sections explore some common methods that multiplayer games use to handle latency.
Client Side Interpolation
The jumpiness brought on by infrequent state updates from the server can make players feel like their game is running slower than it actually is. One way to alleviate this is through client side interpolation. When using client side interpolation, the client game does not automatically teleport objects to their new positions sent by the server. Instead whenever the client receives new state for an object, it smoothly interpolates to that state over time using what’s known as a local perception filter. Figure 8.3 illustrates the timing.
Figure 8.3 Timing of client side interpolation
Let IP represent the interpolation period in milliseconds, or how long the client takes to interpolate from old state to new state. Let PP represent the packet period in milliseconds, or how long the server waits between sending packets. The client finishes interpolating to a packet’s state IP milliseconds after the packet arrives. Thus if IP is less than PP, the client will stop interpolating before a new packet has arrived, and the player may still experience a stutter. To make sure that the client state is changing smoothly each frame and the interpolation never stops, IP should be no less than PP. That way, whenever the client finishes interpolating to a given state, it will have already received the next state and can begin the process again.
Remember that a dumb terminal with no interpolation is always 1/2 RTT behind the server. If state arrives but the client does not display it right away, then the player’s view of the world lags even further behind. Games using client side interpolation display state to players that is approximately 1/2 RTT + IP milliseconds behind the true state on the server. Thus, to minimize latency, IP should be as small as possible. This desire, combined with the fact IP must be greater than or equal to PP to prevent stutter, means it should be exactly equal to the PP.
The server can either notify the client how frequently it intends to send packets, or the client can compute the PP empirically by noting how rapidly packets arrive. Note that the server should set the packet period based on bandwidth, not latency. The server can send packets as frequently as it believes the network between the client and server can transmit them. This means that the latency perceived by players of games that use this type of client side interpolation is a factor of not only network latency, but also of network bandwidth.
Continuing the previous example, if the server sends 15 packets per second, the packet period is 66.7 ms. This means adding 66.7 ms of latency to 1/2 RTT that is already 50 ms. However, the game will look much smoother with interpolation than without, and it can make the experience more pleasant for the player such that latency is less of a concern.
Games that allow the player to manipulate the camera have a potential advantage here that can help reduce the feeling of extra latency. If the camera pose is not critical to the simulation, the game can handle it all client side. Walking around or shooting should require a trip to the server and back because they affect the simulation directly. Just aiming a camera might not affect the simulation in any manner, and if so, the client can update the renderer’s view transform without waiting for a response from the server. Locally handling camera interaction gives the player instant feedback when she moves the camera. This combined with the smooth interpolation can help alleviate a lot of the unpleasant feelings associated with increased latency.
Client side interpolation still is considered a conservative algorithm: Although it may sometimes represent a state that the server did not replicate exactly, it only represents states that are between two states that the server did simulate. The client smoothens out the transition from state to state, but never guesses at what the server is doing, and therefore never ends up at a wildly incorrect state. This is not true about all methodologies, as the next section shows.
Client Side Prediction
Client side interpolation can smooth out your players’ gameplay experiences, but it still won’t bring them closer to what’s actually happening on the server. Even with a tiny interpolation period, state is still at least 1/2 RTT old by the time the player sees it. To show game state that is any more current, your game needs to switch from interpolation to extrapolation. Through extrapolation, your client can take slightly old state received by the client and bring it approximately up to date before displaying it to the player. Techniques that perform this sort of extrapolation are often referred to as client side prediction.
To extrapolate the current state, the client must be able to run the same simulation code that the server runs. When the client receives a state update, it knows the update is 1/2 RTT ms old. To make the state more current, the client simply runs the simulation for an extra 1/2 RTT. Then, when the client displays the result to the player, it is a much closer approximation of the true game state currently simulating on the server. To maintain this approximation, the client continues running the simulation each frame and displaying the results to the player. Eventually, the client receives the next state packet from the server and internally simulates it for 1/2 RTT ms, at which point it ideally matches the exact state that the client has already calculated based on the previous received state!
To perform extrapolation by 1/2 RTT, the client must first be able to approximate the RTT. Because the clocks on the server and client are not necessarily in sync, the naïve approach of having the server timestamp a packet and then having the client check the age of the stamp will not work. Instead, the client must calculate the entire RTT and cut it in half. Figure 8.4 illustrates how to do so.
Figure 8.4 RTT calculation
The client sends a packet to the server containing a timestamp based on the client’s own local clock. Upon receiving this packet, the server copies that timestamp into a new packet and sends it back to the client. When the client receives this new packet, it subtracts the old timestamp, based on its clock, from the current time on its clock. This yields the exact amount of time between when the client first sent the packet and when it received the response—the definition of RTT. With this information, the client knows approximately how old the rest of the data in the packet is, and can use that information to extrapolate the contained state.
Warning
Remember that 1/2 RTT is only an approximation of how old the data is. Traffic does not necessarily flow with the same speed in both directions, and thus the actual travel time from server to client may be more or less than 1/2 RTT. Regardless, 1/2 RTT is a good enough approximation for most real-time game purposes.
In Robo Cat Action, discussed in Chapter 6, the client already sends timestamped moves to the server, so the server just needs to send the timestamp from the most recent move back to the client when it sends state. Listing 8.1 shows the changes to the NetworkManagerServer which handle this.
Listing 8.1 Returning Client Timestamp to Client
void NetworkManagerServer::HandleInputPacket(
ClientProxyPtr inClientProxy,
InputMemoryBitStream& inInputStream)
{
uint32_t moveCount = 0;
Move move;
inInputStream.Read(moveCount, 2);
for(; moveCount > 0; –moveCount)
{
if(move.Read(inInputStream))
{
if(inClientProxy->GetUnprocessedMoveList().AddMoveIfNew(move))
{
inClientProxy->SetIsLastMoveTimestampDirty(true);
}
}
}
}
bool MoveList::AddMoveIfNew(const Move& inMove)
{
float timeStamp = inMove.GetTimestamp();
if(timeStamp > mLastMoveTimestamp)
{
float deltaTime = mLastMoveTimestamp >= 0.f?
timeStamp - mLastMoveTimestamp: 0.f;
mLastMoveTimestamp = timeStamp;
mMoves.emplace_back(inMove.GetInputState(), timeStamp, deltaTime);
return true;
}
return false;
}
void NetworkManagerServer::WriteLastMoveTimestampIfDirty(
OutputMemoryBitStream& inOutputStream,
ClientProxyPtr inClientProxy)
{
bool isTimestampDirty = inClientProxy->IsLastMoveTimestampDirty();
inOutputStream.Write(isTimestampDirty);
if(isTimestampDirty)
{
inOutputStream.Write(
inClientProxy->GetUnprocessedMoveList().GetLastMoveTimestamp());
inClientProxy->SetIsLastMoveTimestampDirty(false);
}
}
For each incoming input packet, the server calls HandleInputPacket, which calls the move lists’s AddMoveIfNew on each move in the packet. AddMoveIfNew checks each move’s timestamp to see if it is newer than the most recently received move. If so, it adds the move to the move list and updates the list’s most recent timestamp. If AddMoveIfNew added any moves, HandleInputPacket marks the most recent timestamp as dirty so that the NetworkManager will know the client should be sent this timestamp. When it is finally time for theNetworkManager to send a packet to the client, it checks to see if the timestamp for the client is dirty. If it is, it writes the cached timestamp from the move list into the packet. When the client receives this timestamp on the other end, it subtracts the timestamp from its current time, giving it an exact measure of how much time passed between when it sent its input to the server and when it received a corresponding response.
Dead Reckoning
Most aspects of a game simulation are deterministic, so the client can simulate them simply by executing a copy of the server’s simulation code. Bullets fly through the air in the same way on both the server and the client. Balls bounce off walls and floors and obey the same laws of gravity. If the client has a copy of the AI code, it can even simulate AI-driven game objects to keep them in sync with the server. However, there is one class of objects that is completely nondeterministic and impossible to simulate perfectly: human players. There is no way the client can know what remote players are thinking, what actions they will initiate, or where they will move. This puts a kink in the extrapolation plan. In this scenario, the best solution is for the client to make an educated guess, and then correct this guess as necessary when an update arrives from the server.
In a networked game, dead reckoning is the process of predicting an entity’s behavior based on the assumption that it will keep doing whatever it’s currently doing. If this is a running player, it means assuming the player will keep running in the same direction. If it’s a banking plane, it means assuming it will keep banking.
When the simulated object is controlled by a player, dead reckoning requires running the same simulation that the server is running, but in the absence of changing player input. This means that in addition to replicating the pose of player-controlled objects, the server must replicate any variables used by the simulation to calculate future poses. This includes velocity, acceleration, jump state, or more, depending on the specifics of your game.
As long as remote players continue doing exactly what they’re doing, dead reckoning allows clients’ games to accurately predict the current true world state on the server. However, when remote players take unexpected actions, the client simulation diverges from the true state, and must be corrected. Given that dead reckoning makes assumptions about behavior on the server before having all the facts, dead reckoning is not considered a conservative algorithm. It is instead known as an optimistic algorithm. It hopes for the best, guesses right most of the time, but sometimes is completely wrong and must adjust. Figure 8.5 illustrates this.
Figure 8.5 Dead reckoning misprediction
Assume an RTT of 100 ms and a frame rate of 60 frames per second. At time 50 ms, Client A receives information that Player B is at position (0, 0), running in the positive X direction at 1 unit per millisecond. Because this state is behind by 1/2 RTT, it simulates Player B’s continued running at a constant speed for 50 ms before displaying Player B’s position as (50, 0). Then, while waiting four frames for another state packet, it continues to simulate Player B’s run each frame. By the fourth frame, at time 117 ms, it has predicted that Player B should be at (117, 0). It then receives a packet from the server replicating Player B’s velocity as (1, 0) and pose as (67, 0). The client again simulates ahead for 1/2 RTT and finds that the position matches what it expected.
All is well. It continues the simulation for another four frames at which point it predicts Player B to be at (184, 0). However, at that point, it receives new state from the server dictating that Player B’s position is (134, 0) but that his velocity has changed to (0, 1). Player B most likely stopped running forward and started strafing. Simulating ahead by 1/2 RTT yields a position of (134, 50), not at all what dead reckoning on the client previously predicted. Player B took an unexpected, unpredictable action, and as such, Client A’s local simulation diverged from the true state of the world.
When a client detects that its local simulation has grown inaccurate, there are three ways it can remedy the situation:
Instant state update. Simply update to the new state immediately. The player may notice the object jumping around, but that might be preferable to having inaccurate data. Remember that even after the immediate update, the state from the server is still 1/2 RTT old, so the client should use dead reckoning and the latest state to simulate it another 1/2 RTT.
Interpolation. Taking a page from the client side interpolation method, your game can smoothly interpolate to the new state over a set number of frames. This could mean calculating and storing a delta to each incorrect state variable (position, rotation, etc.) that should be applied in each frame. Alternatively, you could just move the object part way to the corrected position and wait for future state from the server to continue the correction. One popular method is to use cubic spline interpolation to create a path that matches both position and velocity to transition smoothly from the predicted state to the corrected state. There is more in-depth information on this technique in the “Additional Readings” section.
Second-order state adjustment. Even interpolation may be jarring if it suddenly ramps up the velocity of a near-stationary object. To be more subtle, your game can adjust second-order parameters like acceleration to very gently ease the simulation back in sync. This can be mathematically complex, but can provide the least noticeable corrections.
Typically, games will use a combination of these methods, based on the magnitude of the divergence and on the specifics of the game. A fast-paced shooter will usually interpolate for a small error and teleport for a large. A slower-paced game like a flight simulator or giant robot mech title might use second-order state adjustment for all but the largest errors.
Dead reckoning works well for remote players, because the local player doesn’t actually know exactly what remote players are doing. When Player A watches Player B’s avatar run across the screen, the simulation diverges every time Player B changes direction, but that’s very hard for Player A to determine; without being in the same room as Player B, Player A doesn’t actually know when Player B is changing input. For the most part, she sees the simulation as consistent, even though the client application is always guessing at least 1/2 RTT ahead of whatever the server has told it.
Client Move Prediction and Replay
Dead reckoning cannot hide latency for a local player. Consider the case of Player A, on Client A, starting to run forward. Dead reckoning uses state sent by the server to simulate, so from the time she pushes forward, it takes 1/2 RTT for the input to get to server, at which point the server adjusts her velocity. Then it takes 1/2 RTT for the velocity to get back to Client A, at which point the game can use dead reckoning. There’s still a lag of RTT between when a player presses a button and when that player sees results.
There is a better alternative. Player A enters all her input directly into Client A, so the game on Client A can just use that input to simulate her avatar. As soon as Player A pushes a button to run forward, the client can start simulating her run. When the input packet reaches the server, it can begin the simulation as well, updating Player A’s state accordingly. Not everything is so simple though.
A problem arises when the server sends a packet back to Client A containing Player A’s replication state. Remember that when using client side prediction, all incoming state should be simulated an additional 1/2 RTT to catch up to the true state of the world. When simulating remote players, the client can just use dead reckoning and update assuming no change in input. Typically the updated incoming state will match the exact state the client has already predicted—if it doesn’t, the client can smoothly interpolate the remote player into place. This won’t work for local players. Local players know exactly where they are and will notice interpolation. They should not experience drifting or smoothing whenever they change their input. Ideally, moving around should feel to a local player like she is playing a single player, non-networked game.
One possible solution to this problem is to completely ignore the server’s state for the local player. Client A can derive Player A’s state solely from its local simulation, and Player A will have a smooth movement experience, with no latency. Unfortunately, this can cause Player A’s state to diverge from the server’s true state. If Player B bumps into Player A, there is no way for Client A to accurately predict the server’s resolution of the collision. Only the server knows Player B’s true position. Client A has a dead reckoned approximation of Player B’s position, so cannot resolve the collision in exactly the same way the server would. Player A might end up in a pit of fire on the server, yet free and clear on the client, which can lead to much confusion. Because Client A ignores all incoming Player A state, there would be no way for the client and server to ever sync up again.
Luckily, there is a better solution. When Client A receives Player A’s state from the server, Client A can use Player A’s inputs to resimulate any state changes Player A instigated since the server calculated the incoming state. Instead of simulating the 1/2 RTT using dead reckoning, the client can simulate the 1/2 RTT using the exact input Player A used when the client side simulation originally ran. By introducing the concept of a move, input state tied to a timestamp, the client can keep track of what Player A was doing at all times. Whenever incoming state arrives for a local player, the client can figure out which moves the server did not yet receive when calculating that state, and then apply those moves locally. Unless there was an encounter with an unexpected, remote player initiated event, this should end up with the same state the client had already locally predicted.
To extend Robo Cat Action with support for move replay, the first step is for the client to hold on to moves in the move list until the server has incorporated them into its simulation of state. Listing 8.2 shows the necessary changes to do so.
Listing 8.2 Retaining Moves
void NetworkManagerClient::SendInputPacket()
{
const MoveList& moveList = InputManager::sInstance->GetMoveList();
if(moveList.HasMoves())
{
OutputMemoryBitStream inputPacket;
inputPacket.Write(kInputCC);
mDeliveryNotificationManager.WriteState(inputPacket);
//write the 3 latest moves for added reliability!
int moveCount = moveList.GetMoveCount();
int firstMoveIndex = moveCount - 3;
if(firstMoveIndex < 3)
{
firstMoveIndex = 0;
}
auto move = moveList.begin() + firstMoveIndex;
inputPacket.Write(moveCount - firstMoveIndex, 2);
for(; firstMoveIndex < moveCount; ++firstMoveIndex, ++move)
{
move->Write(inputPacket);
}
SendPacket(inputPacket, mServerAddress);
}
}
void
NetworkManagerClient::ReadLastMoveProcessedOnServerTimestamp(
InputMemoryBitStream& inInputStream)
{
bool isTimestampDirty;
inInputStream.Read(isTimestampDirty);
if(isTimestampDirty)
{
inPacketBuffer.Read(mLastMoveProcessedByServerTimestamp);
mLastRoundTripTime = Timing::sInstance.GetFrameStartTime()
- mLastMoveProcessedByServerTimestamp;
InputManager::sInstance->GetMoveList().
RemovedProcessedMoves(mLastMoveProcessedByServerTimestamp);
}
}
void MoveList::RemovedProcessedMoves(
float inLastMoveProcessedOnServerTimestamp)
{
while(!mMoves.empty() &&
mMoves.front().GetTimestamp() <=
inLastMoveProcessedOnServerTimestamp)
{
mMoves.pop_front();
}
}
Notice how SendInputPacket no longer clears the move list as soon as it sends the packet. Instead, it holds on to the moves so it can use them for move replay after receiving server state. As an added bonus, because moves now persist for more than a packet, the client sends the three most recent moves in the list. That way, if any input packets are dropped on the way to the server, the moves will have two more chances to make it through. This doesn’t guarantee reliability but it significantly increases the chances.
When the client receives a state packet, it uses ReadLastMoveProcessedOnServerTimestamp to process any move timestamp the server might have returned. If it finds one, it subtracts the timestamp from the current time to measure RTT, which is useful for dead reckoning. It then calls RemovedProcessedMoves to remove any moves marked as at or before that timestamp. That means that after ReadLastMoveProcessedOnServerTimestamp completes, the client’s local move list contains only moves which the server has not yet seen, and thus should be applied to any incoming state from the server. Listing 8.3 details the additions to the RoboCat::Read() method.
Listing 8.3 Replaying Moves
void RoboCatClient::Read(InputMemoryBitStream& inInputStream)
{
float oldRotation = GetRotation();
Vector3 oldLocation = GetLocation();
Vector3 oldVelocity = GetVelocity();
//... Read State Code Omitted ...
bool isLocalPlayer =
(GetPlayerId() == NetworkManagerClient::sInstance->GetPlayerId());
if(isLocalPlayer)
{
DoClientSidePredictionAfterReplicationForLocalCat(readState);
}
else
{
DoClientSidePredictionAfterReplicationForRemoteCat(readState);
}
//if this is not a create packet, smooth out any jumps
if(!IsCreatePacket(readState))
{
InterpolateClientSidePrediction(
oldRotation, oldLocation, oldVelocity, !isLocalPlayer);
}
}
void RoboCatClient::DoClientSidePredictionAfterReplicationForLocalCat(
uint32_t inReadState)
{
//replay moves only if we received new pose
if((inReadState & ECRS_Pose) != 0)
{
const MoveList& moveList = InputManager::sInstance->GetMoveList();
for(const Move& move : moveList)
{
float deltaTime = move.GetDeltaTime();
ProcessInput(deltaTime, move.GetInputState());
SimulateMovement(deltaTime);
}
}
}
void RoboCatClient::DoClientSidePredictionAfterReplicationForRemoteCat(
uint32_t inReadState)
{
if((inReadState & ECRS_Pose) != 0)
{
//simulate movement for an additional RTT
float rtt = NetworkManagerClient::sInstance->GetRoundTripTime();
//split into framelength sized chunks so we don't run through walls
//and do crazy things...
float deltaTime = 1.f / 30.f;
while(true)
{
if(rtt < deltaTime)
{
SimulateMovement(rtt);
break;
}
else
{
SimulateMovement(deltaTime);
rtt -= deltaTime;
}
}
}
}
The Read method begins by storing the current state of the object, so that the method can know later if any adjustments requiring smoothing occurred. It then updates state by reading it in from the packet as described in earlier chapters. After the update, it applies client side prediction to advance the replicated state by 1/2 RTT. If the replicated object is controlled by a local player, it calls DoClientSidePredictionAfterReplicationForLocalCat to run move replay. Otherwise, it calls DoClientSidePredictionAfterReplicationForRemoteCat to run dead reckoning.
DoClientSidePredictionAfterReplicationForLocalCat first checks to make sure that a pose was replicated. If not, there is no need to advance the simulation. If there was a pose, the method iterates through all remaining moves in the move list and applies them to the localRoboCat. This simulates all player actions that the server has not factored into its simulation yet. If nothing unexpected happened on the server, this function should leave the local cat’s state exactly how it was before the Read method processed the packet in the first place.
If the cat being replicated is remote, the DoClientSidePredictionAfterReplicationForRemoteCat method advances the simulation using the latest known state for the cat. This consists of calling SimulateMovement for the appropriate amount of time without any associated ProcessInput calls. Again, if nothing unexpected happened on the server, this should also result in state that matches the state before the Read method began. However, unlike for local cats, it is very likely that something unexpected happened; remote players are always performing actions such as changing direction, speeding up or slowing down, and so on.
After performing client side prediction, the Read() method finally calls InterpolateClientSidePrediction() to handle any state that may have changed. By passing in old state, the interpolation method can decide how much, if at all, it should smooth out the change from old state to new state.
Hiding Latency through Tricks and Optimism
Delayed movement is not the only indication of latency to a player. When a player presses the button to shoot a gun, she expects her gun to fire immediately. When she tries to cast an attack spell, she expects her avatar to throw a big ball of fire. Move replay does not handle a situation like this, so something else is necessary. It’s usually too complicated for the client to create projectiles in a way that the server can take over replicating their state once it creates them itself—there is a simpler solution.
Almost all video game actions have tells, or visual cues that indicate something is happening. Muzzle flashes precede plasma blasts, and mages wave their hands and mumble before spraying fire. These tells usually last at least as long as a round trip to the server and back. This means that, optimistically, the client application can give a local player instant feedback to any input by playing the appropriate animation and effects locally, while waiting for the true simulation to be updated on the server. This doesn’t mean that the client spawns projectiles, but it does start playing the spell casting animation and sound. If all is well, during the spell casting, the server receives the input packet, spawns the fire ball, and replicates it to the client, in time to show up as a result of the spell casting. Dead reckoning code advances the projectile forward by 1/2 RTT and it looks to the player as if she threw a fireball with no latency. If there is a problem, for instance, if the server knows that the player was recently silenced but hasn’t yet replicated that to the player, the optimism proves unwarranted and the spell casting animation fires without a projectile appearing. This is a rare case though, and well worth the benefit typically provided.
Server Side Rewind
Using these various client side prediction techniques, your game can provide a fairly responsive experience to players, even in the presence of moderate latency. However, there is still one common type of game action which client side prediction does not handle perfectly: the long range, instant-hit weapon. When a player equips a sniper rifle, perfectly positions the reticle over another player, and pulls the trigger, she expects a perfect hit. However, due to the inaccuracies of dead reckoning, it is possible that a perfectly lined up shot on the client is not a perfectly lined up shot on the server. This can be a problem for games that rely on realistic, instant-hit weapons.
There is a solution to this, made popular by Valve’s Source Engine, and responsible for the accuracy players feel when firing weapons in games like Counter-Strike. At its core, it works by rewinding state on the server to exactly the state the player perceived when lining up a shot and firing. That way, if the player perceived that she aimed perfectly, her shot will hit 100% of the time.
To accomplish this feat, the game must make a few adjustments to the client side prediction methods discussed earlier:
Use client side interpolation without dead reckoning for remote players. The server needs to have accurate knowledge of exactly what client players see at any time. Because dead reckoning relies on the client advancing the simulation based on its assumptions, it would cause extra complexity for the server, and thus should be turned off. To prevent any jerkiness or stuttering between packets, the client instead uses client side interpolation as described earlier in this chapter. The interpolation period should be exactly equal to the packet period, which is tightly controlled by the server. Client side interpolation introduces additional latency, but it turns out this is not significantly noticed by the player because of move replay and the server side rewind algorithm.
Use local client move prediction and move replay. Although client side prediction is disabled for remote players, it must remain on for the local player. Without local move prediction and move replay, the local player would instantly notice both the latency from network traffic and the increased latency from the client side interpolation. However, by simulating player moves immediately, the local player never feels lagged, regardless of how much latency there is.
Record the client’s view in each move packet sent to the server. The client should stamp every input packet sent with the IDs of the frames between which the client is currently interpolating, and the percentage of the interpolation that is complete. This gives the server an exact indication of the client’s perception of the world at the time.
On the server, store the poses of every relevant object for the last several frames. When a client input packet comes in containing a shot, look up the two stored frames between which the client was interpolating at the time of the shot. Use the interpolation percentage in the packet to rewind all relevant objects to exactly where they were when the client pulled the trigger. Then perform a ray cast from the client’s position to determine if the shot landed.
Server side rewind guarantees that if the client player lined up a shot correctly, it will land on the server. This gives a very satisfying feeling to the shooting player. However, it does not come without drawbacks. Because it rewinds server time by an amount based on the latency between server and client, it can end up causing some unexpected and frustrating experiences for the victims of the shots. Player A may think she has safely ducked around a corner, taking refuge from Player B. However, if Player B is on a particularly laggy network connection, he might have a view of the world that is 300 ms behind that of Player A. Thus on his computer, Player A may not have ducked behind the corner yet. If he lines up the shot and fires, the server will credit a hit to him and alert Player A that she was shot, even though she believed she was safely around a corner. As for all things in game development, it is a tradeoff. Only use these techniques if it is appropriate based on the specifics of your game.
Summary
Although stuttering and lag can ruin a multiplayer game experience, there are several strategies which help mitigate the problems. These days, it is practically required that a multiplayer game make use of one or more of these techniques.
Client side interpolation with a local perception filter smoothens out incoming state updates by interpolating to them instead of immediately presenting them to the client. An interpolation period equal to the period between state updates will provide the player with a consistently updating state, but will increase the player’s perception of latency. It will never show the user an incorrect state.
Client side prediction uses extrapolation instead of interpolation to mask latency and keeps the client’s game state in sync with the server’s true game state. State updates are at least 1/2 RTT old by the time they reach the client, so the client can approximate the true game state by extrapolating the simulation for a duration of 1/2 RTT past the incoming state.
Through dead reckoning, a client uses the last known state of an object to extrapolate future state. It optimistically assumes remote players have not changed their input. Inputs change often, though, so the server does frequently send state to the client that differs from its approximation. When this happens, the client has many ways to factor this changed state into its own simulation, and update what it shows to the player.
Through move prediction and replay, a client can instantly simulate the results of local player input. When receiving local player state from the server, the client advances the state 1/2 RTT by replaying any move the player has made that the server has not yet processed. In most cases, this brings the replicated state into sync with the simulated client state. In the case of unexpected, server side events, like collisions with other players, the client can smooth the replicated, corrected state back into its local simulation.
For the ultimate in lag compensation when dealing with instant-hit weapons, games can employ server side rewind. The server buffers object positions for several frames and actually rewinds state to match the client’s view when processing instant-hit weapon fire. This gives an increased feeling of precision to the shooter, but can result in targeted players taking damage even after they perceive they have safely taken cover.
Review Questions
1. What is meant by the term dumb client? What is the main benefit of a game which uses dumb clients?
2. What is the main advantage of client side interpolation? What is the main drawback?
3. On a dumb client, the state presented to the user is at least how much older than the true state running on the server?
4. What is the difference between a conservative algorithm and an optimistic algorithm? Give an example of each.
5. When is dead reckoning useful? How does it predict the positions of objects?
6. Give three ways to correct predicted state when it turns out to be incorrect.
7. Explain a system which allows a local player to experience no lag at all regarding their own movement.
8. What problem does server side rewind solve? What is its main advantage? What is its main disadvantage?
9. Expand Robo Cat Action with an optional instant-hit yarn ball and implement server side rewind hit detection.
Additional Readings
Aldridge, David. (2011, March). Shot You First: Networking the Gameplay of HALO: REACH. Retrieved from http://www.gdcvault.com/play/1014345/I-Shot-You-First-Networking. Accessed September 12, 2015.
Bernier, Yahn W. (2001) Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization. Retrieved from https://developer.valvesoftware.com/wiki/Latency_Compensating_Methods_in_Client/Server_In-game_Protocol_Design_and_Optimization. Accessed September 12, 2015.
Caldwell, Nick. (2000, February) Defeating Lag with Cubic Splines. Retrieved from http://www.gamedev.net/page/resources/_/technical/multiplayer-and-network-programming/defeating-lag-with-cubic-splines-r914. Accessed September 12, 2015.
Carmack, J. (1996, August). Here is the New Plan. Retrieved from http://fabiensanglard.net/quakeSource/johnc-log.aug.htm. Accessed September 12, 2015.
Sweeney, Tim. Unreal Networking Architecture. Retrieved from https://udn.epicgames.com/Three/NetworkingOverview.html. Accessed September 12, 2015.