New Concept: Proximity Spawning (to reduce bandwidth usage)

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