New Concept: Proximity Spawning (to reduce bandwidth usage)

[trevius]

While talking over performance issues with one of my guides, I came up with an idea that might be an awesome new feature to make a huge impact on the emulator. I think this feature could potentially reduce server load and bandwidth usage by a very noticeable amount.

I think this may also help reduce zone crashes or player LDs from raids in highly populated zones. I have tested and found that a zone with a large amount of spawns will almost always have lag if a raid of 3 groups or more is in it and fighting, but if they fought the same encounter in a zone with only a couple of NPCs there is no lag at all.

The idea is to have a way for spawns to only spawn if a player is within a set proximity to them. So, if a player is in 1 corner of the zone and no other players are in the zone, only the mobs in that corner of the zone would be spawned, which should considerably lower the traffic being sent to the client and possibly server load to manage pathing, scripts, etc on the other NPCs that aren't spawned. As players move throughout the zone, mobs set to use this system will spawn around them as they get within a set range.

The Details so far:

1. To make this work, we could use something similar to aggro radius or proximity, where the spawn point is waiting for a player to enter it's radius before actually spawning if doesn't have time left on the spawn timer. I think that the code for aggro radius might be a good place to start for getting this setup. The server will look at the spawn locations and set a radius to spawn for NPCs that are set to use this feature.

2. I am thinking that either the spawn_conditions table or maybe even just the npc_types table could be used to simply define 2 things to set this up. The first setting would be either 0 or 1 for if you want that particular NPC to use this system or if you want it to spawn normally. This way, you can have named mobs that are always up and just set trash spawns to use this system to reduce the bandwidth load. Any special NPCs with scripts or special pathing can all leave this feature disabled, to make this setup as customizable as anyone wants. The second setting will just be the radius range for the NPC to spawn in. If you are spawning small indoor zone like an LDoN dungeon, you could probably set all trash mobs to spawn within a 200 radius and no one would ever even be able to tell that this system was different than how it worked before (accept MQ users who would be like "WTF" lol). Or, if you were doing a large outdoor zone, you might set the range as far as 600 or so. I don't think mobs are drawn much further than that anyway. Even with a large range like that, a huge zone could still be over 50% empty most of the time, which should make a huge impact on bandwidth.

Post here if you have any concerns, suggestions or thoughts on this system. I think it should be doable and might make a huge difference on servers with limited bandwidth!

I am going to see if I can start figuring out where to even begin on coding this, but if any of the coders want to help out, you are more than welcome! If this ever gets finished, I would be extremely excited to try it out and see what if any impact it has on bandwidth and server load.

[ChaosSlayer]

I am gettying a feeling that in order to detect prox to spawn something you will need first to spawn something to detect proximity =)

Of course just a "watcher" trigger prabobbly will use less CPu/ram than actual mob, but then you running in number of issues to set a whole new way to respawn mobs, encounters, named etc who should be otherwise "UP" and perhaps even trackable (may end up been more complicated that you allready covered)

Another issue- a player running at high end SoW (60%+) speed will be covering a lot of ground VERY fast - this may result in mob spawnign right on top of him as he appraoches since delay in spawn is unavoidable, as well requring you to despawn as player moves away. Now if you got 5 players runing at sow speed in near prox after each other, the whole system turns into spawn fest and i would say MASSIVE server side CPU work as server will be requred to chain spawn/despawn/spawn/etc mobs as group of players runs by.

Not cirticizing idea itself - I just belive its a too complex approach to improve server performance :)

[trevius]

Well, consider that every NPC already has a radius check when they check for people entering aggro range. So, this system would essentially only be extending that radius, which means it probably wouldn't cause more server load in that aspect.

Then, consider that NPCs that might have running scripts, pathing, spell casting, and other checks running continuously would now only be running them when players are within range.

Also, I can repop an entire zone at once with only a blip of a performance hit. If only 2 or 3 spawns are popping per second while players are running around, I don't think that would cause any noticeable impact on performance. Even if they were moving fast enough to spawn 20 at once, it would only happen while they are running around, not while they are fighting, unless maybe if they are kiting. And, raid fights are my main concern for reducing lag. Raids and AE groups are the only real things that I ever see cause performance hits on my server.

And for players moving at really high speeds, normally that would be in open zones outdoors. In that case, you could either leave this system off for all NPCs in the zone, or set them to have a really large radius to ensure that mobs are popping on top of people. I don't think anyone moves faster than 600 feet per second without warping hehe.

Another bonus to this feature is that admins could setup zones that MQ maps are useless for. Players wouldn't be able to see which spawns are up or down on the map unless they actually entered the nearby area. I imagine that could be useful in many situations for those anti-MQ admins :)

The nice thing about this idea is that it would be a fully optional setting. You could leave important NPCs like Named and other scripted NPCs up all of the time by setting them to not use the system. This system is mainly to get rid of unneeded trash spawns.

I do think that the coding for this might be pretty easy to do. I am going to look into the aggroradius code and see if there is a way to possibly combine that with the spawn2 table to make the server watch for players to enter a set radius around each spawn point.

Yeah, not having an NPC there to base the radius check is probably my main concern, but I still think it should be possible. And the potential for very noticeable performance increases should be worth at least looking into this further.

[trevius]

After thinking about it a little more, there would probably have to be a few extra things done to make sure this system was pretty flawless. Most importanly is to make sure that if the NPC is following a running player that it won't poof once the player gets too far away from it's spawn point. So, if IsEngaged, then it negates it from despawning.

Also, we might want to consider adding extra code to make sure that people can't exploit the system by pulling a single mob that is just barely within range to spawn so they can avoid pulling the other spawns that would normally be near it. But, most likely this wouldn't even be a factor if we set the radius range to something like 300+, since I don't think anything can pull from that far anyway.

Here is some unmodified code from the source I found quickly to maybe start looking at to base this code on:

zone/aggro.cpp

//look around a client for things which might aggro the client.
void EntityList::CheckClientAggro(Client *around) {
_ZP(EntityList_CheckClientAggro);

LinkedListIterator<Mob*> iterator(mob_list);
for(iterator.Reset(); iterator.MoreElements(); iterator.Advance()) {
_ZP(EntityList_CheckClientAggro_Loop);
Mob* mob = iterator.GetData();
if(mob->IsClient()) //also ensures that mob != around
continue;

if(mob->CheckWillAggro(around)) {
mob->AddToHateList(around);
}
}
}


