NPC Lag Compensation: Difference between revisions

From Valve Developer Community
Jump to navigation Jump to search
(noted mem leak)
(changed code to remove memory leak)
Line 4: Line 4:


This tutorial details all the changes required - while a lot of code is involved, 95% of it is duplicated from player lag compensation code.
This tutorial details all the changes required - while a lot of code is involved, 95% of it is duplicated from player lag compensation code.
{{bug|This code [[Talk:NPC Lag Compensation|has a memory leak]] somewhere.}}


== ai_basenpc.h ==
== ai_basenpc.h ==
Line 20: Line 18:
<source lang=cpp>#define MAX_AIS 256</source>
<source lang=cpp>#define MAX_AIS 256</source>


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


<source lang=cpp>void AddAI( CAI_BaseNPC *pAI );</source>
Now open up player_lagcompensation.cpp, and cut this define (the first line of code):
<source lang=cpp>#define MAX_LAYER_RECORDS (CBaseAnimatingOverlay::MAX_OVERLAYS)</source>
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
as well as the entire LayerRecord and LagRecord structs just after it, and paste them into the top of ai_basenpc.h, just before this line:
<source lang=cpp>typedef CBitVec<MAX_CONDITIONS> CAI_ScheduleBits;</source>


<source lang=cpp>int AddAI( CAI_BaseNPC *pAI );</source>
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 scroll down to line 2124, just before the closing bracer (<code>};</code>), and add
Now again in ai_basenpc.h, add the following two sections lines to the CAI_BaseNPC class definition - the first somewhere in a private section, and the second in a public section:
<source lang=cpp>CUtlFixedLinkedList< LagRecord > *m_LagTrack;
LagRecord *m_RestoreData;
LagRecord *m_ChangeData;</source>


<source lang=cpp>
<source lang=cpp>CUtlFixedLinkedList< LagRecord > *GetLagTrack() { return m_LagTrack; }
// used by lag compensation to be able to refer to & track specific NPCs, and detect changes in the AI list
LagRecord* GetLagRestoreData() {  if ( m_RestoreData != NULL ) return m_RestoreData; else return new LagRecord();}
void SetAIIndex(int i) { m_iAIIndex = i; }
LagRecord* GetLagChangeData() { if ( m_ChangeData != NULL ) return m_ChangeData; else return new LagRecord();}
int GetAIIndex() { return m_iAIIndex; }
void SetLagRestoreData(LagRecord *l) { if ( m_RestoreData != NULL ) delete m_RestoreData; m_RestoreData = l; }
private:
void SetLagChangeData(LagRecord *l) { if ( m_ChangeData != NULL ) delete m_ChangeData; m_ChangeData = l; }</source>
int m_iAIIndex;
</source>


This "AI Index" is what will track an NPC's position in the list.
This "lag record" is what stores an NPC's historical position and animation information.


== ai_basenpc.cpp ==
== ai_basenpc.cpp ==


Onto the includes at the top of ai_basenpc.cpp, add
In the <code>CAI_BaseNPC</code> destructor, add this line just under <source lang=cpp>delete m_pTacticalServices;</source>
 
<source lang=cpp>m_LagTrack->Purge();</source>
<source lang=cpp>#include "ilagcompensationmanager.h"</source>
 
Find <code>void CAI_Manager::AddAI</code> at line 252, this is the function who's declaration we changed from void to int - change it to read as follows:
 
<source lang=cpp>
int CAI_Manager::AddAI( CAI_BaseNPC *pAI )
{
m_AIs.AddToTail( pAI );
return NumAIs()-1; // return the index it was added to
}
</source>
 
At line 11352, in the <code>CAI_BaseNPC</code> constructor, find the line
 
<source lang=cpp>g_AI_Manager.AddAI( this );</source>
 
and replace it with this
 
<source lang=cpp>
SetAIIndex( g_AI_Manager.AddAI( this ) );
lagcompensation->RemoveNpcData( GetAIIndex() ); // make sure we're not inheriting anyone else's data
</source>
 
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).
 
<source lang=cpp>lagcompensation->RemoveNpcData( GetAIIndex() );</source>
 
== ilagcompensationmanager.h ==
 
This <code>RemoveNpcData</code> will be defined shortly, but first the interface <code>CAI_BaseNPC</code> uses to access it must be created - open ilagcompensationmanager.h, and add this at line 26
 
<source lang=cpp>virtual void RemoveNpcData(int index) = 0;</source>


== player.cpp / player.h ==
== player.cpp / player.h ==
Line 173: Line 139:
</source>
</source>


Now comes the CLagCompensationManager class definition.
The <code>private:</code> section of the CLagCompensationManager class definition should start with the function
To the constructor, add
 
