Author Topic: Quad Tree  (Read 2263 times)

MrTAToad

  • Guest
Quad Tree
« on: 2016-Feb-28 »
This code was written around the middle of last year, and was never posted here for some reason.

A Quad Tree is glorified tree list, and is designed to make rectangular collision detection easier/quicker than just going through a long list of coordinates.  It breaks down the screen into 4 parts, and then splits that into 4 parts and so on.

Code: GLBasic [Select]
// --------------------------------- //
// Project: QuadTree
// Start: Monday, August 17, 2015
// IDE Version: 14.003


// FREE-VERSION:
// Need Premium for Features:
// 3D Graphics
// Network Commands
// INLINE C/C+++ code

// SETCURRENTDIR("Media") // go to media files
TYPE tRect
        x%
        y%
        width%
        height%
ENDTYPE

//template<typename T>
//struct RECT {
//      T x,y,width,height;
//      };
INLINE
class QuadTree {
public:
        QuadTree(int pLevel,tRect pBounds)
        {
                level=pLevel;
                DIM(objects,0);
                bnds=pBounds;
                DIM(nodes,4);
                for (DGNat i=0; i<BOUNDS(nodes,0); i++) nodes(i)=NULL;

        }
        ~QuadTree()
        {
                Clear();
                DIM(nodes,0);
        }

        void Clear()
        {
                DIM(objects,0);
                for (DGNat i=0; i<BOUNDS(nodes,0); i++)
                {
                        if (nodes(i))
                        {
                                nodes(i)->Clear();
                                delete nodes(i);
                        }
                }
        }

        void Split()
        {
                int subWidth = bnds.width/2; //(int)(bounds.getWidth() / 2);
                int subHeight = bnds.height/2; // (int)(bounds.getHeight() / 2);
                int x = (int)bnds.x;
                int y = (int)bnds.y;
                tRect rect;

                DIM(nodes,4);
                rect.x=x + subWidth;    rect.y=y;       rect.width=subWidth;    rect.height=subHeight;
                nodes(0) = new QuadTree(level+1, rect);

                rect.x=x;                               rect.y=y;       rect.width=subWidth;    rect.height=subHeight;
                nodes(1) = new QuadTree(level+1, rect);

                rect.x=x;                               rect.y=y+subHeight;     rect.width=subWidth;    rect.height=subHeight;
                nodes(2) = new QuadTree(level+1, rect);

                rect.x=x + subWidth;    rect.y=y+subHeight;     rect.width=subWidth;    rect.height=subHeight;
                nodes(3) = new QuadTree(level+1, rect);
        }

        DGNat GetIndex(tRect pRect)
        {
                DGNat index = -1;
                DGInt verticalMidpoint = bnds.x+(bnds.width/2);
                DGInt horizontalMidpoint = bnds.y+(bnds.height/2);

                // Object can completely fit within the top quadrants
                DGNat topQuadrant = (pRect.x < horizontalMidpoint && pRect.y + pRect.width < horizontalMidpoint);
                // Object can completely fit within the bottom quadrants
                DGNat bottomQuadrant = (pRect.y > horizontalMidpoint);

                // Object can completely fit within the left quadrants
                if (pRect.x < verticalMidpoint && pRect.x + pRect.width < verticalMidpoint)
                {
                if (topQuadrant)
                {
                        index = 1;
                }
                else if (bottomQuadrant)
                {
                        index = 2;
                }
        }
        // Object can completely fit within the right quadrants
        else if (pRect.x > verticalMidpoint)
        {
                if (topQuadrant)
                {
                        index = 0;
                }
                else if (bottomQuadrant)
                {
                        index = 3;
                }
                }

                return index;
        }

        void Insert(tRect pRect)
        {
        DGNat index;

                if (nodes(0))
                {
                        index=GetIndex(pRect);

                        if (index!=-1)
                        {
                                nodes(index)->Insert(pRect);
                        }

                        return;
                }

                DIMPUSH(objects,pRect);

                if (BOUNDS(objects,0)>MAX_OBJECTS && level < MAX_LEVELS)
                {
                if (nodes(0)==NULL)
                {
                        Split();
                }

                DGNat i = 0;
                while (i < BOUNDS(objects,0))
                {
                        int index = GetIndex(objects(i));
                        if (index != -1)
                        {
                                nodes(index)->Insert(objects(i));
                                DIMDEL(objects,i);
                        }
                        else
                        {
                                i++;
                        }
                }
         }
        }

        DGNat Retrieve(DGArray<tRect > &returnObjects,tRect pRect)
        {
                DGNat index     =       GetIndex(pRect);
                if (index!=-1 && nodes(0)!=NULL)
                {
                        nodes(index)->Retrieve(returnObjects,pRect);
                }

                for (DGNat loop=0; loop<BOUNDS(objects,0); loop++)
                {
                        DIMPUSH(returnObjects,objects(loop));
                }

                return BOUNDS(returnObjects,0);
        }

private:
        const static DGNat MAX_OBJECTS  =       10;
        const static DGNat MAX_LEVELS   =       5;
        DGNat level;
        DGArray<tRect> objects;
        tRect bnds;
        DGArray<QuadTree *> nodes;
        };
