rigz.collision:

Collision Module with quadtrees for spatial partitioning of boundaries

This modules provides a way to check for collisions between boxes, circles, lines and polygons (referred to as boundaries throughout to documentation). The option of using a quadtree is also there to speed up collision checking between large numbers of objects.

Thanks to matibee, Leadwerks and Oddball from the Blitzmax forums, plus the authors of these sites http://en.wikipedia.org/wiki/Quadtree, http://www.kyleschouviller.com/wsuxna/quadtree-source-included/, http://www.heroicvirtuecreations.com/QuadTree.html, http://www.metanetsoftware.com/technique/tutorialA.html and http://www.codeproject.com/KB/GDI-plus/PolygonCollision.aspx where I found lots of useful info!

The aim of this module was to try as much as possible to combine ease of use with performance. In terms of performance it uses a collision checking technique called separating axis theorem, which is quite a common and fast approach to collision detection, as well as providing an easy way to find out about each collision that happens in order to calculate things such as overlap prevention, and rebound vector calculation.

For an example as to how easy the module is to use, to calculate a collision between 2 objects, you can simply use CheckCollisions like so:

local result:tlCollisionResult=CheckCollisions(SourceObject, TargetObject)

Where source and target objects can be either a tlBox, tlCircle, tlLine or tlPolygon. Once the check is done the results of the collision are returned in a tlCollisionResult where you can find out a number of things about the nature of the collision. To prevent 2 objects from overlapping you can simply do:

PreventOverlap(result)

and if a collision occurred then the 2 objects will be separated. See PreventOverlap for more info and an example

Quadtrees are also simple to use, see tlQuadtree for more info and an example.

All boundaries can be placed on one or more layers (up to 32) to help you organise collisions more easily. You can use the constants tlLAYER_1, tlLAYER_2.. etc. up to 32 or tlLAYER_ALL to place a boundary on all layers. To set a layer you can either do it on creation of a boundary ie., with CreateBox, or you can use SetBoundaryLayer. Use GetBoundaryLayer to find out the layer of a boudnary.

It's might be worth noting, that whilst function wrappers for most types have been created for extra convienience, you can still access the those methods directly in a more OO approach if you wish. Peruse the documentation for the specific methods etc.

Functions Summary

AddBoundaryToQuadtree	Add a new bounding box to the Quadtree.
CheckCollision	Check for a collision between 2 Boundaries.
CheckRayCollision	See if a ray collides with a boundary.
CreateBox	Create a new tlBox.
CreateCircle	Create a tlLine.
CreateLine	Create a tlCircle.
CreatePolygon	Create a tlPolygon.
CreateQuadtree	Create a new tlQuadTree.
GetBoundaryData	Get the data assigned to a boundary.
GetBoundaryLayer	Get the collision layer that this boundary is on.
GetQuad	Get the quad a vertex lies within.
GetReboundVector	Get the rebound vector.
IntervalDistance	Find the amount of overlap between 2 1D lines.
LinesCross	Do a Line to Line collision check.
LinesCrossAtPoint	Do a Line to Line collision check and return the point of intersection.
LineToCircle	Do a Line to Circle collision check.
MoveBoundary	Move a Boundary by a given amount.
NearestPointToCircle	Return the nearest point on a line to the center of a circle.
PointInside	Find out if a point is within a boundary.
PreventOverlap	Prevent boundaries from overlapping, based on a tlCollisionResult.
QueryQuadtreeArea	Query a Quadtree to find objects with an area.
QueryQuadtreeBox	Query a quadtree to find objects within a tlBox.
QueryQuadtreeCircle	Query a quadtree to find objects within a tlCircle.
QueryQuadtreeEdge	Query a quadtree with a line edge.
QueryQuadtreeLine	Query a quadtree with a tlLine.
QueryQuadtreeRange	Query a quadtree to find objects within a certain radius.
QueryQuadtreeRay	Query a quadtree with a Ray.
RemoveBoundaryFromQuadTree	Remove a boundary from the quadtree.
RotatePolygon	Rotate a tlPolygon.
RunQuadtreeMaintenance	Perform some house keeping on a quadtree.
SameLayer	Find out if 2 boundaries are on the same collision layers.
ScaleBoundary	Set the scale of a Boundary.
SetBoundaryData	Assign an object to a boundary.
SetBoundaryLayer	Set the collision layer that this boundary is on.
SetBoundaryPosition	Set the position of a Boundary.
SetBoundaryVelocity	Set the velocity of a boundary.
SetPolygonAngle	Set the angle of a tlPolygon.
UpdateBoundaryPosition	Update the position of the boundary.
WithinFieldOfView	Check if a point is with a field of view.

Types Summary

tlBox	Type for handling Axis Aligned Bounding Boxes.
tlCircle	tlCircle for circular boundaries for collision checking.
tlCollisionResult	Type to store the results of collisions.
tlLine	tlLine for line collisions.
tlPolygon	tlPolygon for convex polygon collisions.
tlQuadTree	Quadtree type for managing a quadtree.
tlQuadTreeNode	tlQuadTreeNode type for containing objects within the QuadTree.

Functions

Function AddBoundaryToQuadtree:Int(quadtree:tlQuadTree, Box:tlBox)
Returns	False if the box doesn't overlap the quadtree, otherwise True.
Description	Add a new bounding box to the Quadtree.
Information	A quadtree isn't much use without any objects. Use this to add a tlBox to the quadtree. If the bounding box does not overlap the quadtree then null is returned.

Function CheckCollision:tlCollisionResult(Source:tlBox, Target:tlBox)
Returns	tlCollisionResult.
Description	Check for a collision between 2 Boundaries.
Information	You can use this function to check for collisions between any type of boundary: tlBox, tlCircle, tlLine and tlPolygon. The tlCollisionResult can then be used to determine what you want to do if a collision happened (or will happen). See PreventOverlap to make boundaries block or push each other.
Example	SuperStrict Import rigz.collision Graphics 800, 600 'create a polygon to collide with Local verts:Float[] = [0.0, 0.0, -150.0, 100.0, 50.0, 150.0, 185.0, 100.0, 300.0, 0.0] 'verts = [- 10.0, -10.0, 10.0, -10.0, 10.0, 10.0, -10.0, 10.0] Local poly:tlPolygon = CreatePolygon(400, 200, verts) 'create a box to move about Local box:tlBox = CreateBox(100, 100, 20, 20) 'a local collision result to store the result of the collision test Local result:tlCollisionResult = New tlCollisionResult 'some velocity vectors to move the box about Local VelVector:tlVector2 = CreateVector2(0, 0) Local VelMatrix:tlMatrix2 = CreateMatrix2() Local Direction:Float Local speed:Float = 4 While Not KeyDown(KEY_ESCAPE) Cls 'rotate the polygon by 1 degree every frame poly.Rotate(1) 'some basic movement controls for the box If KeyDown(KEY_UP) direction = 0 If KeyDown(KEY_RIGHT) direction = 90 If KeyDown(KEY_DOWN) direction = 180 If KeyDown(KEY_LEFT) direction = 270 If KeyDown(KEY_RIGHT) And KeyDown(KEY_DOWN) direction = 135 If KeyDown(KEY_DOWN) And KeyDown(KEY_LEFT) direction = 225 If KeyDown(KEY_UP) And KeyDown(KEY_RIGHT) direction = 45 If KeyDown(KEY_LEFT) And KeyDown(KEY_UP) direction = 315 If KeyDown(KEY_UP) Or KeyDown(KEY_DOWN) Or KeyDown(KEY_LEFT) Or KeyDown(KEY_RIGHT) velvector.SetPosition(0, -speed) Else velvector.SetPosition(0, 0) End If velmatrix.set(Cos(direction) , Sin(direction) , -Sin(direction) , Cos(direction)) velvector = velmatrix.transformvector(velvector).Unit() 'set the box velocity so that the collision check can see whether the 2 objects will collide 'the next frame. You don't have to do this, but it makes for more accurate collisions box.velocity = velvector.Scale(speed) 'check for a collision with the poly result = CheckCollision(box, poly) 'prevent the box from overlapping the poly PreventOverlap(result) 'move the box. Important to do this after the collision check, but only if you're setting 'the box velicity. box.Move(box.velocity.x, box.velocity.y) box.draw() poly.draw() Flip Wend

Function CheckRayCollision:tlCollisionResult(Target:tlBox, px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0)
Returns	tlCollisionResult with the results of the collision.
Description	See if a ray collides with a boundary.
Information	You can use this to test for a collision with a ray and any type of boundary: tlBox, tlCircle, tlLine and tlPolygon. Pass the origin of the ray with px and py, and set the direction of the raycast with dx and dy vector. dx and dy will be normalised and extended infinitely if maxdistance equals 0 (default), otherwise set maxdistance to how ever far you want the ray to extend to before stopping. If the ray starts inside the poly then result.rayorigininside will be set to true. You can find the angle of reflection to bounce the ray using GetReboundVector.
Example	SuperStrict Import rigz.collision Graphics 800, 600 'create some shapes for collisions Local verts:Float[] = [- 100.0, 0.0, -150.0, 100.0, 50.0, 150.0, 185.0, 100.0, 300.0, 0.0] Local poly:tlPolygon = New tlPolygon.CreatePoly(400, 200, verts) Local line:tlLine = CreateLine(200, 500, 800, 100) Local box:tlBox = CreateBox(400, 300, 100, 100) Local circle:tlCircle = CreateCircle(400, 300, 40) Local ray:tlVector2 = CreateVector2(0, 0) Local result:tlCollisionResult = New tlCollisionResult Local point:tlVector2 = CreateVector2(0, 0) Local shape:Int While Not KeyDown(KEY_ESCAPE) Cls 'set the ray vector based on the point->mouse vector If MouseDown(1) point.SetPosition(MouseX(), MouseY()) ray.SetPosition(MouseX() - point.x, MouseY() - point.y) 'normalise the ray so we can draw the laser a fixed length a bit more easily ray.Normalise() 'iterate through shapes if space is pressed If KeyHit(KEY_SPACE) shape:+1 If shape > 3 shape = 0 End If SetColor 255, 255, 255 DrawText "Press space to change shape", 10, 10 DrawText "Click and drag to move the laser, mouse pointer set the laser direction", 10, 20 'do a ray collision checked on the selected shape and store the result Select shape Case 0 box.draw() result = CheckRayCollision(box, point.x, point.y, ray.x, ray.y) Case 1 line.Rotate(1) line.draw() result = CheckRayCollision(line, point.x, point.y, ray.x, ray.y) Case 2 circle.draw() result = CheckRayCollision(circle, point.x, point.y, ray.x, ray.y) Case 3 poly.Rotate(1) poly.draw() result = CheckRayCollision(poly, point.x, point.y, ray.x, ray.y) End Select SetColor 255, 0, 0 DrawRect point.x - 5, point.y - 5, 10, 10 'if the result shows an intersection and it wasn't insise the shape If result.GetRayIntersection() And Not result.GetRayOriginInside() 'draw the ray upto the intersection point DrawLine point.x, point.y, result.rayintersection.x, result.rayintersection.y DrawOval result.rayintersection.x - 4, result.rayintersection.y - 4, 8, 8 'find the rebound vector Local rebound:tlVector2 = GetReboundVector(result, ray) 'draw the rebounded ray DrawLine result.rayintersection.x, result.rayintersection.y, .. result.rayintersection.x + rebound.x * 500, result.rayintersection.y + rebound.y * 500 ElseIf result.rayorigininside DrawText "Ray starts inside object!", 10, 30 Else 'no intersection, draw a line for the ray DrawLine point.x, point.y, point.x + ray.x * 1000, point.y + ray.y * 1000 EndIf Flip Wend