<source lang=cpp>m_bNeedsAIUpdate = true;</source>
 
Under the declarations of StartLagCompensation and FinishLagCompensation, add
 
<source lang=cpp>
void RemoveNpcData(int index) // clear specific NPC's history
{
CUtlFixedLinkedList< LagRecord > *track = &m_EntityTrack[index];
track->Purge();
}
</source>
 
The <code>private:</code> section should immediately follow this, starting with the function


<source lang=cpp>void BacktrackPlayer( CBasePlayer *player, float flTargetTime );</source>
<source lang=cpp>void BacktrackPlayer( CBasePlayer *player, float flTargetTime );</source>
Line 196: Line 147:
<source lang=cpp>void BacktrackEntity( CAI_BaseNPC *entity, float flTargetTime );</source>
<source lang=cpp>void BacktrackEntity( CAI_BaseNPC *entity, float flTargetTime );</source>


Next is the ClearHistory function, which loops through all players and purges their records. Have it do the same for NPCs:
<source lang=cpp>
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();
}
</source>
Now declare a function, <code>UpdateAIIndexes();</code>, and create <code>Entity</code> versions of all the <code>Player</code> variables except for m_pCurrentPlayer. Also add a bool, <code>m_bNeedsAIUpdate</code>:
<source lang=cpp>
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;
};
</source>
Next up is <code>FrameUpdatePostEntityThink</code>.
Onto the very start, add
<source lang=cpp>
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;
</source>
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:


Next up is <code>FrameUpdatePostEntityThink</code>. 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:
<source lang=cpp>
<source lang=cpp>
// Iterate all active NPCs
// Iterate all active NPCs
Line 324: Line 227:
</source>
</source>


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.
At the top of StartLagCompensation, just under <source lang=cpp>m_RestorePlayer.ClearAll();</source>, add
 
<source lang=cpp>int nAIs = g_AI_Manager.NumAIs();
<source lang=cpp>
CAI_BaseNPC **ppAIs = g_AI_Manager.AccessAIs();
void CLagCompensationManager::UpdateAIIndexes()
for (int i=0; i<nAIs; i++)
{
ppAIs[ i ]->FlagForLagCompensation(false);</source>
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);
}
}
}
</source>
Onto the start of StartLagCompensation, add
<source lang=cpp>
// 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();
</source>
Under the two Q_memsets in this function, add two more
<source lang=cpp>
Q_memset( m_EntityRestoreData, 0, sizeof( m_EntityRestoreData ) );
Q_memset( m_EntityChangeData, 0, sizeof( m_EntityChangeData ) );
</source>


This function ends with a for loop, commented with
This function ends with a for loop, commented with
Line 454: Line 300:
// If we haven't backtracked this player, do it now
// If we haven't backtracked this player, do it now
// this deliberately ignores WantsLagCompensationOnEntity.
// this deliberately ignores WantsLagCompensationOnEntity.
if ( pNPC && !m_RestoreEntity.Get( pNPC->GetAIIndex() ) )
if ( pNPC && !pNPC->IsLagFlagged() )
{
{
// prevent recursion - save a copy of m_RestoreEntity,
// prevent recursion - save a copy of m_RestoreEntity,
Line 460: Line 306:


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


BacktrackEntity( pHitEntity, flTargetTime );
BacktrackEntity( pHitEntity, flTargetTime );


// Remove the temp flag
// Remove the temp flag
m_RestoreEntity.Clear( pNPC->GetAIIndex() );
pNPC->FlagForLagCompensation(false);
}
}
}
}
Line 482: Line 328:


// get track history of this entity
// get track history of this entity
int index = pEntity->GetAIIndex();
CUtlFixedLinkedList< LagRecord > *track = pEntity->GetLagTrack();
CUtlFixedLinkedList< LagRecord > *track = &m_EntityTrack[ index ];


// check if we have at leat one entry
// check if we have at leat one entry
Line 621: Line 466:
// If we haven't backtracked this player, do it now
// If we haven't backtracked this player, do it now
// this deliberately ignores WantsLagCompensationOnEntity.
// this deliberately ignores WantsLagCompensationOnEntity.
if ( pNPC && !m_RestoreEntity.Get( pNPC->GetAIIndex() ) )
if ( pNPC && !pNPC->IsLagFlagged() )
{
{
// prevent recursion - save a copy of m_RestoreEntity,
// prevent recursion - save a copy of m_RestoreEntity,
Line 627: Line 472:


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


BacktrackEntity( pHitEntity, flTargetTime );
BacktrackEntity( pHitEntity, flTargetTime );


// Remove the temp flag
// Remove the temp flag
m_RestoreEntity.Clear( pNPC->GetAIIndex() );
pNPC->FlagForLagCompensation(false);
}
}
}
}
Line 664: Line 509:
// See if this represents a change for the entity
// See if this represents a change for the entity
int flags = 0;
int flags = 0;
LagRecord *restore = &m_EntityRestoreData[ index ];
LagRecord *restore = new LagRecord();//pEntity->GetLagRestoreData();
LagRecord *change  = &m_EntityChangeData[ index ];
LagRecord *change  = new LagRecord();//pEntity->GetLagChangeData();