LinkedListIterator<Mob*> iterator(mob_list);
for(iterator.Reset(); iterator.MoreElements(); iterator.Advance()) {
Mob* mob = iterator.GetData();
if(mob->IsClient()) //also ensures that mob != around
continue;

if(mob->DistNoRoot(*from_who) > d2)
continue;

if(engaged) {
int32 amm = from_who->GetHateAmount(mob);
if(amm == 0) {
towho->Message(0, "... %s is not on my hate list.", mob->GetName());
} else {
towho->Message(0, "... %s is on my hate list with value %lu", mob->GetName(), amm);
}
} else if(!check_npcs && mob->IsNPC()) {
towho->Message(0, "... %s is an NPC and my npc_aggro is disabled.", mob->GetName());
} else {
from_who->DescribeAggro(towho, mob, verbose);
}
}
}

Also, another idea that would help bandwidth and could replace this idea would be to just make it so that only mobs withing X radius of a player will send their current position information to them regularly. The entire zone would still be spawned exactly like it is now on the emu, but the client would only get updates from nearby mobs instead of every mob in the zone. It wouldn't really effect server load, but it should definitely help bandwidth and may be a better solution than the one I am suggesting in this thread. But I don't know how possible this second idea would be.

I am trying to figure out why WoW Emulator servers can handle 2000 players with only 1 or 2MBs of upload bandwidth (at least that is what I have heard). If it is true, then there definitely has to be something we can cut down by alot to help reduce bandwidth. And, I am almost positive that WoW doesn't send all spawn information to all players, I think they do a radius type thing like I am suggesting.

[trevius]

Still looking into this, it seems like this would maybe not be too hard to implement into the spawn_conditions code. Instead of just checking the time of day, it could have a separate option to just check player range from the spawn point before spawning and then depop if they get out of range of the NPC once it has spawned if they don't have aggro on it already.

I am trying to think of this on a per mob basis to make the concept easier to grasp which should hopefully make coding easier. Basically, all we need is a way for the server to spawn an NPC when a player gets near a spawngroup location without using any kind of placeholder to spawn it. It would have to check if an NPC is already spawned at that location before it tries to spawn another. Then, there needs to be a similar setup to depop the NPC when they get out of range if the NPC isn't engaged/aggroed.

I am sure this could be done with quests fairly easily, but it would be much easier to do it for entire zones at a time by setting a simple setting in the database. I think we could even potentially just have the check run as a client location check vs. the spawn group location and radius settings. Then, every spawn location in the zone wouldn't be looking for players to enter their radius, the check would only be done from around the client if they got within the radius which might reduce server load as well.

it looks like the spawn_conditions are checked before anything else when deciding to spawn an NPC, so that would be a good thing to reference when setting up this system.

Doing the coding work for this is probably a bit above my skill level, but I will keep looking into possibilities of how to write code for it.

[trevius]

Another thing I thought of is that the spawn group IDs, the spawn locations (X, Y, Z), and the spawn_radius setting will probably all need to be loaded into memory when the zone boots up. This way, the system can work without having to poll the database constantly for the spawn locations when it is checking the radius.

[ChaosSlayer]

I am trying to figure out why WoW Emulator servers can handle 2000 players with only 1 or 2MBs of upload bandwidth (at least that is what I have heard). If it is true, then there definitely has to be something we can cut down by alot to help reduce bandwidth. And, I am almost positive that WoW doesn't send all spawn information to all players, I think they do a radius type thing like I am suggesting.

its a good notice. A friend of mine plays wow his loading time is INSTANT from desktop into the game.
Thsi may have to do soemthign with wow inherited seamless zoning structure - the game is inheretly designed to be zoneless (with few exeptions) and this means any given player is only been sent information of some small surrounding area. However this does not mean that mobs are not up.

Now even with all those "wow" features (wow world is much smaller than eq, but on other hand a player is only present in a single zone at a time) the diffirence in numbers of players supported is massive - there got to do be something we missing in how to handle server performance

[KLS]

Personally I really hate this idea, not because i'm against the idea behind it but because I think it's the wrong approach. We really need a more involved spawn conditionals system so people can setup their events in an intelligent manner.

Perhaps a system where npcs can spawn and despawn based on certain conditions set by the quest system. Ex: In this case your boss is engaged and you have it set boss_one_engaged flag for the zone and all npcs that aren't essential despawn. Or perhaps you have a linear zone and only once a boss is killed the trash and next boss will spawn. etc etc.

[KLS]

Oh yeah and how wow works is just more efficient, it's also facilitated by the client.

Every continent is separated into zones which are separated into smaller areas which are all separated into smaller map nodes. Npcs in a node are only active if a player is nearby. At least this is how the emu basically works; not how the official servers work.

Perhaps we could have npcs freeze and not do ai if they're a certain distance from player characters. Might cause some problems for existing events.

[ChaosSlayer]

Personally I really hate this idea, not because i'm against the idea behind it but because I think it's the wrong approach. We really need a more involved spawn conditionals system so people can setup their events in an intelligent manner.

Perhaps a system where npcs can spawn and despawn based on certain conditions set by the quest system. Ex: In this case your boss is engaged and you have it set boss_one_engaged flag for the zone and all npcs that aren't essential despawn. Or perhaps you have a linear zone and only once a boss is killed the trash and next boss will spawn. etc etc.

well this may work for sort of ldon/raid/encounter instance, but then you don't realy need anything special - when boss is engage you simply send a signal to depop entire zone exept the econuter


the real issue comes to handlign somethign as large as West Karana or Dread Lands which supose to have crap load of trash mobs running around

[KLS]

The more I think about it the more I think having npcs freeze if there's no pc nearby would help a lot with the situation and have less of a downside than popping and repopping based on proximity.

[trevius]

We have already been testing a quest system to depopall() on all trash mobs when a boss mob or named is being killed. It seems to completely stop all lag as compared to previously people would go LD and lag extremely bad in some cases.

But, I really don't like the quest solution, because then anyone else in the same zone will then see an empty zone, which not only looks bad, but also lets them roam freely without clearing anything and basically negates all of the work to create the trash mobs in the first place.

Any special settings like the radius_spawn idea or freezing them to stop all AI and pathing would have to be specified by a setting in the NPC_types table so it could be done on a per mob basis. Then you can decide which ones you want to be affected by any of these ideas, and which ones to remain normal all of the time. So, bosses, scripted NPCs and maybe some roamers might want to have this setting turned off, but other than that, almost all trash mobs aren't always needed.

