LOS Cache Prototype Idea

[lerxst2112]

LOSEntry ent = (LOSEntry)iter->second;

You shouldn't need to cast iter->second to LOSEntry, types are not lost when objects are stored in a map.

You should also use a reference here as it avoids a copy, and then use the reference to update the values stored in the object rather than creating a new one and copying it over the existing one.

[image]

I'll take those under consideration thanks. I typecast just to make it look cleaner frankly, but I agree with the update.

[image]

This is a bit cleaner.. The performance seems about the same, it may matter if the zones have 1000+ npc's.

Index: common/ruletypes.h
===================================================================
--- common/ruletypes.h	(revision 2231)
+++ common/ruletypes.h	(working copy)
@@ -480,6 +480,14 @@
 RULE_REAL ( EQStream, RetransmitTimeoutMult, 3.0 ) // multiplier applied to rtt stats to generate a retransmit timeout value
 RULE_BOOL ( EQStream, RetransmitAckedPackets, true ) // should we restransmit packets that were already acked?
 RULE_CATEGORY_END()
+
+// Image: Features that are not required but may help improve performance
+RULE_CATEGORY ( Performance )
+RULE_BOOL ( Performance, LOSCacheEnabled, false )
+// The millisecond value is important to be above the time it would take for AI process or something else to trigger CheckLOS.
+// If you have too low of value, say 250ms, the cached entry will most likely be expired before it can be re-used.
+RULE_INT ( Performance, LOSCacheEntryMS, 3000 )
+RULE_CATEGORY_END()
 
 #undef RULE_CATEGORY
 #undef RULE_INT
Index: zone/aggro.cpp
===================================================================
--- zone/aggro.cpp	(revision 2231)
+++ zone/aggro.cpp	(working copy)
@@ -1002,12 +1002,71 @@
 }
 
 
+// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+bool Mob::FindLosCacheEntry(Mob* other, bool& inLOS, int32& hits)
+{
+	if ( other == NULL || !RuleB(Performance,LOSCacheEnabled) )
+		return false;
+
+	std::map<int16, LOSEntry>::iterator iter = m_LOSCache.find(other->GetID());
+	if ( iter != m_LOSCache.end() )
+	{
+		if ( iter->second.entry == other ) // this means the entry is valid and we have the right mob
+		{
+			if ( Timer::GetCurrentTime() < iter->second.lastChecked )
+			{
+				// Update the entry with the new hits, here we could essentially 'increase' the cache too
+				iter->second.hits += 1;
+				// if this is true then we already have an entry that is at the same location, save it for another period of time
+				if ( iter->second.lastX == other->GetX() &&
+					iter->second.lastY == other->GetY() &&
+					iter->second.ourLastX == GetX() &&
+					iter->second.ourLastY == GetY() )
+					iter->second.lastChecked = Timer::GetCurrentTime() + RuleI(Performance, LOSCacheEntryMS);
+
+				inLOS = iter->second.isLOS;
+				hits = iter->second.hits;
+				return true;
+			}
+		}
+	}
+
+	return false;
+}
+
 //Father Nitwit's LOS code
 bool Mob::CheckLosFN(Mob* other) {
 	bool Result = false;
 
+	if ( other == this )
+		return true;
+	
+	int32 hits = 0;
+
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	if ( FindLosCacheEntry( other, Result, hits) )
+		return Result;
+
 	if(other)
+	{
 		Result = CheckLosFN(other->GetX(), other->GetY(), other->GetZ(), other->GetSize());
+		
+		if ( RuleB(Performance,LOSCacheEnabled) )
+		{
+			LOSEntry newEnt;
+			newEnt.entry = other;
+			newEnt.isLOS = Result;
+			newEnt.lastChecked = Timer::GetCurrentTime() + RuleI(Performance, LOSCacheEntryMS);
+			newEnt.hits = 1;
+			newEnt.lastX = other->GetX();
+			newEnt.lastY = other->GetY();
+			newEnt.lastZ = other->GetZ();
+			newEnt.ourLastX = GetX();
+			newEnt.ourLastY = GetY();
+			newEnt.ourLastZ = GetZ();
+			m_LOSCache[other->GetID()] = newEnt;
+		}
+	}
 
 	return Result;
 }
