Lag Compensation
From AntiHax
The code within this article was briefly designed for metamod running on the HalfLife engine. It has not been fully tested and if you are intending to use this in a game engine you should also be aware you will probably want to unlag other aspects of the entities such as bone positions, etc.
Lag compensation or backwards reconciliation in first person shooter games traditionally helps to reduce the effect of latency on clients when they fire a shot. Of all the algorithms and techniques used within the engine, lag compensation is one of the most important to understand, especially when developing server side cheat detections.
The need for lag compensation stems from the basic fact that the updates sent to a client about remote players locations are delayed due to the latency of the connection between the client and the server. If for example a player has a ping of 120 ms then the information received from the server will be around 60ms old and if the client shoots it will take about 60ms to get that shot to the server. In that 120 ms a player could have moved quite a distance, enough to cause a good shot to miss.
To start, the first thing needed is a record of all clients positions in previous frames so we have a reference when winding them back.
#define HISTORY_SIZE 100
#define MAXPLAYERS 32
// A position history record
struct hist_t {
vec3_t origin;
vec3_t v_angle;
float time;
};
hist_t playerOrigin[MAXPLAYERS][HISTORY_SIZE]; // for the players past positions
int playerOriginSize[MAXPLAYERS]; // Size of the players array
hist_t playerSavedOrigin[MAXPLAYERS]; // for their real position
/////////////////////////////////////////
void unlag_ClientOrigin(edict_t* player, float time) {
int pnum = ENTINDEX(player);
hist_t *h = &(playerOrigin[pnum][0]);
// Shift things to make room for the new entry
memmove(h+1,h,(HISTORY_SIZE-1)*sizeof(hist_t));
if (playerOriginSize[pnum]<HISTORY_SIZE)
playerOriginSize[pnum]++;
memcpy(h->origin,player->v.origin,sizeof(vec3_t));
memcpy(h->v_angle,player->v.v_angle,sizeof(vec3_t));
h->time = time;
// [Danni] We need to add more here, need hbox and such to be
// completely accurate.
}
/////////////////////////////////////////
void unlag_ClientReset(edict_t* player) {
int pnum = ENTINDEX(pev_ent);
playerOriginSize[pnum] = 0;
}
/////////////////////////////////////////
void PlayerPostThink(edict_t *pEntity) {
edict_t* pev_ent = ENT( &pEntity->v ); // Make it REAL
// [Danni] Record the client's position and time.
unlag_ClientOrigin(pev_ent, gpGlobals->time);
RETURN_META(MRES_IGNORED);
}
The PlayerPostThink function is triggered by the game engine every time a player’s Think function completes. We are calling unlag_ClientOrigin here with the time thus creating a timestamped entry in the player’s history array. unlag_ClientReset must also be called whenever a player respawns to prevent bad time-shifts.
Now we have a good reference of where the player was we can figure out how to make the servers view of the world, the same as the local clients at the critical time of hit scans.
There are two approaches to this;
- Send a time stamp with each update to the client, which interpolates the value when it performs Client Interpolation and returns it to the server.
- Calculate the time with ping + client interpolate delay.
For our approach we use the second method because we do not have the availability of the first. Now we know how to pick a point in the history array.
inline static vec3_t Lerp_Vec3( vec3_t p1, vec3_t p2, double t)
{
return (vec3_t) ( p1 + (p2-p1) * t );
}
/////////////////////////////////////////
void unlag_TimeShiftClient(edict_t* player, float time) {
int pnum = ENTINDEX(player);
hist_t *save = &(playerSavedOrigin[pnum]);
int i,n;
double precision;
hist_t *h, *hlo, *hhi;
// [Danni] Save the current position.
memcpy(save->origin, player->v.origin, sizeof(vec3_t));
memcpy(save->v_angle, player->v.v_angle, sizeof(vec3_t));
h = &(playerOrigin[pnum][0]);
n = playerOriginSize[pnum];
if (n<=1 || time>h[0].time)
return;
for (i=1; i<n; i++)
{
if (h[i].time < time)
{
hlo = h + (i-1);
hhi = h + i;
precision = ((double)(time - hlo->time)) /
((double)(hhi->time - hlo->time));
player->v.origin = Lerp_Vec3(hlo->origin, hhi->origin, precision);
player->v.v_angle = Lerp_Vec3(hlo->v_angle, hhi->v_angle, precision);
break;
}
}
}
/////////////////////////////////////////
void unlag_UnShiftClient(edict_t* player) {
int pnum = ENTINDEX(player);
hist_t *h = &(playerOrigin[pnum][0]);
player->v.origin = playerSavedOrigin[pnum].origin;
player->v.v_angle = playerSavedOrigin[pnum].v_angle;
}
In the unlag_TimeShiftClient function we first save away the clients present position so we can restore them later if we have to move them. Next we loop through the array of positions until we find the two elements which span the time passed to the function.
Just to be more accurate, we find the fraction between the two elements which match the unlag time and interpolate the position for this time using linear interpolation (Lerp).
Now we know the position the client was in, we physically move them back.
Once done with the unlagged state, the player must be returned to his original state with unlag_TimeShiftClient.
A simple demonstration in the proper use of this code can be seen below.
// Excuse the mess, this is a simple demo of the unlag code
static float lastCmdTime[MAXPLAYERS];
void CmdStart(const edict_t *player,
const struct usercmd_s *cmd,
unsigned int random_seed)
{
edict_t* source = ENT( &player->v );
int pnum = ENTINDEX(source);
if (gpGlobals->time - lastCmdTime[pnum] < 0.01) {
RETURN_META(MRES_IGNORED);
}
lastCmdTime[pnum] = gpGlobals->time;
int ping, loss;
g_engfuncs.pfnGetPlayerStats(player, &ping, &loss);
float nowTime = gpGlobals->time;
float interpTime = nowTime - ((ping + cmd->lerp_msec) / 1000.0f);
edict_t *target = UTIL_EntitiesInPVS( source );
// Build a list of entities in this list (pent->v.chain)
while ( !FNullEnt( target ) ) {
// Make sure we don't run on the local player
// and make sure the entities are players.
if (ENTINDEX( target ) == pnum ||
!FStrEq(STRING(target->v.classname), "player") ||
!IsAlive(target))
{
target = target->v.chain;
continue;
}
unlag_TimeShiftClient(target,interpTime);
// [Danni] Draw a box where they were
Vector mins = target->v.origin + (target->v.mins );
Vector maxs = target->v.origin + (target->v.maxs );
UTIL_DrawBox(source, mins, maxs, 250, 255, 10, 10);
unlag_UnShiftClient(target);
target = target->v.chain;
}
CmdStart is another metamod hook into the game engine and is executed every time a client usercmd is executed. Since usercmd are also what contain client shots, we want to unlag all other players based on the sender’s latency. In HalfLife and Source the usercmd contains lerp_msec which is the amount of time the client is delaying updates for interpolation, we must figure this into the calculation.
We get the players ping with g_engfuncs.pfnGetPlayerStats add lerp_msec, convert to floating point and take it away from present server time to find the unlagged time (interpTime). If the engine time functions are integers, you can omit the real type conversion.
Next we iterate the players Potential Visibility Set with UTIL_EntitiesInPVS and look for any players we need to shift. We must also ensure that we do not shift the player which is shooting because the Client Prediction ensures the local client’s position matches the servers, hence they are already in the true position.
Next we perform the time shift on a valid player and draw their bounding box at the shifted position, finally restoring him back to the proper place.
Here is a sample image of what should be seen in game with a nice amount of latency.
There are a few variations on this method, one I personally like is the idea of time stamping updates with the server’s time, interpolating it with the clients position when rendering and returning the value to the server with the shots. This provides much more accuracy.
Another variation is unlagged contexts where each players Think function is ran in the unlagged state based on their view of the world, additionally any other entity which is a child of the player, such as rockets, grenades or other projectiles also think within the same context as the player. This vastly improves collisions against other players and the accuracy of projectiles and splash damage.
