• Guest
« 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]
// --------------------------------- //
// Start: Monday, August 17, 2015
// IDE Version: 14.003

// FREE-VERSION:
// 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
public:
{
level=pLevel;
DIM(objects,0);
bnds=pBounds;
DIM(nodes,4);
for (DGNat i=0; i<BOUNDS(nodes,0); i++) nodes(i)=NULL;

}
{
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;

rect.x=x;                               rect.y=y;       rect.width=subWidth;    rect.height=subHeight;

rect.x=x;                               rect.y=y+subHeight;     rect.width=subWidth;    rect.height=subHeight;

rect.x=x + subWidth;    rect.y=y+subHeight;     rect.width=subWidth;    rect.height=subHeight;
}

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)
{
{
index = 1;
}
{
index = 2;
}
}
// Object can completely fit within the right quadrants
else if (pRect.x > verticalMidpoint)
{
{
index = 0;
}
{
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;
};
ENDINLINE

INLINE
tRect rect;

rect.x=x;       rect.y=y;       rect.width=width;       rect.height=height;
ENDINLINE
ENDFUNCTION

INLINE

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
//DGArray<tRect> returnObjects;

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]
// --------------------------------- //
// Start: Monday, August 17, 2015
// IDE Version: 14.003

// FREE-VERSION:
// 3D Graphics
// Network Commands
// INLINE C/C+++ code

TYPE tObject
rect AS tRect
ENDTYPE

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

FOR l%=0 TO BOUNDS(obj,0)-1
IF l%=0
ELSE
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

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 »

#### Ian Price

• Prof. Inline
• Posts: 4136
• On the shoulders of giants.
« 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.

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

#### bigsofty

• Community Developer
• Prof. Inline
• Posts: 2569
« Reply #3 on: 2016-Feb-28 »
Handy stuff, bookmarked.
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

• Community Developer
• Prof. Inline
• Posts: 4152
« 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.

#### Schranz0r

• Prof. Inline
• Posts: 5000
• O Rly?
« Reply #5 on: 2016-Mar-01 »
Hey, good work!
I DGArray's

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