By turning off the AI or freezing the mobs like KLS mentioned, that might help the server performance, but I honestly don't see any issues at all lag-wise on my local lan, ever. I only ever hear about the lag, so it is pretty obviously a bandwidth issue. I have 1MB upload bandwidth from my ISP, which is fairly decent as far as home connections go. If 1MB up can have lag during a raid of about 3 groups with maybe 70 people logged into the server, then I think there could be some definite improvements to improve bandwidth utilization.

Unfortunately, I don't know of any way to not send regular updates of the current location of every spawn in the zone every second to every character in the zone. So, the only solution I can think of is to not have trash mobs spawn unless a player is within range. The only other option would be if someone could figure out a way for the server to only send location updates for NPCs within a radius of the client.

[AndMetal]

I wonder if we might be able to look at this a different way, especially since this seems to be more a bandwidth issue than a processing issue (which could also explain the issues with Warrior Rampage in AoE situations).

While roaming around in a zone, what kind of information is transmitted to the client on a regular basis? Spawn information, etc? Also, are there any kind of limits? So, is everything being sent to everyone, or are there proximity limits on these? If there aren't proximity limits, I think that's where we need to start.

Anyways, just a thought...

[KLS]

Spawn info is sent on login and new spawn. Or if a spawn has to change shape for some reason, typically walking around you wont see many spawn infos. Movement updates are the big thing... which if it's a mob far away they only send movement updates once every 60 seconds, close npcs ie ones you can see send movement updates every few seconds.

[trevius]

Maybe if there was a way to adjust how far away the regular movement updates get sent. I use MQ which helps a ton with developing content and standing in the main part of Dreadspire, I can see probably 50 mobs in the entire main section all moving very accurately and seemingly sending multiple updates per second. It seems to be somewhere around 800 distance away. I can only ever see a max of 400 distance in the entire zone since it is all indoors. So, if I could somehow set that range on a per zone basis, that might help a bit. Also, if it was possible, I wouldn't mind the option to completely disable the zonewide 1 minute updates on a per zone basis. I don't see why my client even needs to be aware of mobs outside of my visual range other than for MQ purposes, which really has no part in actual game play.

I know that the rule for it could be adjusted, but for some zones, the location information might be more important than others. And I know for a fact that those updates are pretty heavy on the server or bandwidth. At one point, I tried setting those zonewide updates in the rules to be every 1 second, because I didn't know what it was doing exactly. With it set that way, my server was so insanely laggy that it was unplayable after a few people logged on. Even 1 time per minute, if you multiply that times 60 clients on the entire server, you are averaging a zone wide update to 1 client per second. Double the players to 120, which is about the max my server can handle and it goes up to an average of 2 zonewide updates per second.

Then, once you start factoring in combat spam that has to go out to each client, a big raid can cause a significant hit to bandwidth and performance. If all of those players were all fighting in separate areas, they would only be receiving their own combat spam, but all in a tight area, everyone gets everyone's combat spam, so it multiplies what needs to be sent by how many characters are there.

I think the AE issue with rampage is more of a server resource issue than it is on bandwidth, since AndMetal brought it up. The main reason to think this is because it is one of the few things that can an will crash a zone if you have too many mobs in the rampage pull. I don't think bandwidth can cause a zone crash, just cause lag and LDs. Only high running processes or bugs can cause crashes, or at least that is my guess. I think a rampage pull of 30+ mobs is just too much combat spam all hitting at the exact same time for the server to handle at once.

I am sure there are some solutions to help this stuff considerably. Even a 20% decrease in bandwidth could make a considerable difference on home run servers that don't have practically unlimited upload speeds. Right now, I think players seem to average about 5k per player on normal use. Though, that probably spikes up a lot during large raids.

[trevius]

Woot! I think I found part of what KLS is talking about:

zone/updatemgr.cpp
//squared distances for each level
//these values are pulled out of my ass, should be tuned some day
const float UpdateManager::level_distances2[UPDATE_LEVELS]
= { 50*50, 250*250, 500*500, 800*800 };

//delay between sending packets in each level, in ms
//its best if they are all multiples of UPDATE_RESOLUTION
//these values are pulled out of my ass, should be tuned some day
const int32 UpdateManager::level_timers[UPDATE_LEVELS+1]
= { UPDATE_RESOLUTION, //.3s
2*UPDATE_RESOLUTION, //.6s
3*UPDATE_RESOLUTION, //.9s
9*UPDATE_RESOLUTION, //~2s
34*UPDATE_RESOLUTION //~10s
};

I like how he says they are pulled out of his ass and need to be tuned lol. If there was a way to set these on a per zone basis, I think that would be amazing. If that would be too complex, I think these could each easily just have rules tied to them so you can adjust them all manually to find which is the best combination.

I think more could definitely be done, but I will have to look into finding other parts that could possibly be tweaked further.

[So_1337]

We have already been testing a quest system to depopall() on all trash mobs when a boss mob or named is being killed. It seems to completely stop all lag as compared to previously people would go LD and lag extremely bad in some cases.
Just a quick note on that. We used to have trouble on our server before we had our DS3 line installed. We'd have too many players whacking on things in heavily NPC-populated zones. Killing Yelinak in particular comes to mind. Now, for Skyshrine, our trash mobs were already all set to a 30 minute repop. We'd do a #depopzone and then manually spawn him so we'd have a chance at killing him without us all getting bugged out. That worked out fine, unless we were slow and the zone repopped before then. At that point, the zone is completely overwhelmed, and everything will freeze for a good long while. 500+ NPCs in Skyshrine =X

Anyway, just my thoughts. I'm sure that if you're doing this, you've already thought of it, but wanted to suggest that if you use quest::depopzone that you make sure to disable the respawn timers until the boss has died, and then re-enable them. Though that only sounds useful for fights that aren't intended to have the added difficulty of add control =)

Just my thoughts, this sounds like a really good suggestion if a reasonable way to implement it can be found.

[kayen85]

Working with Trev on this,

