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.
// --------------------------------- //
// 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
// --------------------------------- //
// 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
Perhaps you did post it and it got lost in the forum crash? It certainly sounds familiar.
Nice work anyhoo :)
Yes, its quite possible!
Handy stuff, bookmarked. :good:
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.
Hey, good work! :)
Glad you like it!