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

[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.

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