We have as system set up atm that if an event is engaged, we do a zone wide depop of all trash mobs using quest::depopall(npcid) for each trash, then pop some KOS guard mobs in specific locations so people can't just run around the zone with a few others things built in to avoid abuse. When event is over zone repops all the trash with quest. This works fine. But obviously the flaws are there which is it really affects any other group in the zone forcing a 8-10 minutes of down time. Plus if you want to do an event with smaller force it could take even longer, and then if your moving from event to event quickly you could basically have the zone locked up for a while making it unplayable by others. Is that worth it so everyone doesn't have a 70% chance to lock up/crash when fighting the event, probably but its not the ideal solution.

There are other ways around it which are better, but just require more advanced planning and coding useing standard scripts, set up certain areas of the zone with only certain NPCid's then have quest mobs spawn and check aggro if any players are in that area and if its clear then depop it, otherwise leave it up and hope by the time they are done in the area the event is over.

But really all these solutions are cumbersome and were praying we can get something more solid.

[ChaosSlayer]

anoher thing: you think turning OFF Npc buff friends would help with the lag?
Since npc needs to not only buff all their friends but also keep a watch when their buffs expire etc

[KLS]

Mob::SendPosUpdate(int8 iSendToSelf) is where you would want to look. We have it hardcoded to 800 dist but it wouldn't be too hard to load that from the zone table and use a custom value instead. Turning off more advanced ai like spell casting and buffing when people aren't close to npcs and npcs aren't engaged is probably a good idea too.

[MNWatchdog]

How about have the server dynamically base the range it sends the clients updates of mobs info is based on if the person is moving around or not.

Someone staying relatively stationary doesnt need to get updates from mobs more than 400 distance, while someone running certainly would in order to avoid running into said mobs.

This also avoids having to set this range on a per zone bases.

[MNWatchdog]

PS You could even add a fudge factor based off current server population so when theres less people logged on the range would be longer and be shorter when more people are logged in.

[Rocker8956]

Mob::SendPosUpdate(int8 iSendToSelf) is where you would want to look. We have it hardcoded to 800 dist but it wouldn't be too hard to load that from the zone table and use a custom value instead. Turning off more advanced ai like spell casting and buffing when people aren't close to npcs and npcs aren't engaged is probably a good idea too.

I wrote some code that replaces the 800 found in Mob::SendPosUpdate(int8 iSendToSelf) with a distance pulled from the zone database. But I have aquestion that is probably dumb but Which would be better...

Query the database everytime the Mob::SendPosUpdate(int8 iSendToSelf) is called? I assume this would be a lot.
OR
Set a variable's value when the zone boots up based on a database query. Then get that variables value whenever Mob::SendPosUpdate(int8 iSendToSelf) is called?

Like I said probably dumb questions but I am not sure how often this would be hitting the database.

[MNWatchdog]

I wrote some code that replaces the 800 found in Mob::SendPosUpdate(int8 iSendToSelf) with a distance pulled from the zone database. But I have aquestion that is probably dumb but Which would be better...

Query the database everytime the Mob::SendPosUpdate(int8 iSendToSelf) is called? I assume this would be a lot.
OR
Set a variable's value when the zone boots up based on a database query. Then get that variables value whenever Mob::SendPosUpdate(int8 iSendToSelf) is called?

Like I said probably dumb questions but I am not sure how often this would be hitting the database.
Do it the way I posted above. :)

[Derision]

Query the database everytime the Mob::SendPosUpdate(int8 iSendToSelf) is called? I assume this would be a lot.


That's the last thing you want to do. I just compiled zone with profiling enabled and stood in Dreadlands by Karnor's Castle for 60 seconds and there were around 4500 calls to that method.

[trevius]

I would almost certainly say to set the variables on zone bootup. Seems to be the obvious choice. Anything that reduces the number of database hits is good, and setting that at zone bootup shouldn't cause any performance differences at all.

But, even though KLS says the 800 is hard coded, I can say that just by looking at what the MQ map shows, it seems pretty clear that the code I posted above is the code used for sending position updates. Within a range of 50ish, the movements on the map are almost perfectly smooth (.3 second timer), then from 50 to about 250, they are slightly less smooth (.6 second timer), and from 250 to 500 even slightly less smooth (.9 second timer), And anything from 500 to 800 is kinda choppy (2 second timer), and after that it uses the zonewide update setting, which by default is 1 minute, but if you set the rule it can be much higher.

So, I am not completely convinced that the 800 setting KLS mentioned is what is being used all of the time.

Here is the code that I think is handling those updates:

mob.cpp
void Mob::SendPosUpdate(int8 iSendToSelf) {
EQApplicationPacket* app = new EQApplicationPacket(OP_ClientUpdate, sizeof(PlayerPositionUpdateServer_Struct));
PlayerPositionUpdateServer_Struct* spu = (PlayerPositionUpdateServer_Struct*)app->pBuffer;
MakeSpawnUpdate(spu);
if (iSendToSelf == 2) {
if (this->IsClient())
this->CastToClient()->FastQueuePacket(&app,false);
}
else
#ifdef PACKET_UPDATE_MANAGER
entity_list.QueueManaged(this, app, (iSendToSelf==0),false);
#else
entity_list.QueueCloseClients(this, app, (iSendToSelf==0), 800, NULL, false);
#endif
safe_delete(app);
}

entity.cpp
void EntityList::QueueManaged(Mob* sender, const EQApplicationPacket* app, bool ignore_sender, bool ackreq) {
LinkedListIterator<Client*> iterator(client_list);

#ifdef PACKET_UPDATE_MANAGER
EQApplicationPacket* tmp_app = app->Copy();
#endif

iterator.Reset();
while(iterator.MoreElements())
{
Client* ent = iterator.GetData();

if ((!ignore_sender || ent != sender))
{
#ifdef PACKET_UPDATE_MANAGER
ent->GetUpdateManager()->QueuePacket(tmp_app, ackreq, sender, ent->DistNoRoot(*sender));
#else
ent->QueuePacket(app, ackreq, Client::CLIENT_CONNECTED);
#endif
}
iterator.Advance();
}
#ifdef PACKET_UPDATE_MANAGER
EQApplicationPacket::PacketUsed(&tmp_app);
#endif
}


void EntityList::QueueClientsStatus(Mob* sender, const EQApplicationPacket* app, bool ignore_sender, int8 minstatus, int8 maxstatus)
{
LinkedListIterator<Client*> iterator(client_list);

iterator.Reset();
while(iterator.MoreElements())
{
if ((!ignore_sender || iterator.GetData() != sender) && (iterator.GetData()->Admin() >= minstatus && iterator.GetData()->Admin() <= maxstatus))
{
iterator.GetData()->QueuePacket(app);
}
iterator.Advance();
}
}

