here is a piece of code that might help.
Basically, pre-computes neighborhood for all mobs in zone every x seconds. This is quite fast, and --linear--
in Entity::AggroCheckClose, instead of parsing all mob_list and checking for neighbors, use that cache
Below are two snippets
i used DoorProcess to update neighborhood, as this is called in most zones (if not all) whatever the players in it. Thus, every 5 secs, an update of the terrain (a static singleton of Terrain class) if performed. After this has been called, terrain hopefully has a list (hastable) of all mobs within a given range, for each mob. i know this is not the right place to do it, but for the moment i didn't want to get too intrusive and add pieces of code in net.cpp or wherever.
Code:
--- ../../cvs/eqemu/eqemu/Source/zone/entity.cpp 2004-02-02 13:55:07.000000000 +0000
+++ entity.cpp 2004-02-05 11:18:55.000000000 +0000
@@ -52,6 +52,10 @@
#define strcasecmp _stricmp
#endif
+#ifdef KD
+#include "../extra/Vector.h"
+#include "../extra/Terrain.h"
+#endif
extern Zone* zone;
extern volatile bool ZoneLoaded;
extern WorldServer worldserver;
@@ -216,6 +220,24 @@
else
iterator.Advance();
}
+#ifdef KD
+ printf("in EntityList::DoorProcess, time is %4.1f: \n",Timer::GetCurrentTime()*0.001f);
+ LinkedListIterator<Mob*> miter(mob_list);
+ Vector *vmob=new Vector();
+ miter.Reset();
+ while(miter.MoreElements()) {
+ //printf("Yet another mob in the list...\n");
+ vmob->add(miter.GetData());
+ miter.Advance();
+ }
+ printf("got %d entities from mob_list\n",vmob->size());
+ Mob* mobs[vmob->size()];
+ vmob->copyInto(mobs);
+ // aggregate on a max 200.0 distance
+ // this should be dynamically set to the max aggro range of all mobs
+ terrain.update(vmob->size(),mobs,200.0f);
+ delete vmob;
+#endif
if(count==0)
in MobAI
when checking for a AgrroRadius match, get the vector of mobs that were matched as neighbors. Use this list insted if the full mob_list to check for aggro.
Code:
--- ../../cvs/eqemu/eqemu/Source/zone/MobAI.cpp 2004-02-02 13:54:59.000000000 +0000
+++ MobAI.cpp 2004-02-05 10:41:31.000000000 +0000
@@ -20,6 +20,11 @@
extern SPDat_Spell_Struct spells[SPDAT_RECORDS];
#endif
+#ifdef KD
+#include "../extra/LL.h"
+#include "../extra/Terrain.h"
+#endif
+
extern EntityList entity_list;
extern Database database;
extern Zone *zone;
@@ -222,7 +227,34 @@
Mob* EntityList::AICheckCloseArrgo(Mob* sender, float iArrgoRange, float iAssistRange) {
if (!sender || !sender->IsNPC())
return 0;
+#ifdef KD
+ Vector *ngh=terrain.neighbors(sender->GetID());
+ if(ngh==NULL){
+ //printf("Mob::AICheckCloseArrgo , %d has no neighbors\n",sender->GetID());
+ return 0;
+ }
+ int ncount= ngh->size();
+ //printf("Mob::AICheckCloseArrgo , got %d neighbors for %d ",ncount, sender->GetID());
+ Mob* neighbors[ncount];
+ ngh->copyInto(neighbors);
+ //for(int i=0;i<ncount;i++) {
+ // printf("%d:[%4.1f,%4.1f]", ((Mob*)ngh->get(i))->GetID(),
+ // ((Mob*)ngh->get(i))->GetX(), ((Mob*)ngh->get(i))->GetY());
+ //}
+ KDIterator<Mob*> iterator(neighbors,ncount,FORWARD);
+#ifdef KDSTAT
+ printf("%d :",sender->GetID());
+ iterator.Reset();
+ while(iterator.MoreElements()) {
+ Mob* mob = iterator.GetData();
+ printf("<%d>",mob->GetID());
+ iterator.Advance();
+ }
+ printf("\n"); fflush(stdout);
+#endif //KDSTAT
+#else
LinkedListIterator<Mob*> iterator(mob_list);
+#endif
iterator.Reset();
float dist;
//float distZ;
the other code (Terrain and Hashtable and Vector ... )are a available here
http://perso.wanadoo.fr/afou/khalzed...ighbors.tar.gz
you need to add -DKD and -DKDSTAT to you COPTS in the zone makefile
tune verbosity by editing the VERBOSE define in Terrain.cpp
Tpical output
Code:
...
Request for neighborhood before initializing
Request for neighborhood before initializing
...
Code:
in EntityList::DoorProcess, time is 5.0:
got 55 entities from mob_list
updating terrain, 55 mobs
enter collide with 55 elements
Terrain::collide for distance 100.0 found :
54 groups of average size 9.9 (max group : 18 + self), and 1 lonely
linear parse : 532 instead of 3025 (17.6%)
leavin collide
nieghbours set
llnear : parse checks wil be made using cache, and thus estimates the amount of cpu used (17,6% means you cut down cpu for check of 82%)
Drawbacks :
* you must select a big-enough value for the cache range checking. on a 'typical' DB :
Code:
mysql> select aggroradius, count(id) from npc_types group by aggroradius;
+-------------+-----------+
| aggroradius | count(id) |
+-------------+-----------+
| 0 | 63 |
| 45 | 152 |
| 65 | 26669 |
| 85 | 37 |
| 200 | 44854 |
+-------------+-----------+
set distance to 200.0f + 20.f (estimated distance moved between two cache updates). The lower, the smaller the groups, thus the less CPU used. But some zones might only have 65.0 agrroradius mobs.
* Use a better timer. Once every second should be fine.
* Nothing ensures that the first call to cache is valid. Thus the first checkings may abort. It does not seem to have any impact, as process goes up normally after the cache has been set.
* the code was written from scratch, or translated from java. It has memory leaks (at least freeing the old hashtable before update, but most probably more). However interfaces are small, so one could easily subst Hashtable and Vector classes for more reliable ones.
As of this code, it gets Sig segv after a few minutes. =(
* some comments are out of date, and irrelevant
Besides this (little) unpleansant effect, results are good. Very good.
Hybrid Mode
