四叉树更新对象失败

Question

实现四叉树时我遇到了问题 当Quadtree中的对象移动时，我们必须在Quadtree中更新该对象的位置。我尝试自己编写更新函数，但它不起作用。*（void UpdatePosition（QuadNode root，bool＆OK）） 我的四叉树课程如下：

class QuadNode
    {
    public:
        vector<Object*> listObj;

        RECT*       _rect;
        QuadNode*   LT,*RT,*LB,*RB;
        QuadNode()
        {
            _rect=NULL;
            LT=RT=LB=RB=NULL;
        }
        QuadNode(int left,int top,int width,int height)
        {
            _rect=new RECT();
            _rect->left=left;
            _rect->top=top;
            _rect->right=_rect->left+width;
            _rect->bottom=_rect->top+height;
            LT=RT=LB=RB=NULL;
        }
    };

    class QuadTree
    {
    public:
        bool CheckRECTInRECT(RECT r,RECT rect);
        bool CheckPointInRECT(int x,int y,RECT rect);
        void GetObjInRec(QuadNode* root,RECT Screen,vector<Object*> &result);

        QuadNode*   _pRoot;
        int         _mapWidth;
        int         _mapHeight;
        int         _count;

        QuadTree(int w,int h);
        ~QuadTree(void);

        void Add(QuadNode *root,Object *Ob);
        void OutPutTree(QuadNode *root);
        QuadNode* getTreeRoot(){ return _pRoot; };
        //Chi in nhung cai nam tren main hinh hien tai
        void DrawObjects(RECT Screen);
        Object* CheckCollision(QuadNode *root,RECT r,int Seq);
        void CheckCollision(QuadNode *root,RECT r,vector<Object*>&result);
        bool IsOnObject(RECT *rect,int Seq);//duoi chan object la object khac hay la khoang trong
        void UpdatePosition(QuadNode *root,bool& OK);
        void GetAllObj(QuadNode *root,vector<Object*> &result);
        void RemoveAll(QuadNode *root);
    };

和：

QuadTree::QuadTree(int w,int h)
    {
        _mapWidth=w;
        _mapHeight=h;
        _pRoot=new QuadNode(0,0,_mapWidth,_mapHeight);
        //_count=0;
    }
    void QuadTree::Add(QuadNode *root,Object *Ob)
    {   
        if(root!=NULL)
        {
            //0: Add ....1: Left_Top..... 2: Right_Top....... 3: Left_Bottom...... 4: Right_Bottom
            int result=0;//add here

            int objWidth    =   Ob->getObjectRect().right - Ob->getObjectRect().left;
            int objHeight   =   Ob->getObjectRect().bottom - Ob->getObjectRect().top;

            int rectWidth   =   root->_rect->right - root->_rect->left; 
            int rectHeight  =   root->_rect->bottom - root->_rect->top;

            int rectWidthNew=   (root->_rect->right + root->_rect->left)/2; //divide RECT root to quad RECT
            int rectHeightNew=  (root->_rect->bottom + root->_rect->top)/2;

            if((objWidth*objHeight > rectWidth*rectHeight/4)/*kiem tra dien tich co lon hon 1/4 dien tich roof ko*/ 
                || (rectWidthNew > Ob->getObjectRect().left && rectWidthNew <= Ob->getObjectRect().right)||
                (rectHeightNew > Ob->getObjectRect().top && rectHeightNew <= Ob->getObjectRect().bottom))
                result=0;//Kiem tra xem objet nam o hon 1/4 cua root thi tra ve khong
            else
            {
                if(Ob->getObjectRect().left >= root->_rect->left &&
                    Ob->getObjectRect().left < rectWidthNew &&
                    Ob->getObjectRect().top >= root->_rect->top &&
                    Ob->getObjectRect().top < rectHeightNew)//Left_Top
                    result =1;
                else 
                    if(Ob->getObjectRect().left < root->_rect->right &&
                        Ob->getObjectRect().left >= rectWidthNew &&
                        Ob->getObjectRect().top >= root->_rect->top &&
                        Ob->getObjectRect().top < rectHeightNew)//Right_Top
                        result =2;
                    else 
                        if(Ob->getObjectRect().left >= root->_rect->left &&
                            Ob->getObjectRect().left < rectWidthNew &&
                            Ob->getObjectRect().top >= rectHeightNew &&
                            Ob->getObjectRect().top < root->_rect->bottom)//Left_Bottom
                            result=3;
                        else//Right_Bottom
                            result=4;
            }

            if(result==0)//Add here
            {
                root->listObj.push_back(Ob);
                _count++; 
            }
            else
            {
                if(rectWidth/2 > LIM_W_H && rectHeight/2 > LIM_W_H)
                {
                    switch(result)
                    {
                    case 1://Left_Top
                        if(root->LT==NULL)
                            root->LT=new QuadNode(root->_rect->left,root->_rect->top,rectWidth/2,rectHeight/2);
                        Add(root->LT,Ob);
                        break;
                    case 2://Right_Top
                        if(root->RT==NULL)
                            root->RT=new QuadNode(rectWidthNew,root->_rect->top,rectWidth/2,rectHeight/2);
                        Add(root->RT,Ob);
                        break;
                    case 3://Left_Bottom
                        if(root->LB==NULL)
                            root->LB=new QuadNode(root->_rect->left,rectHeightNew,rectWidth/2,rectHeight/2);
                        Add(root->LB,Ob);
                        break;
                    case 4://Right_Bottom
                        if(root->RB==NULL)
                            root->RB=new QuadNode(rectWidthNew,rectHeightNew,rectWidth/2,rectHeight/2);
                        Add(root->RB,Ob);
                        break;
                    }
                }
            }
        }
    }

    bool QuadTree::CheckPointInRECT(int x,int y,RECT rect)
    {
        if(x >= rect.left && x <= rect.right && y >= rect.top && y <= rect.bottom)
            return true;
        return false;
    }

    bool QuadTree::CheckRECTInRECT(RECT r,RECT rect)
    {
        if(CheckPointInRECT(r.left,r.top,rect)
            ||CheckPointInRECT(r.right,r.top,rect)
            ||CheckPointInRECT(r.left,r.bottom,rect)
            ||CheckPointInRECT(r.right,r.bottom,rect)
            ||(rect.top<=r.top&&rect.bottom>=r.bottom&&r.left<=rect.left&&r.right>=rect.right))
        {
            return true;
        }
        return false;
    }
    void QuadTree::GetObjInRec(QuadNode* root,RECT Screen,vector<Object*> &result)
    {
        for(int i=0;i<root->listObj.size();i++)
            if(CheckRECTInRECT(root->listObj[i]->getObjectRect(),Screen)||CheckRECTInRECT(Screen,root->listObj[i]->getObjectRect()))//active items on camera
            {
                result.push_back(root->listObj[i]);
            }
            if(root->LT!=NULL&&(CheckRECTInRECT(*root->LT->_rect,Screen)||CheckRECTInRECT(Screen,*root->LT->_rect)))
                GetObjInRec(root->LT,Screen,result);
            if(root->RT!=NULL&&(CheckRECTInRECT(*root->RT->_rect,Screen)||CheckRECTInRECT(Screen,*root->RT->_rect)))
                GetObjInRec(root->RT,Screen,result);
            if(root->LB!=NULL&&(CheckRECTInRECT(*root->LB->_rect,Screen)||CheckRECTInRECT(Screen,*root->LB->_rect)))
                GetObjInRec(root->LB,Screen,result);
            if(root->RB!=NULL&&(CheckRECTInRECT(*root->RB->_rect,Screen)||CheckRECTInRECT(Screen,*root->RB->_rect)))
                GetObjInRec(root->RB,Screen,result);
    }
    void QuadTree::DrawObjects(RECT Screen)
    {
        vector<Object*> total;
        this->GetAllObj(_pRoot,total);

        vector<Object*> result;
        //vector<Object*> allObjet;
        //GetAllObj(_pRoot,allObjet);
        GetObjInRec(_pRoot,Screen,result);
        for (int i=0; i<result.size();i++)
        {
            result[i]->draw(Screen);
        }
    }

