NPC Lag Compensation

Without lag compensation, when you shoot at a target, you have to take your ping time into account and aim ahead of it accordingly. So if your ping is 100ms, you have to aim for where the target's head will be in 100ms, rather than where you see it right now.

Clearly, this is less than ideal, so multiplayer Source games implement lag compensation. When calculating whether a bullet hits or not, it briefly adjusts the position of all players back by the shooter's ping, so that it calculates the bullet collision based upon exactly what the shooter saw when they fired. This effect is missing for NPCs but can be duplicated from the player lag compensation code without too much trouble.

This tutorial details all the changes required—while a lot of code is involved, 95% of it is duplicated from player lag compensation code.

ai_basenpc.h

Just before this line:

typedef CBitVec<MAX_CONDITIONS> CAI_ScheduleBits;

Add the following (taken from player_lagcompensation.cpp, but edited):

#define MAX_LAYER_RECORDS (CBaseAnimatingOverlay::MAX_OVERLAYS)

struct LayerRecordNPC
{
	int m_sequence;
	float m_cycle;
	float m_weight;
	int m_order;

	LayerRecordNPC()
	{
		m_sequence = 0;
		m_cycle = 0;
		m_weight = 0;
		m_order = 0;
	}

	LayerRecordNPC( const LayerRecordNPC& src )
	{
		m_sequence = src.m_sequence;
		m_cycle = src.m_cycle;
		m_weight = src.m_weight;
		m_order = src.m_order;
	}
};

struct LagRecordNPC
{
public:
	LagRecordNPC()
	{
		m_fFlags = 0;
		m_vecOrigin.Init();
		m_vecAngles.Init();
		m_vecMins.Init();
		m_vecMaxs.Init();
		m_flSimulationTime = -1;
		m_masterSequence = 0;
		m_masterCycle = 0;
	}

	LagRecordNPC( const LagRecordNPC& src )
	{
		m_fFlags = src.m_fFlags;
		m_vecOrigin = src.m_vecOrigin;
		m_vecAngles = src.m_vecAngles;
		m_vecMins = src.m_vecMins;
		m_vecMaxs = src.m_vecMaxs;
		m_flSimulationTime = src.m_flSimulationTime;
		for( int layerIndex = 0; layerIndex < MAX_LAYER_RECORDS; ++layerIndex )
		{
			m_layerRecords[layerIndex] = src.m_layerRecords[layerIndex];
		}
		m_masterSequence = src.m_masterSequence;
		m_masterCycle = src.m_masterCycle;
	}

	// Did player die this frame
	int						m_fFlags;

	// Player position, orientation and bbox
	Vector					m_vecOrigin;
	QAngle					m_vecAngles;
	Vector					m_vecMins;
	Vector					m_vecMaxs;

	float					m_flSimulationTime;	
	
	// Player animation details, so we can get the legs in the right spot.
	LayerRecordNPC			m_layerRecords[MAX_LAYER_RECORDS];
	int						m_masterSequence;
	float					m_masterCycle;
};

We are going to attach an NPC's lag record directly onto the NPC to prevent confusion of records, so the NPC code needs to be able to access these.

Now again in ai_basenpc.h, add the following to the CAI_BaseNPC class definition:

public:
	CUtlFixedLinkedList<LagRecordNPC>* GetLagTrack() { return m_LagTrack; }
	LagRecordNPC*	GetLagRestoreData() { if ( m_RestoreData != NULL ) return m_RestoreData; else return new LagRecordNPC(); }
	LagRecordNPC*	GetLagChangeData() { if ( m_ChangeData != NULL ) return m_ChangeData; else return new LagRecordNPC(); }
	void		SetLagRestoreData(LagRecordNPC* l) { if ( m_RestoreData != NULL ) delete m_RestoreData; m_RestoreData = l; }
	void		SetLagChangeData(LagRecordNPC* l) { if ( m_ChangeData != NULL ) delete m_ChangeData; m_ChangeData = l; }
	void		FlagForLagCompensation( bool tempValue ) { m_bFlaggedForLagCompensation = tempValue; }
	bool		IsLagFlagged() { return m_bFlaggedForLagCompensation; }