updatemgr.cpp
void UpdateManager::QueuePacket(EQApplicationPacket *app, bool ack_req, Mob *from, float range2) {
int r = UPDATE_LEVELS;
UMMap *cur = levels;
const float *cur_d = level_distances2;
cur += UPDATE_LEVELS; //move to the end.
cur_d += UPDATE_LEVELS - 1;
//work backwards since mobs are more likely to be further away
for(r = UPDATE_LEVELS; r >= 0; r--, cur--, cur_d--) {
if(range2 < *cur_d)
continue;
//this packet falls into this queue...
uint32 id = MakeUpdateID(from, app);
// if(r < 2)
// net->QueuePacket(app, ack_req);
//LogFile->write(EQEMuLog::Debug, "Queueing packet from %s (0x%.4x) id=0x%x at level %d\n", from->GetName(), app->GetOpcode(), id, r);
app->PacketReferenced();
//reference decrementing is taken care of my UMType destructor
//if anything is overwritten
(*cur)[id] = UMType(app, ack_req);
// (*cur)[id] = UMType(app->Copy(), ack_req);
return;
}
//if we get here, were in trouble...
}

[KLS]

Yeah I'm right and wrong it depends if you have update manager enabled or not. By default it's turned off though.

[Rocker8956]

Well after looking into this a bit further it looks like I am going to duck out of this one. This code is really out of my league and I currently do not have time to learn it.
Sorry guys, I was going to give it a shot but don't have the time. Hopefully someone else understands all that code and how it works.

[trevius]

Hmm, I haven't turned update manager on myself. But, after checking into it more, it seems like both are actually being used. Both update manager and the hard setting at the same time. It seems like the hard setting is the cutoff to where it will only use the zonewide update timer. But, within the hard setting it uses the settings from the update manager.

What I have done so far is to change the hard settings from 800 down to 400 like this:

mob.cpp
// this one just warps the mob to the current location
void Mob::SendPosition() {
EQApplicationPacket* app = new EQApplicationPacket(OP_ClientUpdate, sizeof(PlayerPositionUpdateServer_Struct));
PlayerPositionUpdateServer_Struct* spu = (PlayerPositionUpdateServer_Struct*)app->pBuffer;
MakeSpawnUpdateNoDelta(spu);
//? spu->heading *= 8;
#ifdef PACKET_UPDATE_MANAGER
entity_list.QueueManaged(this, app, true);
#else
entity_list.QueueCloseClients(this, app, true, 400);
#endif
safe_delete(app);
}

// this one is for mobs on the move, with deltas - this makes them walk
void Mob::SendPosUpdate(int8 iSendToSelf) {
EQApplicationPacket* app = new EQApplicationPacket(OP_ClientUpdate, sizeof(PlayerPositionUpdateServer_Struct));
PlayerPositionUpdateServer_Struct* spu = (PlayerPositionUpdateServer_Struct*)app->pBuffer;
MakeSpawnUpdate(spu);
if (iSendToSelf == 2) {
if (this->IsClient())
this->CastToClient()->FastQueuePacket(&app,false);
}
else
#ifdef PACKET_UPDATE_MANAGER
entity_list.QueueManaged(this, app, (iSendToSelf==0),false);
#else
entity_list.QueueCloseClients(this, app, (iSendToSelf==0), 400, NULL, false);
#endif
safe_delete(app);
}

I also slightly tweaked the update manager settings to be a little smaller and less frequent for mid range distances:

updatemgr.cpp
//squared distances for each level
//these values are pulled out of my ass, should be tuned some day
const float UpdateManager::level_distances2[UPDATE_LEVELS]
= { 50*50, 250*250, 400*400, 600*600 };

//delay between sending packets in each level, in ms
//its best if they are all multiples of UPDATE_RESOLUTION
//these values are pulled out of my ass, should be tuned some day
const int32 UpdateManager::level_timers[UPDATE_LEVELS+1]
= { UPDATE_RESOLUTION, //.3s
2*UPDATE_RESOLUTION, //.6s
3*UPDATE_RESOLUTION, //.9s
12*UPDATE_RESOLUTION, //~2s
48*UPDATE_RESOLUTION //~10s
};

And finally, I set my rule for the zonewide updates from 1 minute to 10 minutes. I really don't even know if we need zone wide updates at all. After these changes, so far the raids in Dreadspire which I was using as a reference for the lag issues have said that the lag is now completely gone. I still need to do more testing, but so far this is looking promising. We may not want these same settings across the board or anything, but certainly smaller closed in zones like dungeons should have the option to lower these settings.

I posted the code changes with colors because this isn't any sort of a final code submission. If I come up with anything that seems final, I will try to get it in the format that KLS is wanting. But, the code currently posted should help make it easier to discuss further steps.

Oh, an one idea I had that could potentially save me a TON of bandwidth was if I could disable position updates completely maybe by setting them to 0 for my server base zone which is Nexus. I only have 1 roaming NPC in there anyway, so if I stopped it from roaming, they wouldn't need position updates. And since that zone is almost always occupied by many AFK players, it would potentially save me a TON of bandwidth. Also, if we ever get the bazaar working, I think we should have similar options to help reduce bandwidth in there.

[cubber]

This sounds interesting but I have a few questions to think about.

1. If this despawns mobs that are not in a certian radius of the player then couldn't this approach be used as an exploit? If a player is trying to camp a named mob and the mob is not up, couldn't the player just venture out of the place holder's radius to despawn it? Triggering a respawn when they come back into it's radius, essentialy cycling the camp without killing anything? What about named mobs like CT that are only supposed to spawn on a schedual?

Or will the "despawned mob" basically be "cached" until it is revealed again, killed, or cycled by spawn timer?

2. What about respawn times in general? Could this be used to get around respawn times?

3. Also in comparison to WoW, I think that the spawn radius would have to be quite larger than what they impliment. It is quite annoying to be able to see a few hundred yards away but not see any mobs in that area until you are almost right on top of them.

[Rocker8956]

This does not effect if the mob is spawned. Basically the mob is still there but the player does not get updates on the mob's position unless the player is within so many feet of the mob.

One question I have though, does this effect track?

[cubber]

Ahh that makes more sense then.

[trevius]

