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, and so HL2DM incorporates lag compensation, which when calculating whether a bullet hits or not, 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

Most of the coding will be done in player_lagcompensation.cpp, but first we will tackle a few little changes needed elsewhere. Open ai_basenpc.h, and at about line 450 you'll find the CAI_Manager class definition. In it, you'll see

	enum
	{
		MAX_AIS = 256
	};

This defines the length of the array used to represent "all AIs" - unfortunately it's private, so can't be accessed from outside the class. Remove this snippet, and just before the class declaration add instead

#define MAX_AIS	256

Now we can access this value from anywhere, and will do so later on. Also in this class, notice

void AddAI( CAI_BaseNPC *pAI );

which should be at line 459. We're going NPCs to be able to track where in the AI manager's list they reside, so this function will be changed to return the index it adds them to. For now, just change the type to int

int AddAI( CAI_BaseNPC *pAI );

Now scroll down to line 2124, just before the closing bracer (};), and add

	// used by lag compensation to be able to refer to & track specific NPCs, and detect changes in the AI list
	void				SetAIIndex(int i) { m_iAIIndex = i; }
	int					GetAIIndex() { return m_iAIIndex; }
private:
	int					m_iAIIndex;

This "AI Index" is what will track an NPC's position in the list.

ai_basenpc.cpp

Onto the includes at the top of ai_basenpc.cpp, add

#include "ilagcompensationmanager.cpp

Find void CAI_Manager::AddAI at line 252, this is the function who's declaration we changed from void to int - change it to read as follows:

int CAI_Manager::AddAI( CAI_BaseNPC *pAI )
{
	m_AIs.AddToTail( pAI );
	return NumAIs()-1; // return the index it was added to
}

At line 11352, in the CAI_BaseNPC constructor, find the line

g_AI_Manager.AddAI( this );

and replace it with this

SetAIIndex( g_AI_Manager.AddAI( this ) );
lagcompensation->RemoveNpcData( GetAIIndex() ); // make sure we're not inheriting anyone else's data

This ensures that all NPCs are added to the lag compensation manager as soon as they're created.

Now in the destructor, at line 11378, we'll remove it from the NPC lag compensation, otherwise a crash occured when an NPC was killed and another created in the same game frame (eg headcrab coming off a zombie).

lagcompensation->RemoveNpcData( GetAIIndex() );

ilagcompensationmanager.h

This RemoveNpcData will be defined shortly, but first the interface CAI_BaseNPC uses to access it must be created - open ilagcompensationmanager.h, and add this at line 26

virtual void	RemoveNpcData(int index) = 0;

player.cpp / player.h

To decide what should be lag compensated, the player class has a function, WantsLagCompensationOnEntity - which returns true or false. Unfortunately, its designed to only accept a player as its "entity" parameter - but we want it to lag compensate NPCs too, so 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 thats what you renamed the parameter), and 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, thats 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 );
	}
}

Now comes the CLagCompensationManager class definition. To the constructor, add

m_bNeedsAIUpdate = true;

Under the declarations of StartLagCompensation and FinishLagCompensation, add

	void RemoveNpcData(int index) // clear specific NPC's history
	{
		CUtlFixedLinkedList< LagRecord > *track = &m_EntityTrack[index];
		track->Purge();
	}

The private: section should immediately follow this, starting with the function

void BacktrackPlayer( CBasePlayer *player, float flTargetTime );

Just under this, add

void BacktrackEntity( CAI_BaseNPC *entity, float flTargetTime );

Next is the ClearHistory function, which loops through all players and purges their records. Have it do the same for NPCs:

	void ClearHistory()
	{
		for ( int i=0; i<MAX_PLAYERS; i++ ) // all players
			m_PlayerTrack[i].Purge();
		for ( int j=0; j<MAX_AIS; j++ ) // and all npcs
			m_EntityTrack[j].Purge();
	}

Now declare a function, UpdateAIIndexes();, and create Entity versions of all the Player variables except for m_pCurrentPlayer. Also add a bool, m_bNeedsAIUpdate:

	void UpdateAIIndexes();

	// keep a list of lag records for each player
	CUtlFixedLinkedList< LagRecord >	m_PlayerTrack[ MAX_PLAYERS ];
	CUtlFixedLinkedList< LagRecord >	m_EntityTrack[ MAX_AIS ];

	// Scratchpad for determining what needs to be restored
	CBitVec<MAX_PLAYERS>	m_RestorePlayer;
	CBitVec<MAX_AIS>	m_RestoreEntity;
	bool			m_bNeedToRestore;
	
	LagRecord		m_RestoreData[ MAX_PLAYERS ];	// player data before we moved him back
	LagRecord		m_ChangeData[ MAX_PLAYERS ];	// player data where we moved him back

	LagRecord		m_EntityRestoreData[ MAX_AIS ];
	LagRecord		m_EntityChangeData[ MAX_AIS ];

	CBasePlayer		*m_pCurrentPlayer;	// The player we are doing lag compensation for

	bool			m_bNeedsAIUpdate;
};

Next up is FrameUpdatePostEntityThink. Onto the very start, add

	if ( m_bNeedsAIUpdate )
		UpdateAIIndexes(); // only bother if we haven't had one yet
	else // setting this true here ensures that the update happens at the start of the next frame
		m_bNeedsAIUpdate = true;