Function CreateBox:tlBox(x:Float, y:Float, w:Float, h:Float, layer:Int = tlLAYER_1)
Returns	New tlBox.
Description	Create a new tlBox.
Information	Creates a new Bounding box that you can use for collision checking and adding to a tlQuadTree. Use layer to specify a particular layer to place the box on so that you can more easily organise your collisions. You use tlLAYER_1, tlLAYER_2..and so on up to tlLAYER_32, or tlLAYER_ALL to place the boundary on all layers.

Function CreateCircle:tlCircle(x:Float, y:Float, radius:Float, layer:Int = tlLAYER_1)
Returns	New tlLine.
Description	Create a tlLine.
Information	Create a new tlLine at the given coordinates with the given radius. The coordinates will represent the center of the circle. Use layer to specify a particular layer to place the box on so that you can more easily organise your collisions. You use tlLAYER_1, tlLAYER_2..and so on up to tlLAYER_32, or tlLAYER_ALL to place the boundary on all layers.

Function CreateLine:tlLine(x1:Float, y1:Float, x2:Float, y2:Float, layer:Int = tlLAYER_1)
Returns	New tlCircle.
Description	Create a tlCircle.
Information	Create a new tlLine at the coordinates given, x1 and y1 being the start of the line and x2 and y2 being the end. The will placed exactly according to the coordinates you give, but it's worth bearing in mind that the handle of the line will be at the center point along the line. Therefore the world coordinates will be set to half way point along the line. Use layer to specify a particular layer to place the box on so that you can more easily organise your collisions. You use tlLAYER_1, tlLAYER_2..and so on up to tlLAYER_32, or tlLAYER_ALL to place the boundary on all layers.

Function CreatePolygon:tlPolygon(x:Float, y:Float, verts:Float[], layer:Int = tlLAYER_1)
Returns	New tlPolygon, or Null if verts[] contained the wrong amount.
Description	Create a tlPolygon.
Information	Create a new tlPolygon at the given coordinates with the given array of vertices. The coordinates will represent the center of the polygon which is automatically calculated. The array must contain more then 5 values (2 per vertex) and be an even number or null will be returned. The coordinates of the vertices in the array are arranged like so: [x,y,x,y,x,y .. etc]. Use layer to specify a particular layer to place the box on so that you can more easily organise your collisions. You use tlLAYER_1, tlLAYER_2..and so on up to tlLAYER_32, or tlLAYER_ALL to place the boundary on all layers.

Function CreateQuadtree:tlQuadtree(x:Float, y:Float, w:Float, h:Float, maxlevels:Int = 4, maxpernode:Int = 4)
Returns	A new tlQuadtree.
Description	Create a new tlQuadTree.
Information	Creates a new quad tree with the coordinates and dimensions given. Maxlevels determines how many times the quadtree can be sub divided. A quadtreenode is only subdivided when a certain amount of objects have been added, which is set by passing maxpernode. There's no optimum values for these, it largely depends on your specific needs, so you will probably do well to experiment.

Function GetBoundaryData:Object(Boundary:tlBox, Data:Object)
Description	Get the data assigned to a boundary.
Information	Use this to retrieve the custom data you have assign to a boundary.

Function GetBoundaryLayer:Int(Boundary:tlBox)
Description	Get the collision layer that this boundary is on.

Function GetQuad:Int(axis_x:Float, axis_y:Float, vert_x:Float, vert_y:Float)
Description	Get the quad a vertex lies within.
Information	This will return the quad a vertex lies within according to the x and y axis you pass it.

Function GetReboundVector:tlVector2(Result:tlCollisionResult, v:tlVector2, friction:Float = 0, bounce:Float = 1)
Returns	New tlVector2 with the resulting rebound vector, or v, if there was nothing to rebound.
Description	Get the rebound vector.
Information	When an object collides with a surface you may want to know a resulting vector based on bounce and friction. So you can call this and pass the velocity vector of the incoming object, and the amount of bounce and friction to have, where a bounce value of 1 and a friction value of 0 will result in a perfect bounce.
Example	SuperStrict Import rigz.collision Graphics 800, 600 Local qtree:tlQuadTree = CreateQuadtree(0, 0, GraphicsWidth(), GraphicsHeight()) 'Add some obstacles to the quadtree AddBoundaryToQuadtree(qtree, CreateBox(10, 0, GraphicsWidth() - 20, 10)) AddBoundaryToQuadtree(qtree, CreateBox(10, GraphicsHeight() - 10, GraphicsWidth() - 20, 10)) AddBoundaryToQuadtree(qtree, CreateBox(0, 10, 10, GraphicsHeight() - 20)) AddBoundaryToQuadtree(qtree, CreateBox(GraphicsWidth() - 10, 10, 10, GraphicsHeight() - 20)) Local verts:Float[] = [- 50.0, -50.0, -70.0, 0.0, -50.0, 50.0, 50.0, 50.0, 100.0, 0.0, 50.0, -50.0] AddBoundaryToQuadtree(qtree, CreatePolygon(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), verts)) AddBoundaryToQuadtree(qtree, CreateCircle(500, 400, 100)) AddBoundaryToQuadtree(qtree, CreateBox(500, 200, 50, 50)) AddBoundaryToQuadtree(qtree, CreateLine(300, 300, 350, 590)) 'create a ball to bounce about Local ball:tlCircle = CreateCircle(200, 200, 10) SetBoundaryVelocity(ball, 5, 5) While Not KeyDown(KEY_ESCAPE) Cls 'Query the quadtree with the screen area and call a function that will draw the stuff it finds QueryQuadtreeArea(qtree, 0, 0, GraphicsWidth(), GraphicsHeight(), Null, renderscreen) 'Query the quadtree with the ball and call the function to handle it colliding with stuff in the quadtree QueryQuadtreeBox(qtree, ball, ball, BounceBall) UpdateBoundaryPosition(ball) ball.draw() Flip 1 Wend 'render screen callback function Function renderscreen(o:Object, data:Object) Local box:tlBox = tlBox(o) SetColor 255, 255, 255 box.Draw() End Function 'ball colliding callback function Function BounceBall(o:Object, data:Object) 'o will be the object found in the quadtree 'data is our ball we passed through to this function 'cast the objects into local variables Local ball:tlCircle = tlCircle(data) Local wall:tlBox = tlBox(o) 'check for collisions between the ball and the obstacle found in the quadtree Local result:tlCollisionResult = CheckCollision(ball, wall) 'prevent the 2 objects from overlapping PreventOverlap(result) 'set the ball velocity to the appropriate rebound vector to make it bounce off the walls. ball.velocity = GetReboundVector(result, ball.velocity) End Function

Function IntervalDistance:Float(min0:Float, max0:Float, min1:Float, max1:Float)
Returns	The amount of overlap. Any value less then 0 is not overlapping.
Description	Find the amount of overlap between 2 1D lines.

Function LinesCross:Int(x0:Float, y0:Float, x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float)
Returns	True if lines overlap.
Description	Do a Line to Line collision check.
Information	x0, y0, x1, y1 is the first line and x2, y2, x3, y3 is the second line you want want check for an intersection.

Function LinesCrossAtPoint:Int(x0:Float, y0:Float, x1:Float, y1:Float, x2:Float, y2:Float, x3:Float, y3:Float, X_Point:Float Var, Y_Point:Float Var)
Returns	True if lines overlap, and Sets X_Point and Y_Point to the point of interection.
Description	Do a Line to Line collision check and return the point of intersection.
Information	x0, y0, x1, y1 is the first line and x2, y2, x3, y3 is the second line you want want check for an intersection.

Function LineToCircle:Int(x1:Float, y1:Float, x2:Float, y2:Float, px:Float, py:Float, r:Float)
Returns	True if line and circle overlap.
Description	Do a Line to Circle collision check.
Information	x1, y1 and x2, y2 represent the beginning and end line coordinates, and px, py and r represent the circle coordinates and radius.

Function MoveBoundary(Boundary:tlBox, x:Float, y:Float)
Description	Move a Boundary by a given amount.
Information	This sets the position of a tlBox, tlCircle or tlPolygon by moving it by the x and y amount.

Function NearestPointToCircle:Int(x1:Float, y1:Float, x2:Float, y2:Float, px:Float, py:Float, r:Float, NearestPoint_x:Float, NearestPoint_y:Float)
Returns	NearestPoint_x and NearestPoint_y.
Description	Return the nearest point on a line to the center of a circle.
Information	x1, y1 and x2, y2 represent the beginning and end line coordinates, and px, py and r represent the circle coordinates and radius.

Function PointInside:Int(Boundary:tlBox, x:Float, y:Float)
Returns	True if the point is within.
Description	Find out if a point is within a boundary.
Information	Use this to find out if a point at x,y falls within a tlBox, tlCircle or tlPolygon.

