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.
Code:
#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
Code:
#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);
}