Basically we want UpdateAIIndexes to be called every frame, but it has to be called before any lag compensation occurs. If no lag compensation occurs, it will be called here instead. 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];
		CUtlFixedLinkedList< LagRecord > *track = &m_EntityTrack[i];

		if ( !pNPC )
		{
			track->RemoveAll();
			continue;
		}

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

		// remove tail records that are too old
		int tailIndex = track->Tail();
		while ( track->IsValidIndex( tailIndex ) )
		{
			LagRecord &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 )
		{
			LagRecord &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
		LagRecord &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();
	}

The next function is a new one, created because of a problem with NPCs. Positions in the Player List are fixed: if a player is in Position 5, they will always be in Position 5. With the AI index, its different. When the AI in position 4 dies, the one from the end of the list is moved into position 4 to replace it. This function is designed to account for that, and swap the movement records when an NPC's index changes.

void CLagCompensationManager::UpdateAIIndexes()
{
	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 && pNPC->GetAIIndex() != i ) // index of NPC has changed
		{// move their data to their new index, probably wanting to delete the old track record
			int oldIndex = pNPC->GetAIIndex();
			int newIndex = i;

			//Msg("Lag compensation record adjusting, moving from index %i to %i\n",oldIndex,newIndex);

			CUtlFixedLinkedList< LagRecord > *track = &m_EntityTrack[ oldIndex ];
			CUtlFixedLinkedList< LagRecord > *oldTrack = &m_EntityTrack[ newIndex ];

			m_EntityTrack[oldIndex] = *oldTrack;
			m_EntityTrack[newIndex] = *track;
			if ( oldTrack->Count() > 0 ) // there's data in the auld yin, probably from someone newly dead,
			{// but if not we'll swap them round so that the old one can then fix their AI index
				//Msg("Index %i already contains data!\n",newIndex);
				for ( int j=0; j<nAIs; j++ )
				{
					CAI_BaseNPC *pConflictingNPC = ppAIs[j];
					if ( pConflictingNPC && pConflictingNPC->GetAIIndex() == newIndex )
					{// found the conflicting NPC, swap them into the old index
						pConflictingNPC->SetAIIndex(oldIndex); // presumably they'll fix themselves further down the loop
						Warning("Lag compensation adjusting entity index, swapping with an existing entity! (%i & %i)\n",oldIndex,newIndex);
						break;
					}
				}
			}

			pNPC->SetAIIndex(newIndex);
		}
	}
}

Onto the start of StartLagCompensation, add

	// sort out any changes to the AI indexing
	if ( m_bNeedsAIUpdate ) // to be called once per frame... must happen BEFORE lag compensation -
	{// if that happens, that is. if not its called at the end of the frame
		m_bNeedsAIUpdate = false;
		UpdateAIIndexes();
	}

	m_RestoreEntity.ClearAll();

Under the two Q_memsets in this function, add two more

	Q_memset( m_EntityRestoreData, 0, sizeof( m_EntityRestoreData ) );
	Q_memset( m_EntityChangeData, 0, sizeof( m_EntityChangeData ) );

This function ends with a for loop, commented with

	// Iterate all active players

Remove it, and replace it with two:

	// 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
	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];
		// 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 && !m_RestoreEntity.Get( pNPC->GetAIIndex() ) )
					{
						// prevent recursion - save a copy of m_RestoreEntity,
						// pretend that this player is off-limits

						// Temp turn this flag on
						m_RestoreEntity.Set( pNPC->GetAIIndex() );

						BacktrackEntity( pHitEntity, flTargetTime );

						// Remove the temp flag
						m_RestoreEntity.Clear( pNPC->GetAIIndex() );
					}
				}
			}

Two more big blocks to go. Firstly, you guessed it, we're gonna make an NPC version of BacktrackPlayer, BacktrackEntity. Its 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
	int index = pEntity->GetAIIndex();
	CUtlFixedLinkedList< LagRecord > *track = &m_EntityTrack[ index ];

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

	int curr = track->Head();

	LagRecord *prevRecord = NULL;
	LagRecord *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 && !m_RestoreEntity.Get( pNPC->GetAIIndex() ) )
					{
						// prevent recursion - save a copy of m_RestoreEntity,
						// pretend that this player is off-limits

						// Temp turn this flag on
						m_RestoreEntity.Set( pNPC->GetAIIndex() );

						BacktrackEntity( pHitEntity, flTargetTime );

						// Remove the temp flag
						m_RestoreEntity.Clear( pNPC->GetAIIndex() );
					}
				}
			}

			// 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;
	LagRecord *restore = &m_EntityRestoreData[ index ];
	LagRecord *change  = &m_EntityChangeData[ index ];

	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 )
			{
				LayerRecord &recordsLayerRecord = record->m_layerRecords[layerIndex];
				LayerRecord &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 ); */

	m_RestoreEntity.Set( index ); //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

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

And 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 ( !m_RestoreEntity.Get( i ) )
		{
			// entity wasn't changed by lag compensation
			continue;
		}

		LagRecord *restore = &m_EntityRestoreData[ i ];
		LagRecord *change  = &m_EntityChangeData[ i ];

		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 its working, run a map and 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.