New Concept: Proximity Spawning (to reduce bandwidth usage)

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