Quadtree Topic

5 replies to this topic

#1 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14389 posts
• Version:GM:Studio

Posted 29 July 2012 - 06:03 AM

I got interested in quad trees a while ago while exploring voxels which are usually optimized with a octree system. The method of a quadtree is a simple division of an area into 4 regions, then each region is divided by 4, subsequently until the region is small enough to stop the subdivision.

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...
• 0

#2 Zesterer

Zesterer

Professor of Articul

• GMC Member
• 1018 posts
• Version:GM8

Posted 29 July 2012 - 07:10 AM

Very interesting...

I too am working on a voxel-based engine (not a Minecraft clone!), and I have found the octree structure of storing data useful, but somewhat irrelevant sometimes. The time taken to decompress octree structures into a standard 3D array is very large, compared to other compression algorithms such as RLC. Despite octrees compressing to a (usually) higher level, the difference compared to an optimised RLC system and/or a system that 'predicts' data positions (due to the fact that the data is generally uniform) in memory space is slight, and the decompression is much faster.

However, this is a good article to show newcomers how one may use octrees/quadtrees in their games.

Zesterer
• 0

#3 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14389 posts
• Version:GM:Studio

Posted 29 July 2012 - 09:00 AM

Anything implemented here is for learning purpose, the most we can do in GM is experiment with he various uses. for now well just work a simple quadtree system for collision optimisation

Here I found a method for converting from xy to quadtree quadrant and back

```//quad = QTXYToQuadrant()
var maxlevel; maxlevel = 8;
var xx,yy,ww,hh;

xx = room_width/2;
yy = room_height/2;
ww = room_width/2;
hh = room_height/2;

var quads, q;
quad[0] = "0";
quad[1] = "1";
quad[2] = "2";
quad[3] = "3";

var ret; ret = "";

repeat(maxlevel)
{
q = quad[floor(point_direction(xx,yy,x,y)/90)];
ret+= q;
ww/=2;
hh/=2;
switch(q)
{
case "0": xx+=ww;yy-=hh; break;
case "1": xx-=ww;yy-=hh; break;
case "2": xx-=ww;yy+=hh; break;
case "3": xx+=ww;yy+=hh; break;
}
}
return ret;
```

```//QTQuadrantToXY(quad)
var maxlevel; maxlevel = 8;
var xx,yy,ww,hh;

xx = room_width/2;
yy = room_height/2;
ww = room_width/2;
hh = room_height/2;

var q;

var i; i = 1;
repeat(maxlevel)
{
q = string_char_at(argument0,i);
i+=1;
ww/=2;
hh/=2;
switch(q)
{
case "0": xx+=ww;yy-=hh; break;
case "1": xx-=ww;yy-=hh; break;
case "2": xx-=ww;yy+=hh; break;
case "3": xx+=ww;yy+=hh; break;
}

}
__x = xx;
__y = yy;
```

```//QTQuadrantDebugDraw(quad)
var maxlevel; maxlevel = 8;
var xx,yy,ww,hh;

xx = room_width/2;
yy = room_height/2;
ww = room_width/2;
hh = room_height/2;

var q;

var i; i = 1;
repeat(maxlevel)
{
q = string_char_at(argument0,i);
i+=1;
ww/=2;
hh/=2;

switch(q)
{
case "0": xx+=ww;yy-=hh; break;
case "1": xx-=ww;yy-=hh; break;
case "2": xx-=ww;yy+=hh; break;
case "3": xx+=ww;yy+=hh; break;
}
draw_rectangle(xx-ww,yy-hh,xx+ww,yy+hh,1);
}
```

usage, in draw
```m_Radius = 10;
x = mouse_x;
y = mouse_y;

quad = QTXYToQuadrant();
QTQuadrantToXY(quad);
x = __x;
y = __y;
draw_circle(x,y,m_Radius,1);
draw_text(0,0,quad);
QTQuadrantDebugDraw(quad)

```

maxlevel would eventually be passed to the scripts. The location is store in the form of a string, each byte with a valued from "0" to "3"

where 0 is upper right, 1 is upper left, 2 is lower right and 3 is lower left.

Not sure it's the optimal method to figure out each quadrant. and the use of a string is purely visual. we can convert that location code to a real number as long as the world is not too large, but this method should support any size world since a string is not limited to the number of digits...
• 0

#4 YellowAfterlife

YellowAfterlife

GMC Member

• Global Moderators
• 3492 posts
• Version:GM:Studio

Posted 29 July 2012 - 09:42 AM

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

A better way:
```// rectIntersectCircle(l,t,r,b, px,py, radius)
// . . . . . . . . . . 0 1 2 3 . 4 . 5 . . . 6
var nx, ny; // find nearest to circle coords x, y in rectangle area:
if (argument4 < argument0) nx = argument0 else if (px > argument2) nx = argument2 else nx = argument4
if (argument5 < argument1) ny = argument1 else if (py > argument3) ny = argument3 else ny = argument5
// subtract circle coordinates to have distance between nearest point in rectangle and circle center:
nx -= argument4
ny -= argument5
return nx * nx + ny * ny < argument6 * argument6```

• 0

#5 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14389 posts
• Version:GM:Studio

Posted 29 July 2012 - 10:08 PM

A better way:

```// rectIntersectCircle(l,t,r,b, px,py, radius)
// . . . . . . . . . . 0 1 2 3 . 4 . 5 . . . 6
var nx, ny; // find nearest to circle coords x, y in rectangle area:
if (argument4 < argument0) nx = argument0 else if (px > argument2) nx = argument2 else nx = argument4
if (argument5 < argument1) ny = argument1 else if (py > argument3) ny = argument3 else ny = argument5
// subtract circle coordinates to have distance between nearest point in rectangle and circle center:
nx -= argument4
ny -= argument5
return nx * nx + ny * ny < argument6 * argument6```

Thanks that improves it a lot. I'm working on the gmk and will release it when I can debug in a streamlined fashion. It's hard to tell with all the drawing if the improvements are substantial. This seems to have improved it a lot.
• 0

#6 icuurd12b42

icuurd12b42

Self Formed Sentient

• Global Moderators
• 14389 posts
• Version:GM:Studio

Posted 30 July 2012 - 03:21 AM

So here is a start... QuadTree2.gmk (GM8)
https://skydrive.live.com/redir?resid=FBA0B7E57CC98D0A!232

Right now I'm using instances as quadtree nodes, they have the benefit of lowering confusion and to debug draw. Later I will convert this to a GM data structure based system

The tree nodes will draw the level starting from max level all the way to 0... should be to opposite, 0 to max level, but it was easier that way.
If anyone can figure out why the quadtree main container is always visible please tell me.

It's rather slow at the moment so please inspect the code and see where improvements are possible.

Right now adding stuff in the tree, it uses a radius to add items in all the nodes an instance overlaps. It's slower than use just the coord.

Also the adding goes to the last level even if it would not need to, so instead of taking 1 cell at the level that fits the instance, that cell is subdivided to the end.
Fixed in version 3
https://skydrive.live.com/redir?resid=FBA0B7E57CC98D0A!233
• 0

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users