QuadTree for a 2D particle System

326 Views Asked by At

I have programmed a Quadtree for detection of collisions between particles in my 2D game. The code works but it is not very fast. Especially the retrieve() function. Being a beginner in c ++, if you have tips to optimize my code, it's will be nice.

QuadTree.h

class QuadTree{
public:
    QuadTree();
    QuadTree(int level, int posX, int posY, int width, int height);
    virtual ~QuadTree();

    void clearQuadTree();
    void split();
    void insertObject(Particle particle, int indexParticule, Particle *particles);
    int getIndex(Particle particule);
    void retrieve(Particle particle, std::vector<int>& particles);
    void displayQuad(Window *window, Camera *camera);

    const static int MAX_OBJECTS = 10;
    const static int MAX_LEVELS = 30;

    std::vector<int> mObjects;
    std::vector<QuadTree> mNodes;
    int mLevel;

    // bounds
    int mPosX;
    int mPosY;
    int mWidth;
    int mHeight;
};

QuadTree.cpp

void QuadTree::clearQuadTree(){
    mObjects.clear();
    while(!mNodes.empty())
        mNodes.pop_back();
    for(int i=0;i<mNodes.size();i++)
        mNodes[i].clearQuadTree();}

void QuadTree::split(){
    int subWidth = mWidth / 2;
    int subHeight = mHeight / 2;
    mNodes.push_back(QuadTree(mLevel+1, mPosX + subWidth, mPosY, subWidth, subHeight));
    mNodes.push_back(QuadTree(mLevel+1, mPosX, mPosY, subWidth, subHeight));
    mNodes.push_back(QuadTree(mLevel+1, mPosX, mPosY + subHeight, subWidth, subHeight));
    mNodes.push_back(QuadTree(mLevel+1, mPosX + subWidth, mPosY + subHeight, subWidth, subHeight));}

void QuadTree::insertObject(Particle particle, int indexParticule, Particle *particles){
    if(!mNodes.empty()){
        int index = getIndex(particle);

        if(index != -1) {
            mNodes[index].insertObject(particle, indexParticule, particles);
            return;
        }
    }

    mObjects.push_back(indexParticule);

    if(mObjects.size() > MAX_OBJECTS && mLevel < MAX_LEVELS) {
        if(mNodes.empty())
            split();

        // moves object in new sub-nodes
        std::vector<int>::iterator i = mObjects.begin();
        while(i != mObjects.end()){
            int index = getIndex(particles[*i]);
            if (index != -1){
                mNodes[index].insertObject(particles[*i], *i, particles);
                mObjects.erase(i);
            }
            else
                i++;
        }

    }
}

void QuadTree::retrieve(Particle particle, std::vector<int>& particles){

    // add objects in current node
    for(int i=0; i<mObjects.size(); i++)
        particles.push_back(mObjects[i]);


    // add objects in sub-nodes
    int index = getIndex(particle);
    if(index == -1 )
        for(int i=0; i<mNodes.size(); i++)
            mNodes[i].retrieve(particle, particles);
    else if(!mNodes.empty())
        mNodes[index].retrieve(particle, particles);
}

With that code i can only reach around 300 particles in my 2d game.

Edit:

int QuadTree::getIndex(Particle particle){
    int index = -1;
    int verticalMidpoint = mPosX + mWidth/2;
    int horizontalMidpoint = mPosY + mHeight/2;

    // Object can completely fit within the top quadrants
    bool topQuadrant = (particle.mPositionY-(particle.RADIUS_PARTICLE)>horizontalMidpoint);
    // Object can completely fit within the bottom quadrants
    bool bottomQuadrant = (particle.mPositionY+(particle.RADIUS_PARTICLE)<horizontalMidpoint);

    // Object can completely fit within the left quadrants
    if(particle.mPositionX + (particle.RADIUS_PARTICLE)<verticalMidpoint){
        if(topQuadrant)
            index = 2;
        else if(bottomQuadrant)
            index = 1;
    }
    // Object can completely fit within the right quadrants
    else if(particle.mPositionX - (particle.RADIUS_PARTICLE)>verticalMidpoint){
        if (topQuadrant)
            index = 3;
        else if (bottomQuadrant)
            index = 0;
    }

    return index;}
0

There are 0 best solutions below