ENDINLINE

FUNCTION CreateQuad%:x%,y%,width%,height%
INLINE
        class QuadTree *quad;
        tRect rect;

        DEBUG("CreateQuad\n------\n");
        rect.x=x;       rect.y=y;       rect.width=width;       rect.height=height;
        quad=new QuadTree(0,rect);
        return (DGNat) quad;
ENDINLINE
ENDFUNCTION

FUNCTION AddObject%:quad%,rect AS tRect,isFirst%
INLINE
        class QuadTree  *q;

                q=(QuadTree *) quad;
                if (q)
                {
                        if (isFirst)    q->Clear();
                        //rect.x=x;     rect.y=y;       rect.width=width;       rect.height=height;
                        q->Insert(rect);
                }
ENDINLINE
ENDFUNCTION

FUNCTION CheckCollision%:quad%,rect AS tRect,returnObjects[] AS tRect
INLINE
        class QuadTree  *q;
        //DGArray<tRect> returnObjects;

                q=(QuadTree *) quad;
                if (q)
                {
                        DIM(returnObjects,0);
                        //rect.x=x;     rect.y=y;       rect.width=width;       rect.height=height;
                        return q->Retrieve(returnObjects,rect);
                        //DEBUG(FORMAT_Str(4,4,BOUNDS(returnObjects,0)));
                        //DEBUG("\n");
                }

                return 0;
ENDINLINE
ENDFUNCTION

Code: GLBasic [Select]
// --------------------------------- //
// Project: QuadTree
// Start: Monday, August 17, 2015
// IDE Version: 14.003


// FREE-VERSION:
// Need Premium for Features:
// 3D Graphics
// Network Commands
// INLINE C/C+++ code

TYPE tObject
        rect AS tRect
ENDTYPE

LOCAL quad%
LOCAL obj[] AS tRect
LOCAL returnObj[] AS tRect

DIM obj[16]
FOR l%=0 TO BOUNDS(obj,0)-1
        obj[l%].x=RND(500)
        obj[l%].y=RND(500)
        obj[l%].width=RND(64)+1
        obj[l%].height=RND(64)+1
NEXT

quad%=CreateQuad(0,0,600,600)

FOR l%=0 TO BOUNDS(obj,0)-1
        IF l%=0
                AddObject(quad%,obj[l%],TRUE)
        ELSE
                AddObject(quad%,obj[l%],FALSE)
        ENDIF
NEXT

WHILE TRUE
        FOR l%=0 TO BOUNDS(obj,0)-1
                DRAWRECT obj[l%].x,obj[l%].y,obj[l%].width,obj[l%].height,IIF(l%=0,RGB(255,255,255),RGB(255,0,0))
        NEXT

        IF CheckCollision(quad%,obj[0],returnObj[])
                DEBUG "Here\n"
                FOR l%=0 TO BOUNDS(returnObj,0)-1;
                        IF returnObj[l%].x<>obj[0].x AND _
                                returnObj[l%].x<>obj[0].y AND _
                                returnObj[l%].x<>obj[0].width AND _
                                returnObj[l%].x<>obj[0].height
                                DRAWRECT returnObj[l%].x,returnObj[l%].y,returnObj[l%].width,returnObj[l%].height,RGB(255,0,255)
                        ENDIF
                NEXT
        ENDIF

        SHOWSCREEN
WEND
 
« Last Edit: 2016-Feb-28 by MrTAToad »

Offline Ian Price

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 4122
  • On the shoulders of giants.
    • View Profile
    • My Apps
Re: Quad Tree
« Reply #1 on: 2016-Feb-28 »
Perhaps you did post it and it got lost in the forum crash? It certainly sounds familiar.

Nice work anyhoo :)
I came. I saw. I played.

MrTAToad

  • Guest
Re: Quad Tree
« Reply #2 on: 2016-Feb-28 »
Yes, its quite possible!

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2511
    • View Profile
Re: Quad Tree
« Reply #3 on: 2016-Feb-28 »
Handy stuff, bookmarked.  :good:
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 4101
    • View Profile
    • Portfolio
Re: Quad Tree
« Reply #4 on: 2016-Mar-01 »
This looks very interesting, I usually do all my collision by coord, haven´t even tried box collision yet.
Will check it out later in full.

edit: as with Ian, I think I have seen this before too.

Offline Schranz0r

  • Premium User :)
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 4966
  • O Rly?
    • View Profile
Re: Quad Tree
« Reply #5 on: 2016-Mar-01 »
Hey, good work! :)
I <3 DGArray's :D

PC:
AMD RYzen 7 1700 @3.9Ghz, 16GB HyperX Fury 2666Mhz Ram, ASUS ROG GTX 1060 STRIX 6GB, Windows 10 Pro 64Bit, MSi Tomahawk B350 Mainboard

MrTAToad

  • Guest
Re: Quad Tree
« Reply #6 on: 2016-Mar-02 »
Glad you like it!