Cubber, the original suggestion to actually depop mobs that were out of range would have worked perfectly fine for everything accept Track. The spawn timers would still be checked before a mob would be spawned if a player entered the spawn radius. The only thing you would need to take into account to avoid possible exploits would be to remember that you don't want to depop and repop named or anything with particularly nice loot tables, especially if they are set to equip the items. As long as they don't equip the items, the players would still have no way to tell what loot was or wasn't on the mob, so even named could potentially be depopped. The main thing is that there would be a per NPCID setting to allow you to enable the spawn to use the system or just to stay up like mobs currently do.

But, it looks like this change may not even be needed anyway as there seems to be a much better way to accomplish what I was originally wanting to do just by adjusting values in the source for setting the radius that the updates are sent.

The last code changes I posted in this thread show how to adjust the source to help reduce bandwidth. As far as I can tell and have heard so far, even just making the changes I posted has made a HUGE impact (in a positive way) on the amount of lag and performance problems on the server. The only time my players have seen noticeable lag since the change was when my server broke 100+ players this weekend, which hasn't happened in a while. So, I am fairly confident that if we can make some code that allows each of these settings to be tweaked in the source, I think we can potentially make a great reduction in bandwidth utilization and allow more players on servers with lower upload speeds and with less lag.

I think we should have settings added to the zones table to set the QueueCloseClients settings for both warping to location and for walking animations. I also think we should have the options to be able to adjust all 4 of the level_distances2 settings individually as well as all 5 of the UPDATE_RESOLUTION settings. Of course there should be defaults set if the fields are left at 0, which would be default for the new fields. But, by giving this option, I really think high traffic zones could be tweaked enough to really make a big difference on any server.

Also, I have set zone wide updates to 10 minutes and so far I haven't noticed any different at all in game other than less lag from when it was set to the default of 1 minute. I will have to try running around in an open zone at GM speed to see if I notice anything weird. But, unless I am wrong, maybe we should allow the globalpositionupdate rule to have a setting that will completely disable zone wide updates. Maybe setting it to something like 0 or so could make it disabled.

Either way, I think we are on the way to increasing server performance for servers with limited bandwidth. I would love to see home servers able to reach the 200 or 250+ player counts that are seen on PEQ or the CEQ Dragon Soul server. I know PEQ is/was hosted in a Data Center which essentially gave it unlimited upload speeds and I assume Dragon Soul is as well.

[KLS]

Yes, you need zonewide updates.

But we can make the zone wide update smarter, it's only really a problem for mobs that move a significant distance in their roam path. Think large zones like plane of growth or temple of veeshan.

The problem is this:

Player is at point A and receives basic mob initial positions.
Player sees mob at point B 1000 units away but because it's out of update range and mob is a roamer it wont update.
Player moves to point B but mob is at point C 1000 units away because it roamed and now sees the ghosted mob because point C is out of update range too and point B was initial position.

We can make it smarter by sending updates to all players if a npc moves a certain distance threshold I think, then we wont have to send a global update for all npcs.

[Rocker8956]

I think this would only effect character's with track and people using MQ. Couple of questions to confirm that though.

Does track get the mob's position from the server everytime it ticks? or does it use the cleint's last known position of that mob?

The ghost would disappear before the player saw it because the player would have to be within the level 3 distance to see it correct? or does the update only happen if the mob is within that range?

Is the client smart enough to ask "Is this mob really there?" when the player tries to target it?

[Rocker8956]

Sorry for the back to back post, ran out of time to edit.

Does an update occur in the level 2 and level 3 intervals even though it occured during the level 1 interval?

[trevius]

I think the NPC ghost will still be there because it doesn't check if it is actually there, it only updates if it is there. So, since it isn't there, it would never update until the globalposition timer was up.

I do think we are doing the same work multiple times in some cases though. If so, it is a huge waste of bandwidth and resources. For example, from reading the code, it looks like the globalpositionupdate is done everytime the threshold (60 seconds by default) is met. But, it will still send it even if that same mob is within close range of the player and may have just sent an update already. Here is the code that decides when to send the position update:

npc.cpp

global_position_update_timer(RuleI(Zone, NPCGlobalPositionUpdateInterval)),

//lines between this code and the code below here:

//60 seconds, or whatever the rule is set to has passed, send this position to everyone to avoid ghosting
if(global_position_update_timer.Check()){
SendAllPosition();
}

And then the SendAllPosition code:

mob.cpp
// this one just warps the mob to the current location
void Mob::SendAllPosition() {
EQApplicationPacket* app = new EQApplicationPacket(OP_ClientUpdate, sizeof(PlayerPositionUpdateServer_Struct));
PlayerPositionUpdateServer_Struct* spu = (PlayerPositionUpdateServer_Struct*)app->pBuffer;
MakeSpawnUpdateNoDelta(spu);
//? spu->heading *= 8;
entity_list.QueueClients(this, app, true);
safe_delete(app);
}

After thinking about it more, maybe the zonewide update of the NPCGlobalPositionUpdateInterval should actually be part of the update manager settings. So, it all works in the same system and all works together to make it as efficient as possible and reduce any overlapping possibilities.

Maybe an all around better system would be to only update NPC locations if they actually move from their current position. So, only pathing NPCs or NPC that have been moved by a player by being pulled or whatever would ever be sending updates. Then you instantly reduce regular updates down to only pathing NPCs and the few that are maybe aggroed and chasing a player or whatever. Then, after the check to see if the NPC is moving happens, it would use a radius check to see how far away they are from the player to decide how often they will update the player. This should minimize traffic to a very bare minimum, at least the traffic related to spawn updates. From what I have seen, it does seem like a large portion of the traffic for the emulator is related to updates, so tweaks to the system could have a nice impact. If this could all be adjusted on a per zone basis, I wouldn't be too surprised if servers could be tweaked to handle double the number of players that they can now. I haven't really done any detailed testing on this yet, but from what I have seen, the changes I have made already are a very noticeable improvement.

Maybe if we could check the NPCs current position and if it differs by X amount from the last time it was checked, it sends a global position update.

[trevius]

Still looking into how to trim down the bandwidth from location updates, I think I know how things need to work to trim bandwidth to a minimum without effecting how players see the world.

If a player zones in, they will be sent position updates for all NPCs in the zone, but after that they only need to know if an NPC moves, depops/dies or spawns. Zoning and spawn/depop/death updates are already set, so all we need to adjust are the regular updates that occur.

First, we would only want position updates to come in if they NPC has actually moved, so maybe a check something like this could look for NPC movement:

