You can think of it as a recursive sector/quadrant system where sector 0 is the entire area and sector 0.1 is the upper left, 0.2 is upper right quadrant, 0.3 lower left and 0.4 lower right.... 0.1.1.1.4 would be the lower right of the upper left of the upper left of the upper left of the upper left of the entire screen.
this system of sub division can be used to bunch together a number of instances in order to lower the number of collision checks. For example, you would only check for collision on objects within a quadrant and object exists in. In the case where the instance has a radius, it wouljd exists in all the quadrants it overlaps into and so the collision would be done with that instance that ovelaps the quadrant with all others that also overlap the quadrant.
Here is a lame recursive system to visually demonstrate the quadtree subdivision. It is super slow because it's simply doing range checks to determine if instances overlap a sector defined by x1,y1,x2,y2, a rectangle, it does so in a recursive fasion until the subdivision of the area to check becomes too small.
/*
** Usage:
** point_line_distance(x1,y1,x2,y2,x3,y3,segment)
**
** Arguments:
** x1,y1 first end point of line
** x2,y2 second end point of line
** x3,y3 point to measuring from
** segment set to true to limit to the line segment
**
** Returns:
** the distance from the given point to a given line
**
** GMLscripts.com
*/
{
var x0,y0,x1,y1,x2,y2,x3,y3,dx,dy,t,segment;
x1 = argument0;
y1 = argument1;
x2 = argument2;
y2 = argument3;
x3 = argument4;
y3 = argument5;
segment = argument6;
dx = x2 - x1;
dy = y2 - y1;
if ((dx == 0) && (dy == 0)) {
x0 = x1;
y0 = y1;
}else{
t = ((x3 - x1) * dx + (y3 - y1) * dy) / (dx * dx + dy * dy);
if (segment) t = min(max(0,t),1);
x0 = x1 + t * dx;
y0 = y1 + t * dy;
}
return point_distance(x3,y3,x0,y0);
}
//RectIntersectCircle(l,t,r,b, px,py, radius)
if(point_line_distance(argument0,argument1,argument2,argument1,argument4,argument5,1) < argument6)
{
return 1;
}
if(point_line_distance(argument2,argument1,argument2,argument3,argument4,argument5,1) < argument6)
{
return 1;
}
if(point_line_distance(argument2,argument3,argument0,argument3,argument4,argument5,1) < argument6)
{
return 1;
}
if(point_line_distance(argument0,argument3,argument0,argument1,argument4,argument5,1) < argument6)
{
return 1;
}
return 0;
//QTAddItem(xs,ys,xe,ye)
var w; w = argument2 - argument0;
var h; h = argument3 - argument1;
var xx; xx = x-argument0;
var yy; yy = y-argument1;
var found; found = false;
ct+=1;
if(w>1 and h>1)
{
if(xx <= w)
if(yy <= h)
if(xx >= 0)
if(yy >= 0)
{
found = true;
}
if(!found)
found = RectIntersectCircle(argument0,argument1,argument2,argument3,x,y,m_Radius);
if(found)
{
//debug output
draw_rectangle(argument0,argument1,argument2,argument3,true);
QTAddItem(argument0,argument1,argument0+w/2,argument1+h/2);
QTAddItem(argument0+w/2,argument1,argument2,argument1+h/2);
QTAddItem(argument0,argument1+h/2,argument0+w/2,argument3);
QTAddItem(argument0+w/2,argument1+h/2,argument2,argument3);
}
}
return found;
usage In draw of test object
ct = 0; m_Radius = 10; x = mouse_x; y = mouse_y; QTAddItem(0,0,room_width,room_height); draw_circle(x,y,m_Radius,1); draw_text(0,0,string(ct));
I got a ct counter in there to mesure the number of recursion. it's about 500+
Clearly it's not a good method.
There must be a way to translate the x,y Cartesian value of the instance position into the recursive sub quadrant based position
AKA (x,y) (100,100) = quadtree 01114
var hash; hash = QTPosFromXY(x,y); QTPosToXY(hash); x = __x; y = __y;the resulting quadtree hash value could be sorted to figure out what instances neighbor each other.
There is the added difficulty of the function to add multiple quadtree hash values to the lists so instances with a radius would generate multiple keys...
