Home

Nice graphics are good to draw attention, but underneath, the physics do the real fun job.

Introduction

This page tells a bit about the interpolation done in Racer for multiplayer. The multiplayer code has 2 parts - linear interpolation and splined interpolation. Linear interpolation is simpler and is quite useful for LAN playing, but requires slightly higher update rates.

Linear interpolation

A good page to read would be the page on Valve's Half Life 2 multiplayer networking. Racer follows a similar method, only where Valve will use the last 2 packets and interpolate between those in Half Life 2, Racer uses the last packet to predict the car locations, rather than to lag too much behind. This is hopefully helpful when 2 cars are racing close to eachother and touching.

To explain Racer's linear interpolation, review the image below:

2 packets are remembered by Racer; the latest incoming packet with position & velocity information, and the one before that ('prevPos' above). If you would just take the latest packet and interpolate from there, you'd get a small jump every time a packet arrives.

To deal with that, the 2 latest packets are used. Here is what happens above:

• At t=900, a packet came in, and interpolation is used to determine the car position: curPos = prevPos+t*vel.
• The mean time between packets is set to 100ms (10Hz), so we expect another packet around t=1000.
• The packet arrives a bit sooner, at around t=980. We then calculate where the car currently is shown, to avoid a jump. Racer will keep interpolating 'prevPos' but it will transition to the new packet's path.
• The new packet indicates that at t=1000, the car was at 'lastPos'. We remember at what time the packet came in, to make an interpolation for the red line. Each step, we calculate where the previous path would lead us (prevPos+prevVel*time_since_prevPos) and also the new path (lastPos+lastVel*time_since_lastPos). Then we interpolate with time_since_last_packet_arrived from the 'prev' path to the 'last' path. This time factor should normally go from 0 to 1 within the period we expect a new packet to arrive again. To calculate this value we use: time_since_last_packet_arrived=current_time-time_of_last_packet_arrival)/time_per_network_update, where time_per_network_update is typically around 10-100ms.
• So we slowly (in the period upto the next packet's arrival) interpolation from the 'prev' path towards the 'last' path. The nice thing is that we don't get too much jumping of the car, since it will create a new path to end up at the latest 'lastPos' path to correct things. At that time, we receive a new packet and shift 'lastPos' to 'prevPos' (and also velocity and arrival time).
• A good extra interpolation is to use time_since_last_packet_arrived to interpolate 'prevVel' towards 'lastVel' and use the interpolated result to calculate the point on the line starting at 'prevPos'.

This all works quite nicely in practice. There is some flux due to network timings changing, but it is very low.

Timing in linear interpolation

Note the above method is not that trivial. We use 2 separate timings:

• The server time at which a car was at position X. This is used to generate car positions based on 'prevPos' and 'lastPos'.
• The local client time; this is used to calculate the interpolation amount from the 'prev' path to the 'last' path (last=last packet that arrived, prev=the packet before that). We want to interpolate from prev -> last using the local time so it goes nicely from 0..1. If we'd use server time we would always lag ping_time/2, so you'd get a jump in position since at the first render, you get time_since_last_packet_arrived having a value quite larger than 0 already.
  Also, make sure to clamp time_since_last_packet_arrived between 0 and 1; values outside that make no sense, since this variable is about the transition from the 'prev' path and the 'last' path. Once 1.0, keep it clamped to 1.0 so that you fully use the last path.

Time syncing

The above method requires each multiplayer client to be clock-synced to the server. In LAN, we achieve around 5 milliseconds accuracy using the following method (it's a bit dependent on framerate really). It's a bit like a simple NTP protocol.

• The server sends out a sync request message to a client, sending the server clock time (REQ).
• The client responds with it's local clock time, and it also returns the server's clock time (ACK).
• The server receives back the ACK (acknowledge) and can figure out ping time and clock offset: ping time is the current server clock time minus the returned packet's clock time. The clock offset is the server clock time minus the local client time (all in the packet) plus half the ping time (to get the packet to the client).
• The server uses each client offset to generalise a 'server time' for incoming packets. Before sending updates through, state update packets get converted to 'server time'.
• The clients similarly can convert packets to server time by adding the same time offset. A client can calculate it's time offset using the same sync method, but Racer's server will send out the time offset as perceived by the server. This keeps the time offset quite the same on clients and server, giving optimal server time calculations.

Note that you have to filter the resulting times a bit to avoid sudden jumps in the time offsets. For LAN, this is not too important though.

Source code

As always, some source code goes a long way, especially if the above text is a bit unclear. It's not entirely wonderfully styled; the 'last' packet data is in the variables 'lastPos' and 'vel'. The previous packet's data is in 'prevPos' and 'prevVel'. Upon reception of a new packet, a function is called which stores things like 'prevPacketTime' and such. 'prevPacketTime' is the server time which was in the packet, 'lastPacketTime' is the time in the last received packet (in server time, just like 'prevPacketTime'). lastSimTime is the simulation time at which the last packet was received, and RMGR->time->GetSimTime() gets the current simulation time (in milliseconds).

Here's my prediction function:

void RNetworkInfo::PredictLinear(RCar *car)
// Predict the state (position/orientation) of the car at the current time
// This is really prediction - whereas Half-Life 2 uses interpolation between the last 2 packets,
// we try to keep with the real current position, to improve collisions (and cars
// don't generally move around that fast, derivative-of-acceleration-wise (jerk) )
{
   // Try to predict current positon
   DVector3 *pos=car->GetPosition();
   int       tServer;                // This is in milliseconds (int)
   rfloat    t,
              tSinceLastPacket,       // Time since last packet's event time
              tSinceLastUpdate,       // Time (in real server time) since last update was received
              tSincePrevPacket,       // Time since previous packet's event time
              tLerp;                  // Interpolation from previous packet's position to currently predicted packet position
   RNetworkInfo *ni=car->GetNetworkInfo();

   // Time since last packet info
   tServer=RMGR->network->GetServerTime();
   tSincePrevPacket=(tServer-prevPacketTime)*0.001f;
   tSinceLastPacket=(tServer-lastPacketTime)*0.001f;
   tSinceLastUpdate=(RMGR->time->GetSimTime()-lastSimTime)*0.001f;

   // Calculate time to interpolate from the previous path
   // to ideal (last) packet's path
   tLerp=tSinceLastUpdate/(float(RMGR->timePerNetworkUpdate)*0.001f);
   rfloat tLerpRaw=tLerp;

   // Clamp to 0..1 - it's just about the previous -> last path so no prediction or history
   if(tLerp<0)tLerp=0;
   else if(tLerp>1.0f)tLerp=1.0f;

   // Cache 1-tLerp
   rfloat oneMinusTlerp=1.0f-tLerp;

   //
   // Linear interpolation - should be perfect for static linear velocity tests with 1 server and 1 client
   // More clients will mean the clock varies a bit from clients -> srv -> other clients
   //
   t=Limiter(tSinceLastPacket);

   // Calculate current position based on packet info
   DVector3 posLast,posPrev;
   posLast.x=lastPos.x+vel.x*t;
   posLast.y=lastPos.y+vel.y*t;
   posLast.z=lastPos.z+vel.z*t;

   // Calculate predicted previous position - use time since last interpolation time
   // Calculate interpolated velocity for a bit more smoothness
   DVector3 ipVel;
   ipVel.x=tLerp*vel.x+oneMinusTlerp*prevVel.x;
   ipVel.y=tLerp*vel.y+oneMinusTlerp*prevVel.y;
   ipVel.z=tLerp*vel.z+oneMinusTlerp*prevVel.z;

   t=Limiter(tSincePrevPacket);
   posPrev.x=prevPos.x+ipVel.x*t;
   posPrev.y=prevPos.y+ipVel.y*t;
   posPrev.z=prevPos.z+ipVel.z*t;

   // Calculate position, interpolating from posPrev -> posLast as time goes by
   // to correct towards the last received packet
   curPos.x=tLerp*posLast.x+oneMinusTlerp*posPrev.x;
   curPos.y=tLerp*posLast.y+oneMinusTlerp*posPrev.y;
   curPos.z=tLerp*posLast.z+oneMinusTlerp*posPrev.z;

   *pos=curPos;

   // Use a different method for orientation, which interpolates
   // the rotation from the previous to the new quat.
   // Use unclamped lerp from prev->last since we want prediction
   t=tLerpRaw;       // limit this a bit?
   // Calculate interpolant into 'quat' (current value)
   prevQuat.Slerp(&lastQuat,t,&quat);
}

(last updated November 13, 2012 )