Quad Tree

Previous topic - Next topic

MrTAToad

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

Ian Price

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

Yes, its quite possible!

bigsofty

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)

erico

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.

Schranz0r

Hey, good work! :)
I <3 DGArray's :D

PC:
AMD Ryzen 7 3800X 16@4.5GHz, 16GB Corsair Vengeance LPX DDR4-3200 RAM, ASUS Dual GeForce RTX™ 3060 OC Edition 12GB GDDR6, Windows 11 Pro 64Bit, MSi Tomahawk B350 Mainboard

MrTAToad

Glad you like it!