Lag compensation of a player's attack, using a historical stack of quadtrees and "rewinding" relevant entities stored in the quadtrees to the position they were at in the recent past (as decided by the player's ping).There is a SIGNFICANT oddity to this code, which is that quadtrees used for collisions are point quadtrees. Because of this, the i…

lagCompensation.js

// a fat hitbox around the player considered the 'relevant' area for a collision
var hitArea = new AABB({x: player.x, y: player.y}, { x: 54, y : 54})
var actualHitArea = new AABB({x: player.x, y: player.y}, { x: 36, y : 36})

// how behind the player is, in server time
var delay = player.ping + (1000 / player.tickRate)
var tickLength = 1000 / TICKS_PER_SECOND
var ticksAgo = Math.floor(delay / tickLength)
var tickPortion = (delay % tickLength) / tickLength

// the two nearest time slices to the point in the past that the player attacked
var timeSliceA = history[tick - ticksAgo - 1]
var timeSliceB = history[tick - ticksAgo]

// get all the NPCs from the quadtree in the relevant area for both time slices
// TODO: return entities as a dictionary instead of an array
var positionsA = []
timeSliceA.queryRange(hitArea, positionsA)
var positionsB = []
timeSliceB.queryRange(hitArea, positionsB)

// copy the entity position data into a dictionary instead of an array
var entitiesA = {}
var entitiesB = {}

for (var i = 0; i < positionsA.length; i++) {
    entitiesA[positionsA[i].id] = positionsA[i]
}

for (var i = 0; i < positionsB.length; i++) {
    entitiesB[positionsB[i].id] = positionsB[i]
}


// for every NPC within area of concern...
for (var entityId in entitiesA) {
    if (isNPC(entityId)) {
        
        // if it appears in both timeSlices...
        if (entitiesB[entityId]) {
            // lerp between the position in timeSliceA and timeSliceB
            var entityA = entitiesA[entityId]
            var entityB = entitiesB[entityId]
            var x = math.lerp(entityA.x, entityB.x, tickPortion)
            var y = math.lerp(entityA.y, entityB.y, tickPortion)
            
            // create a hitbox at the lerp'd position
            var entityBox = new AABB({
                x: x,
                y: y
            }, {
                x: 18,
                y: 18
            })
            
            // see if the player hit this entity
            if (actualHitArea.intersects(entityBox)) {
                player.attack(npc[entityId])
            } 
        }
    }
}