float cur_x = GetX();
float cur_y = GetY();
float cur_z = GetZ();

if( cur_x != last_x || cur_y != last_y || cur_z != last_z ) {
float last_x = cur_x;
float last_y = cur_y;
float last_z = cur_z;
SendAllPosition();
}

Currently, all NPCs send regular updates whether they have moved or not, which is a major waste of bandwidth. Unless a zone is full of NPCs that move non-stop, then a simple change to only update when they do move will make a considerable difference.

Next, we would just have it use the Update Manager to set the levels and timers for updates. So that close npc updates will update often and NPCs that are further away will update slower with diminishing returns the further away they are. This code is already in place in the update manager, so my only suggestion would be to allow the levels to be able to be set in the zones table and then load those levels into memory for the zone when it boots up. We could also have an adjustable setting for the level timers in the zones table, but that isn't quite as important as the levels themselves. It is probably a good idea to have a default value for all zones if these fields are left at 0. But, it would also be nice if there was a way to disable position updates completely on a per zone basis if needed.

Last, I think we could make a big difference if we have a check to see if a player was actually moving before checking the Update Manager Levels. If a player is not moving, we could have it divide the levels by 2 so that you only get updates on nearby NPCs. Most of the time, players are not moving, so they don't need to have updates from very far away. But, if they are moving, you don't want things to warp right on top of them due to having low level settings on the update manager. This would further reduce the required bandwidth for position updates to help make it as efficient as possible.

Maybe using the client movement checks created for the MQ Detection that were added to #showstats could be used to check if a player is moving so it can decide to divide the update manager levels or not:

if (GetMovementSpeed() = 0)

Then have it divide the update manager levels by 2. If they are moving, then it just uses whatever the levels are set to for that particular zone.

With some help from other coders, I think we can get this working and make a huge impact on reducing bandwidth utilization. Since that is a big limiting factor for most emulator servers, I think this change of process would be good for the whole project. Any input from experienced coders would be much appreciated!

[KLS]

we would only want position updates to come in if they NPC has actually moved

I agree, it's a good thing it already does that. =p

Ima add your suggestion of a variable distance for the update manager based on zone settings. Also the global position update will no longer fire if you have the update manager enabled, and I think I'll make it being on default.

Edit: And actually after trying it, it seems like a lot of it may need to be rewritten before we can make it usable =/

[trevius]

Thanks for looking into this, KLS! I do know for sure that even just by changing the globalpositionupdate rule from 60 seconds to 10 minutes makes a huge difference on raid lag. With enough tweaking to the system to make it as efficient as possible, I think we could remove a large chunk of unneeded bandwidth usage. I wouldn't even be surprised if we could double the amount of players that a server could handle.

So, if we disabled the globalpositionupdate, do you think we would need to essentially add it to the update manager levels? Currently, there are 4 levels that can be set in the update manager. Could there be a 5th level that is just equal to anything greater than the 4th level to encompass the rest of the zone? Then maybe have an update timer for that level similar to how the global position updates work now, but adjustable per zone. I think that would take care of possible mob ghosting issues.

You mention that position updates are currently only sent if an NPC moves. That may be true for the update manager, but I think the globalpositionupdate is currently just sending the entire zone's NPC positions whether they moved or not. I think that is why non-moving NPCs seem to jump every minute, but I may be wrong about that. If it was only sending updates for NPCs that had moved, I don't think adjusting the timer setting rule would have made nearly as much impact as what I have seen from it.

I have been looking through the code for this alot lately. I know my code understanding is still noob at best, but from what I can tell, the globalpositionupdate is sending every npc's position whether they moved or not.

//60 seconds, or whatever the rule is set to has passed, send this position to everyone to avoid ghosting
if(global_position_update_timer.Check()){
SendAllPosition();
}

void Mob::SendAllPosition() {
EQApplicationPacket* app = new EQApplicationPacket(OP_ClientUpdate, sizeof(PlayerPositionUpdateServer_Struct));
PlayerPositionUpdateServer_Struct* spu = (PlayerPositionUpdateServer_Struct*)app->pBuffer;
MakeSpawnUpdateNoDelta(spu);
//? spu->heading *= 8;
entity_list.QueueClients(this, app, true);
safe_delete(app);
}

void EntityList::QueueClients(Mob* sender, const EQApplicationPacket* app, bool ignore_sender, bool ackreq) {
LinkedListIterator<Client*> iterator(client_list);

iterator.Reset();
while(iterator.MoreElements())
{
Client* ent = iterator.GetData();

if ((!ignore_sender || ent != sender))
{
ent->QueuePacket(app, ackreq, Client::CLIENT_CONNECTED);
}
iterator.Advance();
}
}

void Mob::MakeSpawnUpdateNoDelta(PlayerPositionUpdateSe rver_Struct *spu){
memset(spu,0xff,sizeof(PlayerPositionUpdateServer_ Struct));
spu->spawn_id = GetID();
spu->x_pos = FloatToEQ19(x_pos);
spu->y_pos = FloatToEQ19(y_pos);
spu->z_pos = FloatToEQ19(z_pos);
spu->delta_x = NewFloatToEQ13(0);
spu->delta_y = NewFloatToEQ13(0);
spu->delta_z = NewFloatToEQ13(0);
spu->heading = FloatToEQ19(heading);
spu->animation = 0;
spu->delta_heading = NewFloatToEQ13(0);
spu->padding0002 =0;
spu->padding0006 =7;
spu->padding0014 =0x7f;
spu->padding0018 =0x5df27;
}

I am not trying to second guess you, btw. I just want to understand what is happening to see how/where it can possibly be tweaked to work better.

[thepoetwarrior]

Any further work on these ideas?

[Drajor]

I have tentative plans to implement something similar on my server. I have not read this entire thread but from the gist I got my approach would be very different. There are already well established techniques and algorithms for dividing and searching space. See quadtree or octtree. If I do have a go I will share the results, whether successful or not.

[Drajor]

I got inspired and started work on this. My theory is as follows, note that I do not know anything about the mob update packets yet so I have made some assumptions.

This approach aims to address two things;
- Improve NPC proximity aggro check performance.
- Add the concept of Mob 'visibility'.

Each (zone)instance has a quadtree which all Mob's are added to when they are created and removed from when they are destroyed. The quadtree provides a query(region) interface which returns a list of Mob* which are within this region.

