EQEmulator Forums - New Concept: Proximity Spawning (to reduce bandwidth usage)

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

}