QAngle angdiff = pEntity->GetLocalAngles() - ang;
QAngle angdiff = pEntity->GetLocalAngles() - ang;
Line 805: Line 650:
NDebugOverlay::EntityBounds( pEntity, 255, 0, 0, 32, 10 ); */
NDebugOverlay::EntityBounds( pEntity, 255, 0, 0, 32, 10 ); */


m_RestoreEntity.Set( index ); //remember that we changed this entity
pEntity->FlagForLagCompensation(true); //remember that we changed this entity
 
m_bNeedToRestore = true;  // we changed at least one player / entity
m_bNeedToRestore = true;  // we changed at least one player / entity
restore->m_fFlags = flags; // we need to restore these flags
restore->m_fFlags = flags; // we need to restore these flags
change->m_fFlags = flags; // we have changed these flags
change->m_fFlags = flags; // we have changed these flags
pEntity->SetLagRestoreData(restore);
pEntity->SetLagChangeData(change);


if( sv_showlagcompensation.GetInt() == 1 )
if( sv_showlagcompensation.GetInt() == 1 )
Line 830: Line 679:
CAI_BaseNPC *pNPC = ppAIs[i];
CAI_BaseNPC *pNPC = ppAIs[i];
if ( !m_RestoreEntity.Get( i ) )
if ( !pNPC->IsLagFlagged() )
{
{
// entity wasn't changed by lag compensation
// entity wasn't changed by lag compensation
Line 836: Line 685:
}
}


LagRecord *restore = &m_EntityRestoreData[ i ];
LagRecord *restore = pNPC->GetLagRestoreData();
LagRecord *change  = &m_EntityChangeData[ i ];
LagRecord *change  = pNPC->GetLagChangeData();


bool restoreSimulationTime = false;
bool restoreSimulationTime = false;

Revision as of 15:30, 14 November 2009

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 multiplayer Source games implement 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.

Now open up player_lagcompensation.cpp, and cut this define (the first line of code): 

#define MAX_LAYER_RECORDS (CBaseAnimatingOverlay::MAX_OVERLAYS)

as well as the entire LayerRecord and LagRecord structs just after it, and paste them into the top of ai_basenpc.h, just before this line: 

typedef CBitVec<MAX_CONDITIONS> CAI_ScheduleBits;

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 two sections lines to the CAI_BaseNPC class definition - the first somewhere in a private section, and the second in a public section: 

CUtlFixedLinkedList< LagRecord > *m_LagTrack;
LagRecord			*m_RestoreData;
LagRecord			*m_ChangeData;

CUtlFixedLinkedList< LagRecord > *GetLagTrack() { return m_LagTrack; }
LagRecord*			GetLagRestoreData() {  if ( m_RestoreData != NULL ) return m_RestoreData; else return new LagRecord();}
LagRecord*			GetLagChangeData() { if ( m_ChangeData != NULL ) return m_ChangeData; else return new LagRecord();}
void				SetLagRestoreData(LagRecord *l) { if ( m_RestoreData != NULL ) delete m_RestoreData; m_RestoreData = l; }
void				SetLagChangeData(LagRecord *l) { if ( m_ChangeData != NULL ) delete m_ChangeData; m_ChangeData = l; }

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

ai_basenpc.cpp

In the CAI_BaseNPC destructor, add this line just under 

delete m_pTacticalServices;

m_LagTrack->Purge();

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 );
	}
}

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];
	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();
}

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: 

// 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 && !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< LagRecord > *track = pEntity->GetLagTrack();

	// 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 && !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;
	LagRecord *restore = new LagRecord();//pEntity->GetLagRestoreData();
	LagRecord *change  = new LagRecord();//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 )
			{
				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 ); */

	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);
	}
}

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 ( !pNPC->IsLagFlagged() )
	{
		// entity wasn't changed by lag compensation
		continue;
	}

	LagRecord *restore = pNPC->GetLagRestoreData();
	LagRecord *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 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.

Retrieved from "https://developer.valvesoftware.com/w/index.php?title=NPC_Lag_Compensation&oldid=127029"