-- Aggro
When it comes time for Mobs to check for proximity agro, each mob passes an AABB which encloses it's aggro circle to the query interface. From the Mobs returned, we compare the absolute distance and factions as per normal.

-- Visibility
The client will query() at a fixed interval and provide an AABB which encloses it's 'visibility circle'. From the list of Mobs returned we check if any were added or removed (list diff, twice). If a Mob was added, the client gets a SPAWN_PACKET or if removed, DESPAWN_PACKET. When it comes time to update the client with new Mob positions, we only send packets for the mobs on their visibility list.

-- Important Notes
- Each time a Mob (Client or NPC) moves, they will need to update their position in the quadtree.
- Just before a mob checks for proximity aggro, they will need to update their AABB.

Comments? Suggestions?

[Drajor]

Upon further inspection I have decided to not continue with this. I believe the number of changes required would be significant and I do not have the knowledge to undertake them. Below is my (untested) code for the quadtree.

#ifndef DG_QUAD_TREE
#define DG_QUAD_TREE

#define QTCHILDREN 4
#define QTCAPACITY 25

// A maximum tree depth is defined to prevent infinite subdivisions (consider a train of 50 mobs all sitting on top of each other).
#define QTMAXDEPTH 10

// Directions.
#define QTNE 0
#define QTNW 1
#define QTSE 2
#define QTSW 3

#include <list>

class Mob;

struct QTAABB {
QTAABB(float pX, float pY, float pHalfDim);
float mX;
float mY;
float mHalfDim;
float mExtents[4];

const bool contains(Mob* pMob);
const bool intersects(QTAABB& pRegion);
};

class QuadTree {
public:

static QuadTree* create(float pX, float pY, float pHalfDim);
~QuadTree();

__forceinline const bool isLeaf() const { return mChildren[QTNE] == 0; }

const bool insert(Mob* pMob);
void remove(Mob* pMob);

// Search!
void query(QTAABB& pRegion, std::list<Mob*>& pResult);

private:

QuadTree(QuadTree* pParent, float pX, float pY, float pHalfDim, unsigned short pDepth);

void add(Mob* pMob);
void subdivide();
QTAABB mRegion;
QuadTree* mParent;
QuadTree* mChildren[QTCHILDREN];
unsigned short mDepth;

typedef std::list<Mob*> MobList;
typedef MobList::iterator MobListIterator;
MobList mMobs;
};

#endif

#include "dg_quadtree.h"
#include "../zone/mob.h"

#define QTMINX 0
#define QTMAXX 1
#define QTMINY 2
#define QTMAXY 3

// Shorthand Extents.
#define AABB_MINX mExtents[QTMINX]
#define AABB_MAXX mExtents[QTMAXX]
#define AABB_MINY mExtents[QTMINY]
#define AABB_MAXY mExtents[QTMAXY]

QTAABB::QTAABB(float pX, float pY, float pHalfDim) : mX(pX), mY(pY), mHalfDim(pHalfDim) {
// Pre-calculate AABB extents.
AABB_MINX = mX - mHalfDim;
AABB_MAXX = mX + mHalfDim;
AABB_MINY = mY - mHalfDim;
AABB_MAXY = mY + mHalfDim;
}

const bool QTAABB::contains(Mob* pMob) {
float mobX = pMob->GetX();
float mobY = pMob->GetY();
return mobX >= AABB_MINX && mobX < AABB_MAXX && mobY >= AABB_MINY && mobY < AABB_MAXY;
}

const bool QTAABB::intersects(QTAABB& pRegion) {
const float dims = pRegion.mHalfDim + mHalfDim;
return fabs(pRegion.mX - mX) <= dims && fabs(pRegion.mY - mY) <= dims;
}

QuadTree* QuadTree::create(float pX, float pY, float pHalfDim) {
return new QuadTree(0, pX, pY, pHalfDim, 0);
}

QuadTree::QuadTree(QuadTree* pParent, float pX, float pY, float pHalfDim, unsigned short pDepth) : mParent(pParent), mRegion(pX, pY, pHalfDim), mDepth(pDepth) {
memset(mChildren, 0, sizeof(QuadTree*)*QTCHILDREN);
}

QuadTree::~QuadTree() {
if(!isLeaf())
for(int i = 0; i < QTCHILDREN; i++)
delete mChildren[i];
}

void QuadTree::query(QTAABB& pRegion, std::list<Mob*>& pResult) {

if(!mRegion.intersects(pRegion)) return;

// Check: Each mob that belongs to this region.
for(MobListIterator i = mMobs.begin(); i != mMobs.end(); i++)
if(pRegion.contains(*i))
pResult.push_back(*i);

// No children to check.
if(isLeaf()) return;

// Search continues.
for(int i = 0; i < QTCHILDREN; i++)
mChildren[i]->query(pRegion, pResult);
}

void QuadTree::add(Mob* pMob) {
mMobs.push_back(pMob);
}

const bool QuadTree::insert(Mob* pMob) {
// Check: pMob within this region.
if(!mRegion.contains(pMob)) return false;

const bool hasCapacity = mMobs.size() < QTCAPACITY;
const bool atMaxDepth = mDepth == QTMAXDEPTH;

// Check: Is there capacity for pMob in this region OR the tree has reached the maximum depth allowed.
if(hasCapacity || atMaxDepth) {
add(pMob);
return true;
}
else if(isLeaf()) {
// Divide this region.
subdivide();

// Try adding pMob to the new children.
for(int i = 0; i < QTCHILDREN; i++)
if (mChildren[i]->insert(pMob))
return true;
}

// Error.
return false;
}

void QuadTree::remove(Mob* pMob) {
mMobs.remove(pMob);
}

void QuadTree::subdivide() {
const unsigned short childDepth = mDepth+1;
const float quarterDim = mRegion.mHalfDim * 0.5f;
mChildren[QTNE] = new QuadTree(this, mRegion.mX + quarterDim, mRegion.mY + quarterDim, quarterDim, childDepth);
mChildren[QTNW] = new QuadTree(this, mRegion.mX - quarterDim, mRegion.mY + quarterDim, quarterDim, childDepth);
mChildren[QTSE] = new QuadTree(this, mRegion.mX + quarterDim, mRegion.mY - quarterDim, quarterDim, childDepth);
mChildren[QTSW] = new QuadTree(this, mRegion.mX - quarterDim, mRegion.mY - quarterDim, quarterDim, childDepth);
}