Function PreventOverlap(Result:tlCollisionResult, Push:Int = False)
Description	Prevent boundaries from overlapping, based on a tlCollisionResult.
Information	After you have retrieved a tlCollisionResult from calling CheckCollision you can call this function to separate 2 boundaries from each other. If push is false (default) then the source boundary will be stopped by the target boundary, otherwsie the source bouandry will push the target boundary along it's veloctity vector and the normal of the edge it's pushing against. *NOTE* Remember that after an overlap has been been prevented, the coordinates of the boundary wil have change in order to separate it from the other boundary, so remember to update any other objects coordinates to match this (such as your game object). If your game object is dictating where the boundary is located then it might inadvertantly place the bouandary back inside the object it's colliding with causing strange things to happen.
Example	SuperStrict Import rigz.collision Import "TDungeon.bmx" Const wallsize:Int = 64 'set up a maze using TDungeon - Thanks to impixi from the blitz forums for the code in archives found here: 'http://www.blitzbasic.com/codearcs/codearcs.php?code=1891 Graphics 800, 600 Cls DrawText "Please wait, generating a maze", 10, 10 Flip Local WallGrid:Byte[,] Local Columns:Int Local Rows:Int Local maze:TDungeon = New TDungeon maze.generate(MilliSecs(), 128, 128) wallgrid = maze.getWallGrid() Local d:Int[] = WallGrid.Dimensions() columns = d[0] rows = d[1] 'create the quadtree. We're creating quite a big game world so the quad tree needs quite a few levels to create 'the amount of partitioning we need. 9 levels=256x256 possible partitions (2^(levels-1)) Local QTree:tlQuadTree = CreateQuadtree(0, 0, columns * wallsize, rows * wallsize, 9, 1) 'create and add all of the walls of the maze to the quadtree using tlBox for walls. Local wall:tlBox Local wallcount:Int For Local c:Int = 0 To Columns - 1 For Local r:Int = 0 To Rows - 1 If wallgrid[c, r] = True wall = CreateBox(c * wallsize, r * wallsize, wallsize, wallsize) AddBoundaryToQuadtree(qtree, wall) wallcount:+1 End If Next Next DebugLog wallcount + " walls added to quadtree" DebugLog "World size is " + (columns * wallsize) + " x "+ (rows * wallsize) Local direction:Float Local speed:Float = 5.1 Local velvector:tlVector2 = CreateVector2(0, 0) Local VelMatrix:tlMatrix2 = CreateMatrix2() 'create a player to move about the world, and a camera vector to scroll about with Local camera:tlVector2 = CreateVector2(0, 0) Local player:tlCircle = CreateCircle(96, 96, 16) Local time:Int = MilliSecs() While Not KeyDown(KEY_ESCAPE) Cls 'some basic movement controls for the player If KeyDown(KEY_UP) direction = 0 If KeyDown(KEY_RIGHT) direction = 90 If KeyDown(KEY_DOWN) direction = 180 If KeyDown(KEY_LEFT) direction = 270 If KeyDown(KEY_RIGHT) And KeyDown(KEY_DOWN) direction = 135 If KeyDown(KEY_DOWN) And KeyDown(KEY_LEFT) direction = 225 If KeyDown(KEY_UP) And KeyDown(KEY_RIGHT) direction = 45 If KeyDown(KEY_LEFT) And KeyDown(KEY_UP) direction = 315 If KeyDown(KEY_UP) Or KeyDown(KEY_DOWN) Or KeyDown(KEY_LEFT) Or KeyDown(KEY_RIGHT) velvector.SetPosition(0, -speed) Else velvector.SetPosition(0, 0) End If velmatrix.set(Cos(direction) , Sin(direction) , -Sin(direction) , Cos(direction)) velvector = velmatrix.transformvector(velvector).Unit() velvector = velvector.Scale(speed) 'move the player player.Move(velvector.x, velvector.y) time = MilliSecs() 'query the screen space of the quadtree and call the renderscreen callback funtion QueryQuadtreeArea(qtree, camera.x, camera.y, GraphicsWidth() , GraphicsHeight() , camera, RenderScreen) Local screenobjects:Int = qtree.GetObjectsFound() 'query the quadtree with the player and call the PlayervsWall callback function 'to prevent overlapping with the wall QueryQuadtreeCircle(qtree, player, player, PlayervsWall) 'update the camera position camera.SetPosition(player.world.x - GraphicsWidth() / 2, player.world.y - GraphicsHeight() / 2) 'draw the player setcolor 0, 255, 0 player.draw(camera.x, camera.y) DrawText "Time to run all queries:" + (MilliSecs() - time), 10, 10 DrawText "Render screen objects found: " + screenobjects + " / " + wallcount, 10, 20 DrawText "Objects close to player found: " + qtree.GetObjectsFound() + " / " + wallcount, 10, 30 Flip Wend 'Here's the Render screen function called by the QueryQuadtreeArea function in the mainloop 'everytime it finds an object on screen to draw Function RenderScreen(wall:Object, cam:Object) 'Here, we're passing the wall and the camera as objects through to the callback function 'so we can use casting to put them into local variables Local box:tlBox = tlBox(wall) Local camera:tlVector2 = tlVector2(cam) SetColor 128, 128, 128 'draw the wall, offsetting it's location by the camera coordinates DrawRect box.world.x - camera.x - wallsize / 2, box.world.y - camera.y - wallsize / 2, wallsize, wallsize End Function 'And here's the function called by the QueryQuadtreeCircle function in the mainloop 'evertime it finds an object in the same space as the player Function PlayervsWall(wall:Object, player:Object) 'cast the objects into locals Local box:tlBox = tlBox(wall) Local p:tlCircle = tlCircle(player) 'check for a collision between the player, and the wall Local result:tlCollisionResult = CheckCollision(p, box) 'prevent the 2 from overlapping if necessary. PreventOverlap(result) End Function

