Lag Compensation - Fair Play for all Pings

In multiplayer games it is common for players to have high ping times to the game server. This means that the world the player sees is slightly behind what the server sees and this leads to problems with hit detection.

This article explains the lag compensation system used in Sector's Edge that improves hit-detection accuracy for players with high ping time.

The full source code for this system is available on GitHub here.

Terminology

• Tick - a 50 millisecond time span
• Tick Lag - how many Ticks the client is behind the server
• Player - a player-controlled character
• Entity - a moving player, grenade, scanner, etc.
• Record - an object that stores the state of all entities at a certain timestamp
• History - the object that manages lag compensation and stores Records
• Message - a network message sent from the client to the server

Overview

Sector's Edge uses the Lidgren C# networking library, which provides the ping time for each player. Traditionally, we would use this ping time to calculate the player's Tick Lag, however this value can fluctuate and doesn't account for player position smoothing and other factors on the client.

Instead, the server stores a Record every tick (50ms) that contains information about every entity's position and state. The client periodically sends the position of a random moving entity to the server, whether it be a player, grenade, scanner, etc. The server will then use this position to determine the player's Tick Lag.

Records that are older than 400ms are discarded for anti-cheat purposes. Players with > 400ms ping will not benefit from lag compensation.

For example, the server is currently running at Tick 9 and a client states that player K is at position 2.5 (the red dotted line):

The server will then look through its History for player K and determine that the client is currently running at around Tick 7.25. This means that the client has a Tick Lag of 1.75 Ticks (about 88ms ping).

In the case that multiple matching positions are found, the most recent position will be used.

The past 20 Tick Lag values are stored for each Player. To minimise fluctuations, the average value of the Tick Lag history is used when calculating hit detection:

public class Player
{
    const int TICK_TIME = 50;
    const int LAG_HISTORY_MAX = 20;    
    double ping;

    List<double> TickLagHistory = new List<double>();
    double AccumulatedTickLag = 0;

    public void AddTickLag(double d)
    {
        TickLagHistory.Add(d);
        
        AccumulatedTickLag += d;

        if (TickLagHistory.Count > LAG_HISTORY_MAX)
        {
            AccumulatedTickLag -= TickLagHistory[0];
            TickLagHistory.RemoveAt(0);
        }
    }
    
    public double AverageTickLag
    {
        get
        {
            // Use ping as an approximation until TickLagHistory is populated
            if (TickLagHistory.Count < LAG_HISTORY_MAX)
                return ping / TICK_TIME;

            return AccumulatedTickLag / LAG_HISTORY_MAX;
        }
    }
}

It takes 1000ms for TickLagHistory to populate when a player first connects to the server. Until it is populated, the player's ping will be used as an approximation.

Note that List<double> can be replaced with a ring buffer as an optimisation.

System Structure

The structure of the GameServer, Record and the History class are as follows:

public class GameServer
{
    List<Player> Players;
    List<Projectile> Projectiles;
    History history;
    
    Stopwatch tickWatch = new Stopwatch();
    int PresentTick
    {
        get
        {
            return (int)(tickWatch.ElapsedMilliseconds / TICK_TIME);
        }
    }
}

public class Record
{
    public int tick;
    public List<Player> players = new List<Player>();

    // As there are 16 players max, we use a linear lookup
    public Player GetPlayer(byte ID)
    {
        for (int i = 0; i < players.Count; i++)
            if (players[i].ID == ID)
                return players[i];

        return null;
    }
}

public class History
{
    GameServer parent;
    List<Record> records;
        
    // As there are 8 records max, we use a linear lookup
    Record GetRecord(int tick)
    {
        for (int i = 0; i < records.Count; i++)
            if (records[i].tick == tick)
                return records[i];

        return records.Last();
    }
    
    Player GetPlayer(List<Player> players, byte ID) { ... }
    void ProjectileLoop(double tick, Projectile proj) { ... }
}

We also rely on interpolating between two Vector3 values, which is handled in a Helper class:

public static class Helper
{
    public static double Interpolate(double first, double second, double by)
    {
        return first + by * (second - first);
    }

    public static Vector3 Interpolate(in Vector3 first, in Vector3 second, double by)
    {
        double x = Interpolate(first.X, second.X, by);
        double y = Interpolate(first.Y, second.Y, by);
        double z = Interpolate(first.Z, second.Z, by);
        return new Vector3(x, y, z);
    }
}

The Projectile Loop

When the server receives a mouse click message from the client, it simulates the projectile through each Record in the past until it reaches the present Tick. This is called the Projectile Loop.

void HandleMouseDown(Player player)
{
    // Calculate the player's current tick
    double tick = PresentTick - player.AverageTickLag;   
    
    // Create a projectile
    Projectile proj = player.CreateProjectile();    
    
    // Process the projectile
    history.ProjectileLoop(tick, proj);
}

The ProjectileLoop function recursively checks the projectile against each Record in its history, starting at the provided tick. If the projectile doesn't collide with anything in each Record, the projectile is moved to the current list of projectiles on the GameServer, which are then updated each frame in real time.

void ProjectileLoop(double tick, Projectile proj)
{
    Record lastRecord = records.Last();
    
    // If we have checked each Record and the projectile is still alive, add it to the present
    if (tick > lastRecord.tick)
    {
        parent.Projectiles.Add(proj);
        return;
    }

    bool repeat = false;

    // If tick is 4.75, we want to interpolate 75% between the two Records
    double interpolation = tick - (int)tick;

    // Interpolate between the most recent Record and the present
    if ((int)tick == lastRecord.tick)
    {
        repeat = ProcessCollision(lastRecord.players, parent.Players, interpolation, proj);
    }

    // Interpolate between two Records
    else 
    {
        var eOld    = GetRecord((int)tick);         // Less recent
        var eRecent = GetRecord((int)tick + 1);     // More recent

        repeat = ProcessCollision(eOld.players, eRecent.players, interpolation, proj);
    }

    // Some projectiles are hitcast, which means they have infinite velocity
    // and therefore we only need to check one frame
    if (proj.IsHitCast)
        return;

    // If the projectile didn't hit anything
    if (repeat)
    {
        // Move the projectile
        proj.Position += proj.Velocity * TICK_TIME;

        // Check the next most recent record
        ProjectileLoop(tick + 1, proj);
    }
}

The player's Tick Lag is not always a whole integer and therefore the ProcessCollision function must interpolate between the player positions stored in two Records for accurate hit detection:

bool ProcessCollision(List<Player> playersOld, List<Player> playersRecent, double interpolation, Projectile proj)
{
    // We don't want to modify the player positions stored in the Record, so we use a new list
    List<Player> playerCopies = new List<Player>();

    foreach (var pOld in playersOld)
    {
        // Create a copy of the player containing only the information
        // we need for collision (position, velocity, crouching, aiming, etc)
        var pCopy = pOld.Copy();

        // Find a player with a matching ID in the more recent Record
        var pRecent = GetPlayer(playersRecent, pOld.ID);

        // If the player hasn't disconnected, interpolate their position
        // between the two ticks for more accurate collision detection
        if (pRecent != null)
            pCopy.position = Interpolate(pOld.position, pRecent.position, interpolation);

        playerCopies.Add(pCopy);
    }

    // Calculate collision, deal damage to the players and map, etc
    // Returns true if the projectile didn't hit anything
    return parent.DoCollision(proj, playerCopies);
}

Note that the parent.DoCollision() function handles collision between projectiles, the voxel map and players. This will be covered in another article.

In Practice

The full source code is available on GitHub here.

See the hit detection in action from the point of view of one of our best snipers: