Quad Tree

[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 Expand

// --------------------------------- //
// 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 Expand

// --------------------------------- //
// 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

[MrTAToad]

Yes, its quite possible!

[bigsofty]

Handy stuff, bookmarked. 

[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!

[MrTAToad]

Glad you like it!