//this function doesn't work
    void QuadTree::UpdatePosition(QuadNode *root,bool& OK)
    {
        //vector<Object*> okconde;
        //GetAllObj(_pRoot,okconde);

        if (root->LT == NULL && root->LB==NULL && root->RB==NULL && root->RT==NULL)
        {
            return;
        }
        vector<Object*>::iterator begin, end;
        begin=root->listObj.begin();
        end=root->listObj.end();

        while(begin!=end)
        {
            Object *Ob= *begin;

            if(Ob->getObjectType()!=1)
// get type of Object (if objectType !=1 so they are player or enemey which can move)
            {   


                if(Ob->IsMoving())
// these statement never reach- I have debuged.
                {
                    root->listObj.erase(begin);
                    this->Add(_pRoot,Ob);
                    OK=true;
                }
            }
            else
                begin++;
        }
        if(root->LT!=NULL)
            UpdatePosition(root->LT,OK);
        if(root->RT!=NULL)
            UpdatePosition(root->RT,OK);
        if(root->LB!=NULL)
            UpdatePosition(root->LB,OK);
        if(root->RB!=NULL)
            UpdatePosition(root->RB,OK);
    }

    QuadTree::~QuadTree(void)
    {
    }

    void QuadTree::GetAllObj(QuadNode *root,vector<Object*> &result)
    {

        for(int i=0;i<root->listObj.size();i++)
            result.push_back(root->listObj[i]);

        if(root->LT!=NULL)
            GetAllObj(root->LT,result);

        if(root->LB!=NULL)
            GetAllObj(root->LB,result);

        if(root->RT!=NULL)
            GetAllObj(root->RT,result);

        if(root->RB!=NULL)
            GetAllObj(root->RB,result);
    }

    void QuadTree::RemoveAll(QuadNode *root)
    {
        if (root!=NULL)
        {
            root->listObj.clear();
        }
        if (root->LB!=NULL)
            RemoveAll(root->LB);
        if (root->LT!=NULL)
            RemoveAll(root->LB);
        if (root->RB!=NULL)
            RemoveAll(root->LB);
        if (root->RT!=NULL)
            RemoveAll(root->LB);
    }

Answer 1

这可能不是一个确切的答案，但我在这里有一个松散的四叉树（它比四叉树表现更好但仍然具有相同的结构）我写的。

    pastebin.com/e6yCLzNm
    Quadtree.h
    pastebin.com/REKBQmte
    Quadtree.cpp

这可能对你有帮助。