Function QueryQuadtreeArea(Quadtree:tlQuadTree, x:Float, y:Float, w:Float, h:Float, Data:Object, callback:Int(ReturnedObject:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query a Quadtree to find objects with an area.
Information	When you want to find objects within a particular area of the quadtree you can use this method. Pass the area coordinates and dimensions that you want to check, an object (Data) that can be anything that you want to pass through to the callback function, and the function callback that you want to perform whatever tasks you need on the objects that are found within the area. The callback function you create needs to have 2 parameters: ReturnedObject:object which will be the Box/circle/poly, and Data:object which can be an object you want to pass through to the call back function. Use GetObjectsFound to find out how many objects were found on the last search.

Function QueryQuadtreeBox(Quadtree:tlQuadTree, area:tlBox, Data:Object, callback:Int(o:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query a quadtree to find objects within a tlBox.
Information	This does the same thing as QueryQuadtreeArea except you can pass a tlBox instead to query the quadtree.

Function QueryQuadtreeCircle(Quadtree:tlQuadTree, circle:tlCircle, Data:Object, callback:Int(ReturnedObject:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query a quadtree to find objects within a tlCircle.
Information	This will query the quadtree and do a callback on any objects it finds within the given tlCircle.

Function QueryQuadtreeEdge:Int(Quadtree:tlQuadTree, x1:Float, y1:Float, x2:Float, y2:Float, Data:Object, callback:Int(ReturnedObject:Object, Data:Object, Result:tlCollisionResult), Layer:Int = tlLAYER_ALL)
Returns	False if the line did not touch anything, otherwise True.
Description	Query a quadtree with a line edge.
Information	This will query the quadtree with a line and perform a callback on all the objects the line intersects. Pass the quadtree to do the query on, the start and end point of the line (x1,y1,x2,y2), an object you want to pass through to the callback, and the callback itself. It's worth noting that the callback also requires you have a tlCollisionResult parameter which will be passed to the callback function with information about the results of the raycast.

Function QueryQuadtreeLine:Int(Quadtree:tlQuadTree, Line:tlLine, Data:Object, callback:Int(ReturnedObject:Object, Data:Object, Result:tlCollisionResult), Layer:Int = tlLAYER_ALL)
Returns	False if the line did not touch anything, otherwise True.
Description	Query a quadtree with a tlLine.
Information	This will query the quadtree with a line and perform a callback on all the objects the tlLine intersects. Pass the quadtree to do the query on, the tlLine to query with, an object you want to pass through to the callback, and the callback itself. It's worth noting that the callback also requires you have a tlCollisionResult parameter which will be passed to the callback function with information about the results of the raycast.
Example	SuperStrict Import rigz.collision Graphics 1024, 768 'Create our quadtree. Here we're allowing for 5 levels of subdivision and upto 1 object before subdividing 'a quadtree node Local QTree:tlQuadTree = CreateQuadtree(0, 0, GraphicsWidth() , GraphicsHeight(), 5, 1) 'Populate the quadtree with a bunch of objects For Local c:Int = 1 To 1000 Local t:Int = Rnd(3) Local rect:tlBox Select t Case 0 'Create a Basic bounding box boundary rect = CreateBox(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), 10, 10) Case 1 'Create a circle Boundary rect = CreateCircle(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), 5) Case 2 'Create a polygon boundary Local verts:Float[] = [- 10.0, -10.0, -15.0, 0.0, -10.0, 10.0, 10.0, 10.0, 15.0, 0.0, 10.0, -10.0] rect = CreatePolygon(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), verts) RotatePolygon(tlPolygon(rect), Rnd(360)) End Select 'Add the boundary to the quadtree AddBoundaryToQuadtree(QTree, rect) Next 'create a ray vector and its point of origin Local line:tlLine = CreateLine(200, 200, 500, 500) While Not KeyDown(KEY_ESCAPE) Cls 'set the ray to point towards the mouse pointer If MouseDown(1) line.SetPosition(MouseX(), MouseY()) If MouseDown(2) line.Rotate(1) 'Query screen space and render all on screen QueryQuadtreeArea(QTree, 0, 0, GraphicsWidth(), GraphicsHeight(), Null, RenderScreen) 'query the quadtree with the ray and run our call back if it hit. Otherwise draw the full length of the ray (300) 'we're using the data variable here to pass through the Point to the callback function QueryQuadtreeLine(qtree, line, line, LineHandler) SetColor 255, 255, 255 line.draw() SetColor 0, 255, 0 DrawText "Click and drag to move the line about", 10, 10 DrawText "Use right mouse to rotate the line", 10, 20 Flip 1 Wend 'Our first callback function which is called when space is pressed and objects are found within the screen space Function RenderScreen(o:Object, data:Object) 'use casting to create the local rect Local rect:tlBox = tlBox(o) 'and draw it SetColor 255, 255, 255 rect.draw() End Function 'Our call back function to handle the ray cast. Note that a ray cast callback must also have a tlCollisionResult parameter. Function LineHandler(o:Object, data:Object, result:tlCollisionResult) 'cast the objects to some local variables Local line:tlLine = tlLine(data) Local box:tlBox = tlBox(o) SetColor 0, 255, 0 box.Draw() End Function

Function QueryQuadtreeRange(Quadtree:tlQuadTree, x:Float, y:Float, radius:Float, Data:Object, callback:Int(ReturnedObject:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query a quadtree to find objects within a certain radius.
Information	This will query the quadtree and do a callback on any objects it finds within a given radius. See QueryQuadtreeArea for more info.

Function QueryQuadtreeRay:Int(Quadtree:tlQuadTree, px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0, Data:Object, callback:Int(ReturnedObject:Object, Data:Object, Result:tlCollisionResult), Layer:Int = tlLAYER_ALL)
Returns	False if the ray did not hit anything, otherwise True.
Description	Query a quadtree with a Ray.
Information	This will query the quadtree with a ray and perform a callback on the first object the ray hits. Pass the quadtree to do the query on, the starting point of the ray (px,py), the direction vector of the ray (dx,dy), the maximum distance you want the ray to travel (maxdistance, 0 means an infinit ray will be cast), an object you want to pass through to the callback, and the callback itself. It's worth noting that the callback also requires you have a tlCollisionResult parameter which will be passed to the callback function with information about the results of the raycast.
Example	SuperStrict Import rigz.collision Graphics 1024, 768 'Create our quadtree. Here we're allowing for 5 levels of subdivision and upto 1 object before subdividing 'a quadtree node Local QTree:tlQuadTree = CreateQuadtree(0, 0, GraphicsWidth() , GraphicsHeight(), 5, 1) 'Populate the quadtree with a bunch of objects For Local c:Int = 1 To 250 Local t:Int = Rnd(3) Local rect:tlBox Select t Case 0 'Create a Basic bounding box boundary rect = CreateBox(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), 10, 10) Case 1 'Create a circle Boundary rect = CreateCircle(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), 5) Case 2 'Create a polygon boundary Local verts:Float[] = [- 10.0, -10.0, -15.0, 0.0, -10.0, 10.0, 10.0, 10.0, 15.0, 0.0, 10.0, -10.0] rect = CreatePolygon(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), verts) RotatePolygon(tlPolygon(rect), Rnd(360)) End Select 'Add the boundary to the quadtree AddBoundaryToQuadtree(QTree, rect) Next 'create a ray vector and its point of origin Local ray:tlVector2 = New tlVector2.Create(0, 0) Local point:tlVector2 = New tlVector2.Create(400, 300) While Not KeyDown(KEY_ESCAPE) Cls 'set the ray to point towards the mouse pointer If MouseDown(1) point.SetPosition(MouseX(), MouseY()) ray.SetPosition(MouseX() - point.x, MouseY() - point.y) 'normalise the ray into a unit vector. Not necessary for the ray cast query, it's just so 'I can draw the ray a specific length ray.Normalise() 'Query screen space and render all on screen QueryQuadtreeArea(QTree, 0, 0, GraphicsWidth(), GraphicsHeight(), Null, RenderScreen, 1) 'query the quadtree with the ray and run our call back if it hit. Otherwise draw the full length of the ray (300) 'we're using the data variable here to pass through the Point to the callback function If Not QueryQuadtreeRay(qtree, point.x, point.y, ray.x, ray.y, 300, point, RayHandler, 1) SetColor 255, 0, 0 DrawLine point.x, point.y, point.x + ray.x * 300, point.y + ray.y * 300 End If SetColor 255, 255, 255 DrawText "Click and drag to move the ray origin about", 10, 10 Flip 1 Wend 'Our first callback function which is called when space is pressed and objects are found within the screen space Function RenderScreen(o:Object, data:Object) 'use casting to create the local rect Local rect:tlBox = tlBox(o) 'and draw it SetColor 255, 255, 255 rect.draw() End Function 'Our call back function to handle the ray cast. Note that a ray cast callback must also have a tlCollisionResult parameter. Function RayHandler(o:Object, data:Object, result:tlCollisionResult) 'cast the objects to some local variables Local point:tlVector2 = tlVector2(data) Local box:tlBox = tlBox(o) SetColor 255, 0, 0 'if the ray does not originate inside an object then draw the ray and intersection point If Not result.GetRayOriginInside() DrawLine point.x, point.y, result.GetRayIntersection().x, result.GetRayIntersection().y DrawOval result.GetRayIntersection().x - 4, result.GetRayIntersection().y - 4, 8, 8 End If 'draw the box we collided with in a different colour box.Draw() End Function

Function RemoveBoundaryFromQuadTree(Box:tlBox)
Description	Remove a boundary from the quadtree.
Information	This will remove a boundary from the quadtree. You'll need to do this when your actor/entity using the boundary is destroyed, blown up or whatever! No need to pass the quadtree as the boundary knows what quadtree it lives in.

Function RotatePolygon(Poly:tlPolygon, angle:Float)
Description	Rotate a tlPolygon.
Information	This will rotate the polygon by the given amount.

Function RunQuadtreeMaintenance(Quadtree:tlQuadtree)
Description	Perform some house keeping on a quadtree.
Information	This will search a quadtree tree for any empty tlQuadTreeNodes and unpartition them if necessary. It's probably unnecessary to run to every frame. Every other frame should be more then enough, and maybe not even necessary at all, it will depend on how you're using the quadtree.

Function SameLayer:Int(Source:tlBox, Target:tlBox)
Returns	True if they are on the same layer, otherwise false.
Description	Find out if 2 boundaries are on the same collision layers.

Function ScaleBoundary(Boundary:tlBox, x:Float, y:Float)
Description	Set the scale of a Boundary.
Information	This sets the scale a tlBox, tlCircle or tlPolygon by x and y (or just x in the case if a tlCircle)

Function SetBoundaryData(Boundary:tlBox, Data:Object)
Description	Assign an object to a boundary.
Information	This can be handy to store extra custom info about a boundary.

Function SetBoundaryLayer(Boundary:tlBox, layer:Int)

Description

Set the collision layer that this boundary is on.

Information

The layer a boundary is on can determine what other boundarys this one can collide with. You may not want some objects to be able to collide with each other, so you can arrange them of different layers. There are 32 layers, assigned to constants: tlLAYER_1, tlLAYER2, tlLAYER_3.. and so on up to 32, so to assign a layer, simply pass the appropriate constant:

MyBox.SetCollisionLayer(tlLAYER_1)

You can also assign to more then one layer using OR:

MyBox.SetCollisionLayer(tlLAYER_1 | tlLAYER_2 | tlLAYER_3)

Finally, assign it to all layers using:

MyBox.SetCollisionLayer(tlLAYER_ALL)

Function SetBoundaryPosition(Boundary:tlBox, x:Float, y:Float)
Description	Set the position of a Boundary.
Information	Sets the position of a tlBox, tlCircle or tlPolygon.

Function SetBoundaryVelocity(Boundary:tlBox, Velocity_x:Float, Velocity_y:Float)
Description	Set the velocity of a boundary.
Information	It's import to set the velocity of the boundary so that collisions can be more accurately calculated. If you're attaching this to an entity in your game then you'll just need to match this to your entities velocity.

Function SetPolygonAngle(Poly:tlPolygon, angle:Float)
Description	Set the angle of a tlPolygon.
Information	This will set the angle of a polygon to the given amount.

Function UpdateBoundaryPosition(Boundary:tlBox)
Description	Update the position of the boundary.
Information	You can use this function to update a boundary's position according to its current velocity vector.

Function WithinFieldOfView:Int(Observer_x:Float, Observer_y:Float, FOV:Float, Direction:Float, PointX:Float, PointY:Float)
Returns	True if if point is withing observers fov, otherwise false.
Description	Check if a point is with a field of view.

Types

Type tlBox

Description

Type for handling Axis Aligned Bounding Boxes.

Information

This type can be used to create bounding boxes for the purpose of collision checking. This is the type used to stored objects in tlQuadTree. It's extended by tlCircle and tlPolygon. To implement collision checking in you game/app will probably end up inlcluding these as a field within your own types, and possibly extending these types so that they can contain a field linking back to your own entity/actor types. Use SetPosistion and Move to align them in your game world, using these methods also ensures that they will be updated within the quadtree if they belong in one.

It's worth noting that if you want a bounding box that can be orientated then create a 4 sided poly using a tlPolygon.

The world coordinates are stored as a vector within the field World, so you can use world.x and world.y to retreive the coordinates of the box.

Methods Summary
BoundingBoxOverlap	Compare this tlBox with another to see if they overlap.
BoxCollide	Check for a collision with another tlBox.
CircleCollide	Check for a collision with a tlCircle.
CircleOverlap	Compare this tlBox with a tlCircle.
Create	Create a new tlBox.
Draw	Draw this tlBox.
GetCollisionLayer	Get the collision layer that this boundary is on.
GetCollisionType	Get the collision type of the Box.
GetData	Get the data assigned to this boundary.
GetShadowPolys	Get a poly represting the shadow of the box.
GetWorldX	Get the x world coordinate of the boundary.
GetWorldY	Get the y world coordinate of the boundary.
LineCollide	Check for a collision with a tlLine.
Move	Move the bounding box by a given amount.
PointInside	Find out if a point is within the bounding box.
PolyCollide	Check for a collision with a tlPolygon.
PreventOverlap	Prevent the boundary from overlapping another based on the result of a collision.
RayCollide	See is a ray collides with this tlbox.
RectWithin	Find out if a tlBox lies within this objects bounding box.
RemoveFromQuadTree	Remove the tlBox from the quadtree.
SetCollisionLayer	Set the collision layer that this boundary is on.
SetData	Assign an object to the boundary.
SetPosition	Set the position of the bounding box.
SetScale	Set the scale of the Box.
SetVelocity	Set the velocity of the boundary.
UpdatePosition	Update the position of the boundary.

Method BoundingBoxOverlap:Int(rect:tlBox, VelocityCheck:Int = False)
Returns	True if they do overlap.
Description	Compare this tlBox with another to see if they overlap.
Information	Use this to find out if this tlBox overlaps the tlBox you pass to it. This is a very simple overlap to see if the bounding box overlaps only Set VelocityCheck to true if you want to see if they will overlap next frame based on their velocities.

Method BoxCollide:tlCollisionResult(Box:tlBox)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with another tlBox.
Information	Use this to check for a collision with another tlBox that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CircleCollide:tlCollisionResult(circle:tlCircle)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlCircle.
Information	Use this to check for a collision with a tlCircle that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CircleOverlap:Int(circle:tlCircle)
Returns	True if they do overlap.
Description	Compare this tlBox with a tlCircle.
Information	This will perfrom a simple bounding box to circle collision check on the tlCircle you pass to it.

Method Create:tlBox(x:Float, y:Float, w:Float, h:Float, layer:Int = tlLAYER_1, Data:Object = Null)
Returns	New tlBox.
Description	Create a new tlBox.
Information	Creates a new Bounding box that you can use for collision checking and adding to a tlQuadTree. The x and y coordinates represent the top left corner of the bounding box. You can also assign some data to the boundary as handy way to store some extra info about the boundary.

Method Draw(offsetx:Float = 0, offsety:Float = 0, boundingbox:Int = False)
Description	Draw this tlBox.
Information	Use this if you need to draw the bounding box for debugging purposes.

Method GetCollisionLayer:Int()
Description	Get the collision layer that this boundary is on.

Method GetCollisionType:Int()
Returns	Either tlBOX_COLLISION, tlCIRCLE_COLLISION, tlLINE_COLLISION or tlPOLY_COLLISION.
Description	Get the collision type of the Box.
Information	the collision type can help you determine what type of collision you should be performing on objects calledback from quadtree queries.

Method GetData:Object()
Description	Get the data assigned to this boundary.
Information	Use this to retrieve the custom data you have assign to the boundary.

Method GetShadowPolys:TList (Light:tlVector2, lType:Int = tlDIRECTIONAL_LIGHT, lengthfactor:Float = 1)
Returns	tList of tlPolygons representing each shadow cast by each line in the box.
Description	Get a poly represting the shadow of the box.
Information	This will take a light located at Light:tlVector2 and create a list of tlPolygons representing a shadow cast by each line in the box.

Method GetWorldX:Float()
Returns	Float with the current x coordinate.
Description	Get the x world coordinate of the boundary.
Information	You can use this to find out the current x coordinate of the boundary. This would be especially useful if you have just used PreventOverlap and need to know the new position of the object to update your game object.

Method GetWorldY:Float()
Returns	Float with the current y coordinate.
Description	Get the y world coordinate of the boundary.
Information	You can use this to find out the current y coordinate of the boundary. This would be especially useful if you have just used PreventOverlap and need to know the new position of the object to update your game object.

Method LineCollide:tlCollisionResult(Line:tlLine)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlLine.
Information	Use this to check for a collision with a tlLine that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method Move(x:Float, y:Float)
Description	Move the bounding box by a given amount.
Information	This sets the position of the top left corner of the bounding box by moving it by the x and y amount. If the box is within quadtree it will automatically update itself within it.

Method PointInside:Int(x:Float, y:Float)
Returns	True if the point is within.
Description	Find out if a point is within the bounding box.
Information	Use this to find out if a point at x,y falls with the bounding box of this tlBox.

Method PolyCollide:tlCollisionResult(poly:tlPolygon)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlPolygon.
Information	Use this to check for a collision with a tlPolygon that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method PreventOverlap(result:tlCollisionResult, push:Int = False)
Description	Prevent the boundary from overlapping another based on the result of a collision.
Information	When you check for a collision, the results of that collision are stored with a tlCollisionResult. This can be passed to this method to prevent 2 boundaries from overlapping. If push is set to true, then the source boundary will push the target boundary along it's velocity vector.
Example	SuperStrict Import rigz.collision Import "TDungeon.bmx" Const wallsize:Int = 64 'set up a maze using TDungeon - Thanks to impixi from the blitz forums for the code in archives found here: 'http://www.blitzbasic.com/codearcs/codearcs.php?code=1891 Graphics 800, 600 Cls DrawText "Please wait, generating a maze", 10, 10 Flip Local WallGrid:Byte[,] Local Columns:Int Local Rows:Int Local maze:TDungeon = New TDungeon maze.generate(MilliSecs(), 128, 128) wallgrid = maze.getWallGrid() Local d:Int[] = WallGrid.Dimensions() columns = d[0] rows = d[1] 'create the quadtree. We're creating quite a big game world so the quad tree needs quite a few levels to create 'the amount of partitioning we need. 9 levels=256x256 possible partitions (2^(levels-1)) Local QTree:tlQuadTree = CreateQuadtree(0, 0, columns * wallsize, rows * wallsize, 9, 1) 'create and add all of the walls of the maze to the quadtree using tlBox for walls. Local wall:tlBox Local wallcount:Int For Local c:Int = 0 To Columns - 1 For Local r:Int = 0 To Rows - 1 If wallgrid[c, r] = True wall = CreateBox(c * wallsize, r * wallsize, wallsize, wallsize) AddBoundaryToQuadtree(qtree, wall) wallcount:+1 End If Next Next DebugLog wallcount + " walls added to quadtree" DebugLog "World size is " + (columns * wallsize) + " x "+ (rows * wallsize) Local direction:Float Local speed:Float = 5.1 Local velvector:tlVector2 = CreateVector2(0, 0) Local VelMatrix:tlMatrix2 = CreateMatrix2() 'create a player to move about the world, and a camera vector to scroll about with Local camera:tlVector2 = CreateVector2(0, 0) Local player:tlCircle = CreateCircle(96, 96, 16) Local time:Int = MilliSecs() While Not KeyDown(KEY_ESCAPE) Cls 'some basic movement controls for the player If KeyDown(KEY_UP) direction = 0 If KeyDown(KEY_RIGHT) direction = 90 If KeyDown(KEY_DOWN) direction = 180 If KeyDown(KEY_LEFT) direction = 270 If KeyDown(KEY_RIGHT) And KeyDown(KEY_DOWN) direction = 135 If KeyDown(KEY_DOWN) And KeyDown(KEY_LEFT) direction = 225 If KeyDown(KEY_UP) And KeyDown(KEY_RIGHT) direction = 45 If KeyDown(KEY_LEFT) And KeyDown(KEY_UP) direction = 315 If KeyDown(KEY_UP) Or KeyDown(KEY_DOWN) Or KeyDown(KEY_LEFT) Or KeyDown(KEY_RIGHT) velvector.SetPosition(0, -speed) Else velvector.SetPosition(0, 0) End If velmatrix.set(Cos(direction) , Sin(direction) , -Sin(direction) , Cos(direction)) velvector = velmatrix.transformvector(velvector).Unit() velvector = velvector.Scale(speed) 'move the player player.Move(velvector.x, velvector.y) time = MilliSecs() 'query the screen space of the quadtree and call the renderscreen callback funtion QueryQuadtreeArea(qtree, camera.x, camera.y, GraphicsWidth() , GraphicsHeight() , camera, RenderScreen) Local screenobjects:Int = qtree.GetObjectsFound() 'query the quadtree with the player and call the PlayervsWall callback function 'to prevent overlapping with the wall QueryQuadtreeCircle(qtree, player, player, PlayervsWall) 'update the camera position camera.SetPosition(player.world.x - GraphicsWidth() / 2, player.world.y - GraphicsHeight() / 2) 'draw the player setcolor 0, 255, 0 player.draw(camera.x, camera.y) DrawText "Time to run all queries:" + (MilliSecs() - time), 10, 10 DrawText "Render screen objects found: " + screenobjects + " / " + wallcount, 10, 20 DrawText "Objects close to player found: " + qtree.GetObjectsFound() + " / " + wallcount, 10, 30 Flip Wend 'Here's the Render screen function called by the QueryQuadtreeArea function in the mainloop 'everytime it finds an object on screen to draw Function RenderScreen(wall:Object, cam:Object) 'Here, we're passing the wall and the camera as objects through to the callback function 'so we can use casting to put them into local variables Local box:tlBox = tlBox(wall) Local camera:tlVector2 = tlVector2(cam) SetColor 128, 128, 128 'draw the wall, offsetting it's location by the camera coordinates DrawRect box.world.x - camera.x - wallsize / 2, box.world.y - camera.y - wallsize / 2, wallsize, wallsize End Function 'And here's the function called by the QueryQuadtreeCircle function in the mainloop 'evertime it finds an object in the same space as the player Function PlayervsWall(wall:Object, player:Object) 'cast the objects into locals Local box:tlBox = tlBox(wall) Local p:tlCircle = tlCircle(player) 'check for a collision between the player, and the wall Local result:tlCollisionResult = CheckCollision(p, box) 'prevent the 2 from overlapping if necessary. PreventOverlap(result) End Function

Method RayCollide:tlCollisionResult(px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0)
Returns	tlCollisionResult with the results of the collision.
Description	See is a ray collides with this tlbox.
Information	You can use this to test for a collision with a ray. Pass the origin of the ray with px and py, and set the direction of the ray with dx and dy. dx and dy will be normalised and extended infinitely, if maxdistance equals 0 (default), otherwise set maxdistance to how ever far you want the ray to extend to. If the ray starts inside the box then result.rayorigininside will be set to true.

Method RectWithin:Int(rect:tlBox)
Returns	True if it is within.
Description	Find out if a tlBox lies within this objects bounding box.
Information	If you need to know whether a tlBox you pass to this method, lies entirely with this tlBox (no overlapping) then you can use this method. Remember, if you call this method from a poly, line or circle, it will only check against the bounding boxes.

Method RemoveFromQuadTree()
Description	Remove the tlBox from the quadtree.
Information	This will remove the tlBox from the quadtree. You'll need to do this when an actor/entity is destroyed, blown up or whatever!

Method SetCollisionLayer(Layer:Int)

Description

Set the collision layer that this boundary is on.

Information

MyBox.SetCollisionLayer(tlLAYER_1)

You can also assign to more then one layer using OR:

MyBox.SetCollisionLayer(tlLAYER_1 | tlLAYER_2 | tlLAYER_3)

Finally, assign it to all layers using:

MyBox.SetCollisionLayer(tlLAYER_ALL)

Method SetData(d:Object)
Description	Assign an object to the boundary.
Information	This can be handy to store extra custom info about the boundary.

Method SetPosition(x:Float, y:Float)
Description	Set the position of the bounding box.
Information	This sets the position of the top left corner of the bounding box. If the box is within quadtree it will automatically update itself within it.

Method SetScale(x:Float, y:Float)
Description	Set the scale of the Box.
Information	This sets scale of the Box.

Method SetVelocity(Velocity_x:Float, Velocity_y:Float)
Description	Set the velocity of the boundary.
Information	It's import to set the velocity of the boundary so that collisions can be more accurately calculated. If you're attaching this to an entity in your game then you'll just need to match this to your entities velocity.

Method UpdatePosition()
Description	Update the position of the boundary.
Information	You can use this method to update it's position according to its current velocity vector.

Type tlCircle Extends tlBox
Description	tlCircle for circular boundaries for collision checking.
Information	This extends tlBox so automatically inherits a bounding box, which can be checked first before doing a more complicated circle collision check. You can add this type to a tlQuadTree just as though it were a standard tlBox, as the quadtree only concerns itself with Boxs.

Methods Summary
BoundingBoxOverlap	Compare this tlCircle with a tlBox.
BoxCollide	Check for a collision with a tlBox.
CircleCollide	Check for a collision with another tlCircle.
CircleOverlap	Compare this circle with another tlCircle.
CreateCircle	Create a tlCircle.
draw	Draw this tlBox.
LineCollide	Check for a collision with a tlLine.
PointInside	Find out if a point is within the circle.
PolyCollide	Check for a collision with a tlPolygon.
RayCollide	See is a ray collides with this tlCircle.
SetCircle	Set the Box of the circle.

Method BoundingBoxOverlap:Int(rect:tlBox, VelocityCheck:Int = False)
Returns	True if they do overlap.
Description	Compare this tlCircle with a tlBox.
Information	This will perfrom a simple circle to bounding box overlap check on the tlBox you pass to it.

Method BoxCollide:tlCollisionResult(Box:tlBox)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlBox.
Information	Use this to check for a collision with a tlBox that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CircleCollide:tlCollisionResult(circle:tlCircle)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with another tlCircle.
Information	Use this to check for a collision with another tlCircle that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CircleOverlap:Int(circle:tlCircle)
Returns	True if they do overlap.
Description	Compare this circle with another tlCircle.
Information	This will perfrom a simple circle to circle collision check on the tlCircle you pass to it.

Method CreateCircle:tlCircle(x:Float, y:Float, _radius:Float, layer:Int = tlLAYER_1, Data:Object = Null)
Returns	New tlCircle.
Description	Create a tlCircle.
Information	Create a new tlCircle at the given coordinates with the given radius. The coordinates will represent where the center of the circle is located in the world. You can also assign some data to the boundary as handy way to store some extra info about the boundary.

Method draw(offsetx:Float = 0, offsety:Float = 0, BoundingBox:Int = False)
Description	Draw this tlBox.
Information	Use this if you need to draw the bounding box for debugging purposes. Pass true of false to draw the bounding box as well.

Method LineCollide:tlCollisionResult(Line:tlLine)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlLine.
Information	Use this to check for a collision with a tlLine that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method PointInside:Int(x:Float, y:Float)
Returns	True if the point is within.
Description	Find out if a point is within the circle.
Information	Use this to find out if a point at x,y falls with the radius of this tlCircle.

Method PolyCollide:tlCollisionResult(poly:tlPolygon)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlPolygon.
Information	Use this to check for a collision with another tlPolygon that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method RayCollide:tlCollisionResult(px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0)
Returns	tlCollisionResult with the results of the collision.
Description	See is a ray collides with this tlCircle.
Information	You can use this to test for a collision with a ray. Pass the origin of the ray with px and py, and set the direction of the ray with dx and dy. dx and dy will be normalised and extended infinitely, if maxdistance equals 0 (default), otherwise set maxdistance to how ever far you want the ray to extend to. If the ray starts inside the poly then result.rayorigininside will be set to true.

Method SetCircle(x:Float, y:Float, _radius:Float)
Description	Set the Box of the circle.
Information	this lets you change the size and location of the tlCircle.

Type tlCollisionResult
Description	Type to store the results of collisions.
Information	When you check for a collision between 2 objects (see CheckCollision) the result of that check will be a tlCollisionResult. This contains information about how the 2 objects collided and can be used to do further calculations. Call GetIntersecting to find out if the 2 objects overlap each other and call GetWillIntersect to see if they will overlap based on their velocities. GetSourceBoundary and GetTargetBoundary will return the object making the collision check and the object being checked against respectively with the exception when using CheckRayCollision where only the target us set. Preventing objects from overlapping can be achieved by simply calling PreventOverlap.

Methods Summary
GetIntersecting	Find out if the last collision check is intersecting.
GetRayDistance	Get the distance from the ray origin to the instersection point.
GetRayIntersection	Get the intersection point of the raycast.
GetRayOriginInside	Find out if the last ray cast found that the ray originated inside the boundary.
GetReboundVector	Get the rebound vector.
GetSourceBoundary	Gets the Source boundary of a collision check.
GetTargetBoundary	Gets the Target boundary of a collision check.
GetTranslationVector	Get the translation vector of the collision.
GetWillIntersect	Find out if the last collision check is intersecting.

Method GetIntersecting:Int()
Returns	true if there was an intersection.
Description	Find out if the last collision check is intersecting.

Method GetRayDistance:Float()
Returns	float value of distance the ray travelled, 0 if there was no intersection.
Description	Get the distance from the ray origin to the instersection point.

Method GetRayIntersection:tlVector2()
Returns	tlvector2.
Description	Get the intersection point of the raycast.
Information	If a ray cast has been performed and the ray successfully connected, then this will return the point of intersection as a tlVector2.

Method GetRayOriginInside:Int()
Returns	true if the last ray check originated inside the boundary.
Description	Find out if the last ray cast found that the ray originated inside the boundary.

Method GetReboundVector:tlVector2(v:tlVector2, friction:Float = 0, bounce:Float = 1)
Returns	New tlVector2 with the resulting rebound vector.
Description	Get the rebound vector.
Information	When an object collides with a surface you may want to know a resulting vector based on bounce and friction. So you can call this and pass the velocity vector of the incoming object, and the amount of bounce and friction to have, where a bounce value of 1 and a friction value of 0 will result in a perfect bounce.
Example	SuperStrict Import rigz.collision Graphics 800, 600 Local qtree:tlQuadTree = CreateQuadtree(0, 0, GraphicsWidth(), GraphicsHeight()) 'Add some obstacles to the quadtree AddBoundaryToQuadtree(qtree, CreateBox(10, 0, GraphicsWidth() - 20, 10)) AddBoundaryToQuadtree(qtree, CreateBox(10, GraphicsHeight() - 10, GraphicsWidth() - 20, 10)) AddBoundaryToQuadtree(qtree, CreateBox(0, 10, 10, GraphicsHeight() - 20)) AddBoundaryToQuadtree(qtree, CreateBox(GraphicsWidth() - 10, 10, 10, GraphicsHeight() - 20)) Local verts:Float[] = [- 50.0, -50.0, -70.0, 0.0, -50.0, 50.0, 50.0, 50.0, 100.0, 0.0, 50.0, -50.0] AddBoundaryToQuadtree(qtree, CreatePolygon(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), verts)) AddBoundaryToQuadtree(qtree, CreateCircle(500, 400, 100)) AddBoundaryToQuadtree(qtree, CreateBox(500, 200, 50, 50)) AddBoundaryToQuadtree(qtree, CreateLine(300, 300, 350, 590)) 'create a ball to bounce about Local ball:tlCircle = CreateCircle(200, 200, 10) SetBoundaryVelocity(ball, 5, 5) While Not KeyDown(KEY_ESCAPE) Cls 'Query the quadtree with the screen area and call a function that will draw the stuff it finds QueryQuadtreeArea(qtree, 0, 0, GraphicsWidth(), GraphicsHeight(), Null, renderscreen) 'Query the quadtree with the ball and call the function to handle it colliding with stuff in the quadtree QueryQuadtreeBox(qtree, ball, ball, BounceBall) UpdateBoundaryPosition(ball) ball.draw() Flip 1 Wend 'render screen callback function Function renderscreen(o:Object, data:Object) Local box:tlBox = tlBox(o) SetColor 255, 255, 255 box.Draw() End Function 'ball colliding callback function Function BounceBall(o:Object, data:Object) 'o will be the object found in the quadtree 'data is our ball we passed through to this function 'cast the objects into local variables Local ball:tlCircle = tlCircle(data) Local wall:tlBox = tlBox(o) 'check for collisions between the ball and the obstacle found in the quadtree Local result:tlCollisionResult = CheckCollision(ball, wall) 'prevent the 2 objects from overlapping PreventOverlap(result) 'set the ball velocity to the appropriate rebound vector to make it bounce off the walls. ball.velocity = GetReboundVector(result, ball.velocity) End Function

Method GetSourceBoundary:tlBox()
Returns	tlBox Or null if no collision occurred.
Description	Gets the Source boundary of a collision check.

Method GetTargetBoundary:tlBox()
Returns	tlBox Or null if no collision occurred.
Description	Gets the Target boundary of a collision check.

Method GetTranslationVector:tlVector2()
Returns	tlVector2.
Description	Get the translation vector of the collision.
Information	If the collision check finds that either the objects are intersecting, or they will intersect, then the translation vector hold exactly how much they do or will overlap. This can then be used to move the 2 objects apart to prevent them overlapping. Handy if you have a wall that you don't want a player to move through. See PreventOverlap to automate this process further.

Method GetWillIntersect:Int()
Returns	true if there will be an intersection.
Description	Find out if the last collision check is intersecting.
Information	knowing if there will be an intersection allows you to adjust the position of objects so that visually they will never overlap. Do do this you can use the information stored in the translation vector, which is the vector describing how much the objects need to move so that they no longer overlap. See GetTranslationVector.

Type tlLine Extends tlPolygon
Description	tlLine for line collisions.
Information	This type extends tlPolygon and can be used to check for collisions with any of the other types of collision.

Methods Summary
BoxCollide	Check for a collision with a tlBox.
CircleCollide	Check for a collision with a tlCircle.
CreateLine	Create a tlLine.
LineCollide	Check for a collision with another tlLine.
PolyCollide	Check for a collision with a tlPoly.
RayCollide	See is a ray collides with this tlLine.

Method BoxCollide:tlCollisionResult(Box:tlBox)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlBox.
Information	Use this to check for a collision with a tlBox that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CircleCollide:tlCollisionResult(circle:tlCircle)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlCircle.
Information	Use this to check for a collision with a tlCircle that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CreateLine:tlLine(x1:Float, y1:Float, x2:Float, y2:Float, layer:Int = tlLAYER_1, Data:Object = Null)
Returns	New tlLine.
Description	Create a tlLine.
Information	Create a new tlLine at the coordinates given, x1 and y1 being the start of the line and x2 and y2 being the end. The will placed exactly according to the coordinates you give, but it's worth bearing in mind that the handle of the line will be at the center point along the line. Therefore the world coordinates will be set to half way point along the line. You can also assign some data to the boundary as handy way to store some extra info about the boundary.

Method LineCollide:tlCollisionResult(Line:tlLine)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with another tlLine.
Information	Use this to check for a collision with another tlLine that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method PolyCollide:tlCollisionResult(poly:tlPolygon)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlPoly.
Information	Use this to check for a collision with a tlPoly that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method RayCollide:tlCollisionResult(px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0)
Returns	tlCollisionResult with the results of the collision.
Description	See is a ray collides with this tlLine.
Information	You can use this to test for a collision with a ray. Pass the origin of the ray with px and py, and set the direction of the ray with dx and dy. dx and dy will be normalised and extended infinitely, if maxdistance equals 0 (default), otherwise set maxdistance to how ever far you want the ray to extend to. If the ray starts inside the poly then result.rayorigininside will be set to true.

Type tlPolygon Extends tlBox
Description	tlPolygon for convex polygon collisions.
Information	This extends tlBox so automatically inherits a bounding box, which can be checked first before doing a more complicated polygon collision check. You can add this type to a tlQuadTree just as though it were a standard tlBox, as the quadtree only concerns itself with Boxs.

Methods Summary
BoxCollide	Check for a collision with a tlBox.
CircleCollide	Check for a collision with a tlCircle.
CreatePoly	Create a tlPolygon.
CreatePolyWorld	Create a tlPolygon.
draw	Draw the polygon.
LineCollide	Check for a collision with a tlLine.
PointInside	Find out if a point resides withing the tlPolygon.
PolyCollide	Check for a collision with another tlpolygon.
RayCollide	See is a ray collides with this tlpolygon.
Rotate	Rotate the polygon.
SetAngle	Set the angle of the polygon.
SetScale	Set the scale of the Polygon.

Method BoxCollide:tlCollisionResult(Box:tlBox)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlBox.
Information	Use this to check for a collision with a tlBox that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CircleCollide:tlCollisionResult(circle:tlCircle)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlCircle.
Information	Use this to check for a collision with a tlCircle that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method CreatePoly:tlPolygon(x:Float, y:Float, verts:Float[], layer:Int = tlLAYER_1, Data:Object = Null)
Returns	New tlPolygon, or Null if verts[] contained the wrong amount.
Description	Create a tlPolygon.
Information	Create a new tlPolygon at the given coordinates with the given array of vertices. The coordinates will represent the center of the polygon, but this can be changed with SetPolyHandle. The array must contain more then 5 values (2 per vertex) and be an even number or null will be returned. The coordinates of the vertices in the array are arranged like so: [x,y,x,y,x,y .. etc]. You can also assign some data to the boundary as handy way to store some extra info about the boundary.

Method CreatePolyWorld:tlPolygon(verts:Float[], layer:Int = tlLAYER_1, Data:Object = Null)
Returns	New tlPolygon, or Null if verts[] contained the wrong amount.
Description	Create a tlPolygon.
Information	Create a new tlPolygon at the given coordinates with the given array of vertices. The coordinates will represent the center of the polygon, but this can be changed with SetPolyHandle. The array must contain more then 5 values (2 per vertex) and be an even number or null will be returned. The coordinates of the vertices in the array are arranged like so: [x,y,x,y,x,y .. etc]. You can also assign some data to the boundary as handy way to store some extra info about the boundary.

Method draw(offsetx:Float = 0, offsety:Float = 0, BoundingBox:Int = False)
Description	Draw the polygon.
Information	You can use this for debugging purposes. Pass true of false to draw the bounding box as well.

Method LineCollide:tlCollisionResult(Line:tlLine)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with a tlLine.
Information	Use this to check for a collision with a tlLine that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method PointInside:Int(x:Float, y:Float)
Returns	True if they do overlap.
Description	Find out if a point resides withing the tlPolygon.
Information	Use this to check if a point with the given coordinates lies within the polygon.

Method PolyCollide:tlCollisionResult(poly:tlPolygon)
Returns	tlCollisionResult type containing info about the collision.
Description	Check for a collision with another tlpolygon.
Information	Use this to check for a collision with a tlPolygon that you pass to the method. You can then use the information stored in tlCollisionResult to perform various things based on the result of the collision check.

Method RayCollide:tlCollisionResult(px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0)
Returns	tlCollisionResult with the results of the collision.
Description	See is a ray collides with this tlpolygon.
Information	You can use this to test for a collision with a ray. Pass the origin of the ray with px and py, and set the direction of the ray with dx and dy. dx and dy will be normalised and extended infinitely, if maxdistance equals 0 (default), otherwise set maxdistance to how ever far you want the ray to extend to. If the ray starts inside the poly then result.rayorigininside will be set to true.

Method Rotate(_angle:Float)
Description	Rotate the polygon.
Information	This will rotate the polygon by the given amount.

Method SetAngle(_angle:Float)
Description	Set the angle of the polygon.
Information	This will adjust the angle of the polygon by the given amount.

Method SetScale(x:Float, y:Float)
Description	Set the scale of the Polygon.
Information	This sets scale of the polygon.

Type tlQuadTree

Description

Quadtree type for managing a quadtree.

Information

Rather then go on about what a quadtree is, here's some useful resources I used myself to find out about them: http://en.wikipedia.org/wiki/Quadtree, http://www.kyleschouviller.com/wsuxna/quadtree-source-included/ and http://www.heroicvirtuecreations.com/QuadTree.html

Quadtrees vary with each implementation based on the users needs. I've tried to be flexible here with a emphasis on handling objects that will move about a lot. If an object moves within a quadtree then it will generally have to be re-added to the quadtree, so I've implemented that possibility here. Thankfully there's no need to rebuild the quadtree every time an object moves, the object just removes and adds itself back to the tree, and it will only do it if it's moved outside of it's containing tlQuadTreeNode.

When I say object, I mean a tlBox, which is a simple axis aligned bounding box type that can be added to the quadtree, the more complex tlCircle, tlLine and tlPolygon which extend tlBox can also be added, but the quadtree will only concern itself with bounding boxes when a query is made on the quadtree.

Using the quadtree is simple enough, create a new quadtree with whatever dimensions you want and then use AddBox to add bounding boxes to it. In your main loop you might want to put RunQuadtreeMaintenance which tidies up the quadtree by finding empty partitions and deleting them. Of course the whole point of a quadtree is to find out which objects are within a particular area so that you can do collision checking, rendering, updating or whatever. To do that, you can query the quadtree by simply calling either QueryQuadtreeArea or QueryQuadtreeBox which will run a callback function of your choice to perform your specific tasks on them. There's also queries available to check for objects within a radius by using, QueryQuadtreeRange and QueryQuadtreeCircle, and also for lines and rays using QueryQuadtreeEdge, QueryQuadtreeLine and QueryQuadtreeRay.

Here is a list of the query functions you can use to query the quadtree, along with the type of callback function you'll need to create to handle the results of each query:

QueryQuadtreeArea / QueryQuadtreeBox	For querying the quadtree with a rectangular area. All objects within the area will be passed through to a callback function that needs the following parameters: Callback(ObjectFoundInQuadtree:object, Data:object) You don't have to use those exact variable names, just as long as the 2 variables are objects.
QueryQuadtreeRange / QueryQuadtreeCircle	For querying the quadtree with a specific radius. All objects within the radius will be passed through to the call back function: Callback(ObjectFoundInQuadtree:object, Data:object)
QueryQuadtreeRay	This is for casting a ray from any point and doing a callback on the first object that is hit. The callback differs slightly in that the results of the ray collision are passed through to the callback aswell. This is because the collision check vs the ray has to be done during the query, so there is no need to do any further ray checks in your callback. The callback should look like this: Callback(ObjectFoundInQuadtree:object, Data:object, Result:tlCollisionResult)
QueryQuadtreeEdge / QueryQuadtreeLine	This is for querying the QuadTree with a line. Every object in the Quadtree that collides with the line is passed To the callback function, and like the ray query, the collision result is also passed through too: Callback(ObjectFoundInQuadtree:object, Data:object, Result:tlCollisionResult)

Implementing this quadtree within your game will probably involve including tlBox, tlCircle, tlLine or tlPolygon as a field within your entity/actor etc types. When your actors move about, just make sure you update the position of the Box as well using SetBoxPosition or MoveBox. When this happens all the necessary updating of the quadtree will happen automatically behind the scenes. Be aware that if an object moves outside of the quadtree bounds it will drop out of the quadtree.

FAQ:

What happens when a object overlaps more then one quadtreenode?

The object is added to each node it overlaps. No object will ever be added to a node that has children, they will be moved down the quadtree to the bottom level of that branch.

What happens when an object is found more then once because it is contained within more than 1 node?

tlBoxs are aware if they have already been found and a callback has been made within the same search, so a callback will never be made twice on the same search query.

What happens if a node no longer contains more then the maximium allowed for a node, are it's objects moved back up the tree?

No, onced a node is partioned and objects moved down, they're there to stay, however if you RunQuadtreeMaintenance then empty nodes will be unpartitioned. I didn't think it was worth the overhead to worry about moving objects back up the tree again.

What collision checking is done when calling, for example, QueryQuadtreeArea?

The quadtree will just concern itself with doing callbacks on objects it finds with rect->rect collision in the case of QueryQuadtreeArea, and circle->rect collision in the case of QueryQuadtreeRange. Once you've found those objects you can then go on and do more complex collision checking such as poly->poly. If however you only need to check for rect->rect then you can assume a hit straight away as the quadtree will only callback actual hits, potential hits are already excluded automatically if their bounding box is outside the area being queried.

What are potential hits?

A potential hit would be an object in the same quadtree node that the area check overlaps. So if the area you're checking a collision for overlaps 2 quadnodes, all the objects in those 2 nodes would be considered potential hits. I decided that I may aswell cull any of those bounding boxes that don't overlap the area being checked before doing the callback so that the amount of potential hits is reduced further, and to save wasting the time doing it in the callback function. This applies to both QueryQuadtreeArea and QueryQuadtreeRange functions, but as mentioned before, it will only cull according to bounding boxes, you'll have to do a further check in your callback to manage the more complex poly->poly, poly->rect etc., collisions.

If I have to use a callback function, how can I do stuff with an object without resorting to globals?

When you run a QueryQuadtreeArea (of any type) you can pass an object that will be passed through to the callback function. So the call back function you create should look like:

Function MyCallBackFunction(ObjectFoundInQuadtree:Object, MyData:object)

So your data could be anything such as a bullet or player ship etc., and assuming that object has a tlBox field you can do further collision checks between the 2. If you don't need to pass any data then just leave it null.

How do I know what kind of tlBox has been passed back from from the quadtree?

tlBoundaries have a field called collisiontype which you can find out by calling GetCollisionType. This will return either tlBOX_COLLISION, tlCIRCLE_COLLISION, tlPOLY_COLLISION or tlLINE_COLLISION. The chances are though, that you won't need to know the type, as a call to CheckCollision will automatically determine the type and perform the appropriate collision check.

Can I have more then one quadtree

Yes you can create as many quadtrees as you want, however, bear in mind that a tlBox can only ever exist in 1 quadtree at a time. I most cases, with the use of layers, 1 quadtree will probably be enough.

Example

SuperStrict

Import rigz.collision

SetGraphicsDriver GLMax2DDriver()

Graphics 1024, 768

'Create our quadtree. Here we're allowing for 5 levels of subdivision and upto 20 objects before subdividing
'a quadtree node
Local QTree:tlQuadTree = CreateQuadtree(0, 0, GraphicsWidth() , GraphicsHeight(), 5, 20)

'Populate the quadtree with a bunch of objects
For Local c:Int = 1 To 1000
	Local t:Int = Rnd(3)
	Local rect:tlBox
	Select t
		Case 0
			'Create a Basic bounding box boundary
			rect = CreateBox(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), 10, 10, tlLAYER_1)
		Case 1
			'Create a circle Boundary
			rect = CreateCircle(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), 5, tlLAYER_2)
		Case 2
			'Create a polygon boundary
			Local verts:Float[] = [- 10.0, -10.0, -15.0, 0.0, -10.0, 10.0, 10.0, 10.0, 15.0, 0.0, 10.0, -10.0]
			rect = CreatePolygon(Rnd(GraphicsWidth()), Rnd(GraphicsHeight()), verts, tlLAYER_3)
	End Select
	'Add the boundary to the quadtree
	AddBoundaryToQuadtree(QTree, rect)
Next

'Create a circle that we can move about the screen with the mouse
Local player:tlBox = CreateBox(0, 0, 50, 50)

While Not KeyDown(KEY_ESCAPE)
	
	Cls
	
	'Update the position of the mouse controlled boundary poly
	SetBoundaryPosition(player, MouseX(), MouseY())
	
	'If the space is pressed then query the quadtree to do a callback on all 
	'the objects on the screen. You could use something similar to cull all 
	'off screen objects
	If KeyDown(KEY_SPACE) QueryQuadtreeArea(QTree, 0, 0, GraphicsWidth(), GraphicsHeight(), Null, RenderScreen, tlLAYER_ALL)
	
	'Query the quadtree with our poly and pass the callback where we can check 
	'for collisions with the potential hits the quadtree finds
	QueryQuadtreeBox(QTree, player, player, MyCallback)
	
	'Draw the quadtree, just to show you how it partitions space
	SetColor 128, 128, 128
	QTree.Draw()

	'Draw the player circle
	SetColor 255, 255, 255
	player.draw()
	
	DrawText "Hold space to render the whole screen", 10, 10
	
	Flip 1

Wend

'Our first callback function which is called when space is pressed and objects are found within the screen space
Function RenderScreen(o:Object, data:Object)
	'use casting to create the local rect
	Local rect:tlBox = tlBox(o)
	'and draw it
	SetColor 255, 255, 255
	rect.draw()
End Function

'This callback is called when the quadtree finds objects within the bounding box of our poly
Function MyCallback(o:Object, data:Object)
	'Use casting to create a local rect of whatever boundary object the quad tree has found.
	'This could be either a tlBoundary, tlBoundaryCircle, tlBoundaryLine or tlBoundaryPoly
	Local rect:tlBox = tlBox(o)
	'We used the data variable to pass the poly we're using to move around the screen. This could be
	'any object, such as a game entity, which could have a field containing a tlBoundary representing
	'its bounding box/poly etc.
	Local player:tlBox = tlBox(data)
	'Do a collision check and store the result
	Local collisionresult:tlCollisionResult = CheckCollision(player, rect)
	If collisionresult.intersecting = True
		If rect.collisiontype = tlPOLY_COLLISION
			tlPolygon(rect).Rotate(1)
		End If
		SetColor 0, 255, 0
		rect.Draw
	End If
End Function

Methods Summary
AddBox	Add a new bounding box to the Quadtree.
Create	Create a new tlQuadTree.
Draw	Draw the quadtree.
ForEachObjectAlongLine	Query a quadtree with a tlLine.
ForEachObjectInArea	Query the Quadtree to find objects with an area.
ForEachObjectInBox	Query the quadtree to find objects within a tlBox.
ForEachObjectInBoxCircle	Query the quadtree to find objects within a tlCircle.
ForEachObjectWithinRange	Query the quadtree to find objects within a certain radius.
GetObjectsFound	Find out how many objects were found on the last query.
GetTotalObjects	Find out how many objects are currently in the quadtree.
RayCast
RunMaintenance	Perform some house keeping on the quadtree.

Method AddBox:Int(r:tlBox)
Returns	False if the box doesn't overlap the qaudtree, otherwise True.
Description	Add a new bounding box to the Quadtree.
Information	A quadtree isn't much use without any objects. Use this to add a tlBox to the quadtree. If the bounding box does not overlap the quadtree then null is returned.

Method Create:tlQuadTree(x:Float, y:Float, w:Float, h:Float, _maxlevels:Int = 4, _maxpernode:Int = 4)
Returns	A new quadtree.
Description	Create a new tlQuadTree.
Information	Creates a new quad tree with the coordinates and dimensions given. _maxlevels determines how many times the quadtree can be sub divided. A quadtreenode is only subdivided when a certain amount of objects have been added, which is set by passing _maxpernode. There's no optimum values for these, it largely depends on your specific needs, so you will probably do well to experiment.

Method Draw(offsetx:Float = 0, offsety:Float = 0)
Description	Draw the quadtree.
Information	This can be used for debugging purposes. Warning: This will be very slow if the quadtree has more then 6 or 7 levels!

Method ForEachObjectAlongLine:Int(line:tlLine, data:Object, callback:Int(ReturnedObject:Object, Data:Object, Result:tlCollisionResult), Layer:Int = tlLAYER_ALL)
Returns	False if the line did not touch anything, otherwise True.
Description	Query a quadtree with a tlLine.
Information	This will query the quadtree with a line and perform a callback on all the objects the tlLine intersects. Pass the quadtree to do the query on, the tlLine to query with, an object you want to pass through to the callback, and the callback itself. It's worth noting that the callback also requires you have a tlCollisionResult parameter which will be passed to the callback function with information about the results of the raycast.

Method ForEachObjectInArea(x:Float, y:Float, w:Float, h:Float, Data:Object, callback:Int(ReturnedObject:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query the Quadtree to find objects with an area.
Information	When you want to find objects within a particular area of the quadtree you can use this method. Pass the area coordinates and dimensions that you want to check, an object that can be anything that you want to pass through to the callback function, and the function callback that you want to perform whatever tasks you need on the objects that are found within the area. The callback function you create needs to have 2 parameters: ReturnedObject:object which will be the tlBox/circle/poly, and Data:object which can be and object you want to pass through to the call back function.

Method ForEachObjectInBox(area:tlBox, Data:Object, callback:Int(o:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query the quadtree to find objects within a tlBox.
Information	This does the same thing as ForEachObjectInArea except you can pass a tlBox instead to query the quadtree.

Method ForEachObjectInBoxCircle(circle:tlCircle, Data:Object, callback:Int(ReturnedObject:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query the quadtree to find objects within a tlCircle.
Information	This will query the quadtree and do a callback on any objects it finds within the given tlCircle.

Method ForEachObjectWithinRange(x:Float, y:Float, radius:Float, Data:Object, callback:Int(ReturnedObject:Object, Data:Object), Layer:Int = tlLAYER_ALL)
Description	Query the quadtree to find objects within a certain radius.
Information	This will query the quadtree and do a callback on any objects it finds within a given radius.

Method GetObjectsFound:Int()
Returns	Number of objects found.
Description	Find out how many objects were found on the last query.
Information	Use this to retrieve the amount of object that were found when the last query was run.

Method GetTotalObjects:Int()
Returns	Number of Total Objects in Tree.
Description	Find out how many objects are currently in the quadtree.
Information	Use this to retrieve the total amount of objects that are stored in the quadtree.

Method RayCast:Int(px:Float, py:Float, dx:Float, dy:Float, maxdistance:Float = 0, Data:Object, callback:Int(ReturnedObject:Object, Data:Object, Result:tlCollisionResult), Layer:Int = tlLAYER_ALL)

Method RunMaintenance()
Description	Perform some house keeping on the quadtree.
Information	This will search the quadtree tree for any empty tlQuadTreeNodes and unpartition them if necessary.

Type tlQuadTreeNode
Description	tlQuadTreeNode type for containing objects within the QuadTree.
Information	This type is use internally by tlQuadTree so you shouldn't have to worry about it.

Methods Summary
Create	Create a new tlQuadTreeNode.

Method Create:tlQuadTreeNode(x:Float, y:Float, w:Float, h:Float, _parenttree:tlQuadTree, parentnode:tlQuadTreeNode = Null, gridref:Int = -1)
Description	Create a new tlQuadTreeNode.
Information	This will create a new node within the quad tree. You shouldn't have to worry about this, as it's performed automatically as objects are added to the quadtree.

Module Information

Author	Peter J. Rigby
Copyright	Peter J. Rigby 2009
Purpose	Provide a way of testing for collisions between boxes, circles, polygons and lines with the added option of using quadtrees
Version	1.01
History	20.06.10 - Fixed a bug with velocity not being taken into account after querying a quadtree which was causing tunnelling to occurr.
History	06.01.10 - Initial Release