private:
	CUtlFixedLinkedList<LagRecordNPC>* m_LagTrack;
	LagRecordNPC*	m_RestoreData;
	LagRecordNPC*	m_ChangeData;
	bool		m_bFlaggedForLagCompensation;

This "lag record" is what stores an NPC's historical position and animation information.

ai_basenpc.cpp

At the bottom of the CAI_BaseNPC constructor, add this line:

m_LagTrack = new CUtlFixedLinkedList< LagRecordNPC >();

In the beginning of the CAI_BaseNPC destructor, add this line:

m_LagTrack->Purge();
delete m_LagTrack;

player.cpp/player.h

To decide what should be lag compensated, the player class has a function, WantsLagCompensationOnEntity, which returns true or false. Unfortunately, it's designed to only accept a player as its "entity" parameter… but we want it to lag compensate NPCs too. To accomplish this, we'll change it from taking only a CBasePlayer pointer to taking a CBaseEntity, which could be a player or an NPC.

Find where the function WantsLagCompensationOnEntity is defined and change the first parameter from const CBasePlayer *pPlayer to const CBaseEntity *pEntity.

Now in player.cpp, find this function at around line 682, and change the CBasePlayer parameter to CBaseEntity, as before. Replace all references to pPlayer (only in this function!) to pEntity (assuming that's what you renamed the parameter), then remove the line:

float maxDistance = 1.5 * pPlayer->MaxSpeed() * sv_maxunlag.GetFloat();

Replace it with the following:

float maxspeed;
CBasePlayer *pPlayer = ToBasePlayer((CBaseEntity*)pEntity);
if ( pPlayer )
	maxspeed = pPlayer->MaxSpeed();
else
	maxspeed = 600;
float maxDistance = 1.5 * maxspeed * sv_maxunlag.GetFloat();

That should do exactly the same for players and something similar for NPCs.

hl2mp_player.cpp/hl2mp_player.h

The same function exists, more or less identically, for hl2mp_player.h & hl2mp_player.cpp, so we'll have to fix that too. Open them both up. First in the header, find where the function WantsLagCompensationOnEntity is defined (as with player.h), and change the first parameter from const CBasePlayer *pPlayer to const CBaseEntity *pEntity.

Now in hl2mp_player.cpp, find WantsLagCompensationOnEntity. Except for a check at the start, this actually does exactly the same as the player.cpp version, so just chop everything except the first if and tell it to call the player.cpp version by using BaseClass:

bool CHL2MP_Player::WantsLagCompensationOnEntity( const CBaseEntity *pEntity, const CUserCmd *pCmd, const CBitVec<MAX_EDICTS> *pEntityTransmitBits ) const
{
	// No need to lag compensate at all if we're not attacking in this command and
	// we haven't attacked recently.
	if ( !( pCmd->buttons & IN_ATTACK ) && (pCmd->command_number - m_iLastWeaponFireUsercmd > 5) )
		return false;

	return BaseClass::WantsLagCompensationOnEntity(pEntity,pCmd,pEntityTransmitBits);
}

player_lagcompensation.cpp

Right, that's all the bits and pieces done, we can now actually do some lag compensation. Essentially, we're going to duplicate everything this class does for players, and make it work for NPCs. We'll go through all the functions in the order that they're written, adjusting and adding as necessary.

To start with, add this to the include list:

#include "ai_basenpc.h"

The first big function here is RestorePlayerTo. We're going to duplicate this, and make the duplicate work for NPCs instead. Paste this after the end of that function, just before the class definition that follows:

static void RestoreEntityTo( CAI_BaseNPC *pEntity, const Vector &vWantedPos )
{
	// Try to move to the wanted position from our current position.
	trace_t tr;
	VPROF_BUDGET( "RestoreEntityTo", "CLagCompensationManager" );
	UTIL_TraceEntity( pEntity, vWantedPos, vWantedPos, MASK_NPCSOLID, pEntity, COLLISION_GROUP_NPC, &tr );
	if ( tr.startsolid || tr.allsolid )
	{
		if ( sv_unlag_debug.GetBool() )
		{
			DevMsg( "RestorepEntityTo() could not restore entity position for %s ( %.1f %.1f %.1f )\n",
					pEntity->GetClassname(), vWantedPos.x, vWantedPos.y, vWantedPos.z );
		}

		UTIL_TraceEntity( pEntity, pEntity->GetLocalOrigin(), vWantedPos, MASK_NPCSOLID, pEntity, COLLISION_GROUP_NPC, &tr );
		if ( tr.startsolid || tr.allsolid )
		{
			// In this case, the guy got stuck back wherever we lag compensated him to. Nasty.

			if ( sv_unlag_debug.GetBool() )
				DevMsg( " restore failed entirely\n" );
		}
		else
		{
			// We can get to a valid place, but not all the way back to where we were.
			Vector vPos;
			VectorLerp( pEntity->GetLocalOrigin(), vWantedPos, tr.fraction * g_flFractionScale, vPos );
			UTIL_SetOrigin( pEntity, vPos, true );

			if ( sv_unlag_debug.GetBool() )
				DevMsg( " restore got most of the way\n" );
		}
	}
	else
	{
		// Cool, the entity can go back to whence he came.
		UTIL_SetOrigin( pEntity, tr.endpos, true );
	}
}

The private: section of the CLagCompensationManager class definition should start with the function:

void BacktrackPlayer( CBasePlayer *player, float flTargetTime );

Just under this, add:

void BacktrackEntity( CAI_BaseNPC *entity, float flTargetTime );

Next up is FrameUpdatePostEntityThink. This function is dominated by a large for loop, which we're going to duplicate and make work for NPCs instead. Add this onto the end of the function:

// Iterate all active NPCs
CAI_BaseNPC **ppAIs = g_AI_Manager.AccessAIs();
int nAIs = g_AI_Manager.NumAIs();

for ( int i = 0; i < nAIs; i++ )
{
	CAI_BaseNPC *pNPC = ppAIs[i];
	if ( !pNPC )
		continue;

	CUtlFixedLinkedList< LagRecordNPC > *track = pNPC->GetLagTrack();

	Assert( track->Count() < 1000 ); // insanity check

	// remove tail records that are too old
	int tailIndex = track->Tail();
	while ( track->IsValidIndex( tailIndex ) )
	{
		LagRecordNPC &tail = track->Element( tailIndex );

		// if tail is within limits, stop
		if ( tail.m_flSimulationTime >= flDeadtime )
			break;
		
		// remove tail, get new tail
		track->Remove( tailIndex );
		tailIndex = track->Tail();
	}

	// check if head has same simulation time
	if ( track->Count() > 0 )
	{
		LagRecordNPC &head = track->Element( track->Head() );

		// check if entity changed simulation time since last time updated
		if ( &head && head.m_flSimulationTime >= pNPC->GetSimulationTime() )
			continue; // don't add new entry for same or older time

		// Simulation Time is set when an entity moves or rotates ...
		// this error occurs when whatever entity it is that breaks it moves or rotates then, presumably?
	}

	// add new record to track
	LagRecordNPC &record = track->Element( track->AddToHead() );

	record.m_fFlags = 0;
	if ( pNPC->IsAlive() )
	{
		record.m_fFlags |= LC_ALIVE;
	}

	record.m_flSimulationTime	= pNPC->GetSimulationTime();
	record.m_vecAngles			= pNPC->GetLocalAngles();
	record.m_vecOrigin			= pNPC->GetLocalOrigin();
	record.m_vecMaxs			= pNPC->WorldAlignMaxs();
	record.m_vecMins			= pNPC->WorldAlignMins();

	int layerCount = pNPC->GetNumAnimOverlays();
	for( int layerIndex = 0; layerIndex < layerCount; ++layerIndex )
	{
		CAnimationLayer *currentLayer = pNPC->GetAnimOverlay(layerIndex);
		if( currentLayer )
		{
			record.m_layerRecords[layerIndex].m_cycle = currentLayer->m_flCycle;
			record.m_layerRecords[layerIndex].m_order = currentLayer->m_nOrder;
			record.m_layerRecords[layerIndex].m_sequence = currentLayer->m_nSequence;
			record.m_layerRecords[layerIndex].m_weight = currentLayer->m_flWeight;
		}
	}
	record.m_masterSequence = pNPC->GetSequence();
	record.m_masterCycle = pNPC->GetCycle();
}

At the top of StartLagCompensation, just under m_RestorePlayer.ClearAll();, add:

int nAIs = g_AI_Manager.NumAIs();
CAI_BaseNPC **ppAIs = g_AI_Manager.AccessAIs();
for (int i=0; i<nAIs; i++)
	ppAIs[ i ]->FlagForLagCompensation(false);

This function ends with a for loop, commented with:

// Iterate all active players

Remove it and replace it with two of:

// Iterate all active players
const CBitVec<MAX_EDICTS> *pEntityTransmitBits = engine->GetEntityTransmitBitsForClient( player->entindex() - 1 );
for ( int i = 1; i <= gpGlobals->maxClients; i++ )
{
	CBasePlayer *pPlayer = UTIL_PlayerByIndex( i );
	if ( !pPlayer || player == pPlayer )
		continue;

	// Custom checks for if things should lag compensate (based on things like what team the player is on).
	if ( !player->WantsLagCompensationOnEntity( pPlayer, cmd, pEntityTransmitBits ) )
		continue;

	// Move other player back in time
	BacktrackPlayer( pPlayer, TICKS_TO_TIME( targettick ) );
}

// also iterate all monsters
for ( int i = 0; i < nAIs; i++ )
{
	CAI_BaseNPC *pNPC = ppAIs[i];
	// Custom checks for if things should lag compensate
	if ( !pNPC || !player->WantsLagCompensationOnEntity( pNPC, cmd, pEntityTransmitBits ) )
		continue;
	
	// Move NPC back in time
	BacktrackEntity( pNPC, TICKS_TO_TIME( targettick ) );
}

We only want to do one thing to BacktrackPlayer, and that check for entities also where we check for players that we might be bumping into. Find:

// don't lag compensate the current player
if ( pHitPlayer && ( pHitPlayer != m_pCurrentPlayer ) )	
{

After the closing bracer of that if (that is, the } matching its {), add this else statement:

else
{
	CAI_BaseNPC *pHitEntity = dynamic_cast<CAI_BaseNPC *>( tr.m_pEnt );
	if ( pHitEntity )
	{
		CAI_BaseNPC *pNPC = NULL;
		CAI_BaseNPC **ppAIs = g_AI_Manager.AccessAIs();
		int nAIs = g_AI_Manager.NumAIs();
		for ( int i = 0; i < nAIs; i++ ) // we'll have to find this entity's index though :(
		{
			pNPC = ppAIs[i];
			if ( pNPC == pHitEntity )
				break;
		}
		// If we haven't backtracked this player, do it now
		// this deliberately ignores WantsLagCompensationOnEntity.
		if ( pNPC && !pNPC->IsLagFlagged() )
		{
			// prevent recursion - save a copy of m_RestoreEntity,
			// pretend that this player is off-limits

			// Temp turn this flag on
			pNPC->FlagForLagCompensation(true);

			BacktrackEntity( pHitEntity, flTargetTime );

			// Remove the temp flag
			pNPC->FlagForLagCompensation(false);
		}
	}
}

Two more big blocks to go. Firstly, you guessed it, we're gonna make an NPC version of BacktrackPlayer, BacktrackEntity. It's big!

void CLagCompensationManager::BacktrackEntity( CAI_BaseNPC *pEntity, float flTargetTime )
{
	Vector org, mins, maxs;
	QAngle ang;

	VPROF_BUDGET( "BacktrackEntity", "CLagCompensationManager" );

	// get track history of this entity
	CUtlFixedLinkedList< LagRecordNPC > *track = pEntity->GetLagTrack();

	// check if we have at leat one entry
	if ( track->Count() <= 0 )
		return;

	int curr = track->Head();

	LagRecordNPC *prevRecord = NULL;
	LagRecordNPC *record = NULL;

	Vector prevOrg = pEntity->GetLocalOrigin();
	
	// Walk context looking for any invalidating event
	while( track->IsValidIndex(curr) )
	{
		// remember last record
		prevRecord = record;

		// get next record
		record = &track->Element( curr );

		if ( !(record->m_fFlags & LC_ALIVE) )
		{
			// entity must be alive, lost track
			return;
		}

		Vector delta = record->m_vecOrigin - prevOrg;
		if ( delta.LengthSqr() > LAG_COMPENSATION_TELEPORTED_DISTANCE_SQR )
		{
			// lost track, moved too far (may have teleported)
			return; 
		}

		// did we find a context smaller than target time ?
		if ( record->m_flSimulationTime <= flTargetTime )
			break; // hurra, stop

		prevOrg = record->m_vecOrigin;

		// go one step back in time
		curr = track->Next( curr );
	}

	Assert( record );

	if ( !record )
	{
		if ( sv_unlag_debug.GetBool() )
		{
			DevMsg( "No valid positions in history for BacktrackEntity ( %s )\n", pEntity->GetClassname() );
		}

		return; // that should never happen
	}

	float frac = 0.0f;
 	if ( prevRecord && 
		 (record->m_flSimulationTime < flTargetTime) &&
		 (record->m_flSimulationTime < prevRecord->m_flSimulationTime) )
	{
		// we didn't find the exact time but have a valid previous record
		// so interpolate between these two records;

		Assert( prevRecord->m_flSimulationTime > record->m_flSimulationTime );
		Assert( flTargetTime < prevRecord->m_flSimulationTime );

		// calc fraction between both records
		frac = ( flTargetTime - record->m_flSimulationTime ) / 
			( prevRecord->m_flSimulationTime - record->m_flSimulationTime );

		Assert( frac > 0 && frac < 1 ); // should never extrapolate

		ang  = Lerp( frac, record->m_vecAngles, prevRecord->m_vecAngles );
		org  = Lerp( frac, record->m_vecOrigin, prevRecord->m_vecOrigin  );
		mins = Lerp( frac, record->m_vecMins, prevRecord->m_vecMins  );
		maxs = Lerp( frac, record->m_vecMaxs, prevRecord->m_vecMaxs );
	}
	else
 	{
		// we found the exact record or no other record to interpolate with
		// just copy these values since they are the best we have
		ang  = record->m_vecAngles;
		org  = record->m_vecOrigin;
		mins = record->m_vecMins;
		maxs = record->m_vecMaxs;
	}

	// See if this is still a valid position for us to teleport to
	if ( sv_unlag_fixstuck.GetBool() )
	{
		// Try to move to the wanted position from our current position.
 		trace_t tr;
		UTIL_TraceEntity( pEntity, org, org, MASK_NPCSOLID, &tr );
		if ( tr.startsolid || tr.allsolid )
		{
			if ( sv_unlag_debug.GetBool() )
				DevMsg( "WARNING: BackupEntity trying to back entity into a bad position - %s\n", pEntity->GetClassname() );

			CBasePlayer *pHitPlayer = dynamic_cast<CBasePlayer *>( tr.m_pEnt );

			// don't lag compensate the current player
			if ( pHitPlayer && ( pHitPlayer != m_pCurrentPlayer ) )	
			{
				// If we haven't backtracked this player, do it now
				// this deliberately ignores WantsLagCompensationOnEntity.
				if ( !m_RestorePlayer.Get( pHitPlayer->entindex() - 1 ) )
				{
					// prevent recursion - save a copy of m_RestorePlayer,
					// pretend that this player is off-limits
					int pl_index = pEntity->entindex() - 1;

					// Temp turn this flag on
					m_RestorePlayer.Set( pl_index );

					BacktrackPlayer( pHitPlayer, flTargetTime );

					// Remove the temp flag
					m_RestorePlayer.Clear( pl_index );
				}				
			}
			else
			{
				CAI_BaseNPC *pHitEntity = dynamic_cast<CAI_BaseNPC *>( tr.m_pEnt );
				if ( pHitEntity )
				{
					CAI_BaseNPC *pNPC = NULL;
					CAI_BaseNPC **ppAIs = g_AI_Manager.AccessAIs();
					int nAIs = g_AI_Manager.NumAIs();
					for ( int i = 0; i < nAIs; i++ ) // we'll have to find this entity's index though :(
					{
						pNPC = ppAIs[i];
						if ( pNPC == pHitEntity )
							break;
					}
					// If we haven't backtracked this player, do it now
					// this deliberately ignores WantsLagCompensationOnEntity.
					if ( pNPC && !pNPC->IsLagFlagged() )
					{
						// prevent recursion - save a copy of m_RestoreEntity,
						// pretend that this player is off-limits

						// Temp turn this flag on
						pNPC->FlagForLagCompensation(true);

						BacktrackEntity( pHitEntity, flTargetTime );

						// Remove the temp flag
						pNPC->FlagForLagCompensation(false);
					}
				}
			}

			// now trace us back as far as we can go
			UTIL_TraceEntity( pEntity, pEntity->GetLocalOrigin(), org, MASK_NPCSOLID, &tr );

			if ( tr.startsolid || tr.allsolid )
			{
				// Our starting position is bogus

				if ( sv_unlag_debug.GetBool() )
					DevMsg( "Backtrack failed completely, bad starting position\n" );
			}
			else
			{
				// We can get to a valid place, but not all the way to the target
				Vector vPos;
				VectorLerp( pEntity->GetLocalOrigin(), org, tr.fraction * g_flFractionScale, vPos );
				
				// This is as close as we're going to get
				org = vPos;

				if ( sv_unlag_debug.GetBool() )
					DevMsg( "Backtrack got most of the way\n" );
			}
		}
	}
	
	// See if this represents a change for the entity
	int flags = 0;
	LagRecordNPC *restore = new LagRecordNPC();//pEntity->GetLagRestoreData();
	LagRecordNPC *change  = new LagRecordNPC();//pEntity->GetLagChangeData();

	QAngle angdiff = pEntity->GetLocalAngles() - ang;
	Vector orgdiff = pEntity->GetLocalOrigin() - org;

	// Always remember the pristine simulation time in case we need to restore it.
	restore->m_flSimulationTime = pEntity->GetSimulationTime();

	if ( angdiff.LengthSqr() > LAG_COMPENSATION_EPS_SQR )
	{
		flags |= LC_ANGLES_CHANGED;
		restore->m_vecAngles = pEntity->GetLocalAngles();
		pEntity->SetLocalAngles( ang );
		change->m_vecAngles = ang;
	}

	// Use absolute equality here
	if ( ( mins != pEntity->WorldAlignMins() ) ||
		 ( maxs != pEntity->WorldAlignMaxs() ) )
	{
		flags |= LC_SIZE_CHANGED;
		restore->m_vecMins = pEntity->WorldAlignMins() ;
		restore->m_vecMaxs = pEntity->WorldAlignMaxs();
		pEntity->SetSize( mins, maxs );
		change->m_vecMins = mins;
		change->m_vecMaxs = maxs;
	}

	// Note, do origin at end since it causes a relink into the k/d tree
	if ( orgdiff.LengthSqr() > LAG_COMPENSATION_EPS_SQR )
	{
		flags |= LC_ORIGIN_CHANGED;
		restore->m_vecOrigin = pEntity->GetLocalOrigin();
		pEntity->SetLocalOrigin( org );
		change->m_vecOrigin = org;
	}

	// Sorry for the loss of the optimization for the case of people
	// standing still, but you breathe even on the server.
	// This is quicker than actually comparing all bazillion floats.
	flags |= LC_ANIMATION_CHANGED;
	restore->m_masterSequence = pEntity->GetSequence();
	restore->m_masterCycle = pEntity->GetCycle();

	bool interpolationAllowed = false;
	if( prevRecord && (record->m_masterSequence == prevRecord->m_masterSequence) )
	{
		// If the master state changes, all layers will be invalid too, so don't interp (ya know, interp barely ever happens anyway)
		interpolationAllowed = true;
	}
	
	////////////////////////
	// First do the master settings
 	bool interpolatedMasters = false;
	if( frac > 0.0f && interpolationAllowed )
 	{
  		interpolatedMasters = true;
		pEntity->SetSequence( Lerp( frac, record->m_masterSequence, prevRecord->m_masterSequence ) );
		pEntity->SetCycle( Lerp( frac, record->m_masterCycle, prevRecord->m_masterCycle ) );

		if( record->m_masterCycle > prevRecord->m_masterCycle )
		{
			// the older record is higher in frame than the newer, it must have wrapped around from 1 back to 0
			// add one to the newer so it is lerping from .9 to 1.1 instead of .9 to .1, for example.
			float newCycle = Lerp( frac, record->m_masterCycle, prevRecord->m_masterCycle + 1 );
			pEntity->SetCycle(newCycle < 1 ? newCycle : newCycle - 1 );// and make sure .9 to 1.2 does not end up 1.05
		}
		else
		{
			pEntity->SetCycle( Lerp( frac, record->m_masterCycle, prevRecord->m_masterCycle ) );
		}
	}
 	if( !interpolatedMasters )
	{
		pEntity->SetSequence(record->m_masterSequence);
		pEntity->SetCycle(record->m_masterCycle);
	}

	////////////////////////
	// Now do all the layers
	int layerCount = pEntity->GetNumAnimOverlays();
	for( int layerIndex = 0; layerIndex < layerCount; ++layerIndex )
	{
		CAnimationLayer *currentLayer = pEntity->GetAnimOverlay(layerIndex);
		if( currentLayer )
		{
			restore->m_layerRecords[layerIndex].m_cycle = currentLayer->m_flCycle;
			restore->m_layerRecords[layerIndex].m_order = currentLayer->m_nOrder;
			restore->m_layerRecords[layerIndex].m_sequence = currentLayer->m_nSequence;
			restore->m_layerRecords[layerIndex].m_weight = currentLayer->m_flWeight;

			bool interpolated = false;
			if( (frac > 0.0f)  &&  interpolationAllowed )
			{
				LayerRecordNPC &recordsLayerRecord = record->m_layerRecords[layerIndex];
				LayerRecordNPC &prevRecordsLayerRecord = prevRecord->m_layerRecords[layerIndex];
				if( (recordsLayerRecord.m_order == prevRecordsLayerRecord.m_order)
					&& (recordsLayerRecord.m_sequence == prevRecordsLayerRecord.m_sequence)
					)
				{
					// We can't interpolate across a sequence or order change
					interpolated = true;
					if( recordsLayerRecord.m_cycle > prevRecordsLayerRecord.m_cycle )
					{
						// the older record is higher in frame than the newer, it must have wrapped around from 1 back to 0
						// add one to the newer so it is lerping from .9 to 1.1 instead of .9 to .1, for example.
						float newCycle = Lerp( frac, recordsLayerRecord.m_cycle, prevRecordsLayerRecord.m_cycle + 1 );
						currentLayer->m_flCycle = newCycle < 1 ? newCycle : newCycle - 1;// and make sure .9 to 1.2 does not end up 1.05
					}
					else
					{
						currentLayer->m_flCycle = Lerp( frac, recordsLayerRecord.m_cycle, prevRecordsLayerRecord.m_cycle  );
					}
					currentLayer->m_nOrder = recordsLayerRecord.m_order;
					currentLayer->m_nSequence = recordsLayerRecord.m_sequence;
					currentLayer->m_flWeight = Lerp( frac, recordsLayerRecord.m_weight, prevRecordsLayerRecord.m_weight  );
				}
			}
			if( !interpolated )
			{
				//Either no interp, or interp failed.  Just use record.
				currentLayer->m_flCycle = record->m_layerRecords[layerIndex].m_cycle;
				currentLayer->m_nOrder = record->m_layerRecords[layerIndex].m_order;
				currentLayer->m_nSequence = record->m_layerRecords[layerIndex].m_sequence;
				currentLayer->m_flWeight = record->m_layerRecords[layerIndex].m_weight;
			}
		}
	}
	
	if ( !flags )
		return; // we didn't change anything

	if ( sv_lagflushbonecache.GetBool() )
		pEntity->InvalidateBoneCache();

	/*char text[256]; Q_snprintf( text, sizeof(text), "time %.2f", flTargetTime );
	pEntity->DrawServerHitboxes( 10 );
	NDebugOverlay::Text( org, text, false, 10 );
	NDebugOverlay::EntityBounds( pEntity, 255, 0, 0, 32, 10 ); */

	pEntity->FlagForLagCompensation(true); //remember that we changed this entity

	m_bNeedToRestore = true;  // we changed at least one player / entity
	restore->m_fFlags = flags; // we need to restore these flags
	change->m_fFlags = flags; // we have changed these flags

	pEntity->SetLagRestoreData(restore);
	pEntity->SetLagChangeData(change);

	if( sv_showlagcompensation.GetInt() == 1 )
	{
		pEntity->DrawServerHitboxes(4, true);
	}
}

Lastly, add this onto the end of FinishLagCompensation:

// also iterate all monsters
CAI_BaseNPC **ppAIs = g_AI_Manager.AccessAIs();
int nAIs = g_AI_Manager.NumAIs();

for ( int i = 0; i < nAIs; i++ )
{
	CAI_BaseNPC *pNPC = ppAIs[i];
	
	if ( !pNPC->IsLagFlagged() )
	{
		// entity wasn't changed by lag compensation
		continue;
	}

	LagRecordNPC *restore = pNPC->GetLagRestoreData();
	LagRecordNPC *change  = pNPC->GetLagChangeData();

	bool restoreSimulationTime = false;

	if ( restore->m_fFlags & LC_SIZE_CHANGED )
	{
		restoreSimulationTime = true;

		// see if simulation made any changes, if no, then do the restore, otherwise,
		//  leave new values in
		if ( pNPC->WorldAlignMins() == change->m_vecMins && 
			pNPC->WorldAlignMaxs() == change->m_vecMaxs )
		{
			// Restore it
			pNPC->SetSize( restore->m_vecMins, restore->m_vecMaxs );
		}
	}

	if ( restore->m_fFlags & LC_ANGLES_CHANGED )
	{ 		  
		restoreSimulationTime = true;

		if ( pNPC->GetLocalAngles() == change->m_vecAngles )
		{
			pNPC->SetLocalAngles( restore->m_vecAngles );
		}
	}

	if ( restore->m_fFlags & LC_ORIGIN_CHANGED )
	{
		restoreSimulationTime = true;

		// Okay, let's see if we can do something reasonable with the change
		Vector delta = pNPC->GetLocalOrigin() - change->m_vecOrigin;
		
		// If it moved really far, just leave the player in the new spot!!!
		if ( delta.LengthSqr() < LAG_COMPENSATION_TELEPORTED_DISTANCE_SQR )
		{
			RestoreEntityTo( pNPC, restore->m_vecOrigin + delta );
		}
	}

	if( restore->m_fFlags & LC_ANIMATION_CHANGED )
	{
		restoreSimulationTime = true;

		pNPC->SetSequence(restore->m_masterSequence);
		pNPC->SetCycle(restore->m_masterCycle);

		int layerCount = pNPC->GetNumAnimOverlays();
		for( int layerIndex = 0; layerIndex < layerCount; ++layerIndex )
		{
			CAnimationLayer *currentLayer = pNPC->GetAnimOverlay(layerIndex);
			if( currentLayer )
			{
				currentLayer->m_flCycle = restore->m_layerRecords[layerIndex].m_cycle;
				currentLayer->m_nOrder = restore->m_layerRecords[layerIndex].m_order;
				currentLayer->m_nSequence = restore->m_layerRecords[layerIndex].m_sequence;
				currentLayer->m_flWeight = restore->m_layerRecords[layerIndex].m_weight;
			}
		}
	}

	if ( restoreSimulationTime )
	{
		pNPC->SetSimulationTime( restore->m_flSimulationTime );
	}
}

Congratulations! Assuming this compiles, your NPCs should all be lag-compensated. To verify that it's working, run a map. In the console, first type sv_cheats 1, then sv_showlagcompensation 1. When you shoot at an NPC, blue rectangles representing each bone should be drawn around it.