Index: zone/command.cpp
===================================================================
--- zone/command.cpp	(revision 2231)
+++ zone/command.cpp	(working copy)
@@ -6723,7 +6723,13 @@
 {
 	if(c->GetTarget())
 	{
-//		if(c->CheckLos(c->GetTarget()))
+		bool los = false;
+		int32 hits = 0;
+		if ( c->FindLosCacheEntry(c->GetTarget(), los, hits) )
+			c->Message(12,"(Client->Mob) Cached entry exists with mob. LOSVisibleStatus: %i.  CacheEntryHits: %i.", los, hits);
+		if ( c->GetTarget()->FindLosCacheEntry(c, los, hits) )
+			c->Message(12,"(Mob->Client) Cached entry exists ON mob. LOSVisibleStatus: %i.  CacheEntryHits: %i.", los, hits);
+
 		if(c->CheckLosFN(c->GetTarget()))
 			c->Message(0, "You have LOS to %s", c->GetTarget()->GetName());
 		else
Index: zone/mob.h
===================================================================
--- zone/mob.h	(revision 2231)
+++ zone/mob.h	(working copy)
@@ -466,6 +466,23 @@
 class EGNode;
 class MobFearState;
 
+// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+struct LOSEntry {
+	Mob* entry;
+	bool isLOS;
+	int32 lastChecked; // Timer::GetCurrentTime entry to compare
+	int32 hits; // times the entry was hit in the timeframe of the cache
+	// target last location
+	float lastX;
+	float lastY;
+	float lastZ;
+
+	// our last location when we got this entry
+	float ourLastX;
+	float ourLastY;
+	float ourLastZ;
+};
+
 class Mob : public Entity {
 public:
 bool logpos;
@@ -646,6 +663,9 @@
 	inline bool SeeInvisibleUndead() const { return see_invis_undead; } 
 	inline bool SeeHide() const { return see_hide; }
 	inline bool SeeImprovedHide() const { return see_improved_hide; }
+	
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	bool FindLosCacheEntry(Mob* other, bool& inLOS, int32& hits);
 
 	bool CheckLos(Mob* other);
 	bool CheckLosFN(Mob* other);
@@ -1256,6 +1276,9 @@
 
 	std::vector<std::string> RampageArray;
 	std::map<std::string, std::string> m_EntityVariables;
+	
+	// Image (10/14/2012): Added LOSEntry as a cache to slow down the attempts against los on the same mob in a short time frame
+	std::map<int16, LOSEntry> m_LOSCache;
 
 	sint16 SkillDmgTaken_Mod[HIGHEST_SKILL+2];
 	sint16 Vulnerability_Mod[HIGHEST_RESIST+2];

[lerxst2112]

I think the cache is a good idea, especially if there are many los checks being performed without the mobs moving, and as you've seen in your tests it does seem to be a performance win.

The only concern I have is that I don't see anything ever being removed from the cache. It'll get cleaned up in the destructor when a mob dies, but any other mob with entries pointing to the now destroyed mob won't go away.

Do mobs regularly perform los checks on each other? I suppose the worry is that in a zone where many mobs are killed over and over but there are some that are never killed, then those caches would continue to grow over time as the entries that point to the dead mobs accumulate.

The only way I can see to keep that from happening would be to tell every other mob to remove any entries pointing to a mob that is being destroyed from their cache. That would mean a potentially costly operation whenever a mob dies. An alternative could be to have a scheduled task on each that dumped entries that were very old, but then that will cause a periodic cpu spike if they all do it at the same time.

Have you seen memory usage creeping up over time if you kill some mobs but not all of them? It might be worth logging out the size of each cache periodically for debugging purposes and see if they just grow forever on any mobs with long lifetimes.

[image]

this CheckLosFN is called for quite a few things including aggro, friendly faction (mobs), spell casting, auto attack, etc. It would be possible to build it over time but difficult to consume large amounts of memory.

As you mentioned it would seem costly for a cleanup and I don't think that you would see the accumulation (we try to start re-using id's once we get up to 1500 in the Entity class).

If anything -- it becoming a problem id say just every 5 minutes or something clear the map (dont bother checking the cache entries just flush it).