rigz.collision: Functions Types Modinfo Source  

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)
ReturnsFalse if the box doesn't overlap the quadtree, otherwise True.
DescriptionAdd a new bounding box to the Quadtree.
InformationA 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)
ReturnstlCollisionResult.
DescriptionCheck for a collision between 2 Boundaries.
InformationYou 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)
ReturnstlCollisionResult with the results of the collision.
DescriptionSee if a ray collides with a boundary.
InformationYou 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)
ReturnsNew tlBox.
DescriptionCreate a new tlBox.
InformationCreates 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)
ReturnsNew tlLine.
DescriptionCreate a tlLine.
InformationCreate 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)
ReturnsNew tlCircle.
DescriptionCreate a tlCircle.
InformationCreate 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)
ReturnsNew tlPolygon, or Null if verts[] contained the wrong amount.
DescriptionCreate a tlPolygon.
InformationCreate 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)
ReturnsA new tlQuadtree.
DescriptionCreate a new tlQuadTree.
InformationCreates 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)
DescriptionGet the data assigned to a boundary.
InformationUse this to retrieve the custom data you have assign to a boundary.

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

Function GetQuad:Int(axis_x:Float, axis_y:Float, vert_x:Float, vert_y:Float)
DescriptionGet the quad a vertex lies within.
InformationThis 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)
ReturnsNew tlVector2 with the resulting rebound vector, or v, if there was nothing to rebound.
DescriptionGet the rebound vector.
InformationWhen 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)
ReturnsThe amount of overlap. Any value less then 0 is not overlapping.
DescriptionFind 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)
ReturnsTrue if lines overlap.
DescriptionDo a Line to Line collision check.
Informationx0, 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)
ReturnsTrue if lines overlap, and Sets X_Point and Y_Point to the point of interection.
DescriptionDo a Line to Line collision check and return the point of intersection.
Informationx0, 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)
ReturnsTrue if line and circle overlap.
DescriptionDo a Line to Circle collision check.
Informationx1, 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)
DescriptionMove a Boundary by a given amount.
InformationThis 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)
ReturnsNearestPoint_x and NearestPoint_y.
DescriptionReturn the nearest point on a line to the center of a circle.
Informationx1, 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)
ReturnsTrue if the point is within.
DescriptionFind out if a point is within a boundary.
InformationUse this to find out if a point at x,y falls within a tlBox, tlCircle or tlPolygon.

Function PreventOverlap(Result:tlCollisionResult, Push:Int = False)
DescriptionPrevent boundaries from overlapping, based on a tlCollisionResult.
InformationAfter 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)
DescriptionQuery a Quadtree to find objects with an area.
InformationWhen 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)
DescriptionQuery a quadtree to find objects within a tlBox.
InformationThis 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)
DescriptionQuery a quadtree to find objects within a tlCircle.
InformationThis 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)
ReturnsFalse if the line did not touch anything, otherwise True.
DescriptionQuery a quadtree with a line edge.
InformationThis 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)
ReturnsFalse if the line did not touch anything, otherwise True.
DescriptionQuery a quadtree with a tlLine.
InformationThis 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)
DescriptionQuery a quadtree to find objects within a certain radius.
InformationThis 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)
ReturnsFalse if the ray did not hit anything, otherwise True.
DescriptionQuery a quadtree with a Ray.
InformationThis 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)
DescriptionRemove a boundary from the quadtree.
InformationThis 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)
DescriptionRotate a tlPolygon.
InformationThis will rotate the polygon by the given amount.

Function RunQuadtreeMaintenance(Quadtree:tlQuadtree)
DescriptionPerform some house keeping on a quadtree.
InformationThis 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)
ReturnsTrue if they are on the same layer, otherwise false.
DescriptionFind out if 2 boundaries are on the same collision layers.

Function ScaleBoundary(Boundary:tlBox, x:Float, y:Float)
DescriptionSet the scale of a Boundary.
InformationThis 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)
DescriptionAssign an object to a boundary.
InformationThis can be handy to store extra custom info about a boundary.

Function SetBoundaryLayer(Boundary:tlBox, layer:Int)
DescriptionSet the collision layer that this boundary is on.
InformationThe 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)
DescriptionSet the position of a Boundary.
InformationSets the position of a tlBox, tlCircle or tlPolygon.

Function SetBoundaryVelocity(Boundary:tlBox, Velocity_x:Float, Velocity_y:Float)
DescriptionSet the velocity of a boundary.
InformationIt'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)
DescriptionSet the angle of a tlPolygon.
InformationThis will set the angle of a polygon to the given amount.

Function UpdateBoundaryPosition(Boundary:tlBox)
DescriptionUpdate the position of the boundary.
InformationYou 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)
ReturnsTrue if if point is withing observers fov, otherwise false.
DescriptionCheck if a point is with a field of view.

Types

Type tlBox
DescriptionType 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)
ReturnsTrue if they do overlap.
DescriptionCompare this tlBox with another to see if they overlap.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with another tlBox.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlCircle.
InformationUse 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)
ReturnsTrue if they do overlap.
DescriptionCompare this tlBox with a tlCircle.
InformationThis 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)
ReturnsNew tlBox.
DescriptionCreate a new tlBox.
InformationCreates 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)
DescriptionDraw this tlBox.
InformationUse this if you need to draw the bounding box for debugging purposes.
Method GetCollisionLayer:Int()
DescriptionGet the collision layer that this boundary is on.
Method GetCollisionType:Int()
ReturnsEither tlBOX_COLLISION, tlCIRCLE_COLLISION, tlLINE_COLLISION or tlPOLY_COLLISION.
DescriptionGet the collision type of the Box.
Informationthe collision type can help you determine what type of collision you should be performing on objects calledback from quadtree queries.
Method GetData:Object()
DescriptionGet the data assigned to this boundary.
InformationUse this to retrieve the custom data you have assign to the boundary.
Method GetShadowPolys:TList (Light:tlVector2, lType:Int = tlDIRECTIONAL_LIGHT, lengthfactor:Float = 1)
ReturnstList of tlPolygons representing each shadow cast by each line in the box.
DescriptionGet a poly represting the shadow of the box.
InformationThis 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()
ReturnsFloat with the current x coordinate.
DescriptionGet the x world coordinate of the boundary.
InformationYou 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()
ReturnsFloat with the current y coordinate.
DescriptionGet the y world coordinate of the boundary.
InformationYou 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlLine.
InformationUse 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)
DescriptionMove the bounding box by a given amount.
InformationThis 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)
ReturnsTrue if the point is within.
DescriptionFind out if a point is within the bounding box.
InformationUse this to find out if a point at x,y falls with the bounding box of this tlBox.
Method PolyCollide:tlCollisionResult(poly:tlPolygon)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlPolygon.
InformationUse 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)
DescriptionPrevent the boundary from overlapping another based on the result of a collision.
InformationWhen 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)
ReturnstlCollisionResult with the results of the collision.
DescriptionSee is a ray collides with this tlbox.
InformationYou 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)
ReturnsTrue if it is within.
DescriptionFind out if a tlBox lies within this objects bounding box.
InformationIf 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()
DescriptionRemove the tlBox from the quadtree.
InformationThis 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)
DescriptionSet the collision layer that this boundary is on.
InformationThe 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)
Method SetData(d:Object)
DescriptionAssign an object to the boundary.
InformationThis can be handy to store extra custom info about the boundary.
Method SetPosition(x:Float, y:Float)
DescriptionSet the position of the bounding box.
InformationThis 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)
DescriptionSet the scale of the Box.
InformationThis sets scale of the Box.
Method SetVelocity(Velocity_x:Float, Velocity_y:Float)
DescriptionSet the velocity of the boundary.
InformationIt'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()
DescriptionUpdate the position of the boundary.
InformationYou can use this method to update it's position according to its current velocity vector.

Type tlCircle Extends tlBox
DescriptiontlCircle for circular boundaries for collision checking.
InformationThis 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)
ReturnsTrue if they do overlap.
DescriptionCompare this tlCircle with a tlBox.
InformationThis will perfrom a simple circle to bounding box overlap check on the tlBox you pass to it.
Method BoxCollide:tlCollisionResult(Box:tlBox)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlBox.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with another tlCircle.
InformationUse 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)
ReturnsTrue if they do overlap.
DescriptionCompare this circle with another tlCircle.
InformationThis 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)
ReturnsNew tlCircle.
DescriptionCreate a tlCircle.
InformationCreate 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)
DescriptionDraw this tlBox.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlLine.
InformationUse 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)
ReturnsTrue if the point is within.
DescriptionFind out if a point is within the circle.
InformationUse this to find out if a point at x,y falls with the radius of this tlCircle.
Method PolyCollide:tlCollisionResult(poly:tlPolygon)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlPolygon.
InformationUse 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)
ReturnstlCollisionResult with the results of the collision.
DescriptionSee is a ray collides with this tlCircle.
InformationYou 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)
DescriptionSet the Box of the circle.
Informationthis lets you change the size and location of the tlCircle.

Type tlCollisionResult
DescriptionType to store the results of collisions.
InformationWhen 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()
Returnstrue if there was an intersection.
DescriptionFind out if the last collision check is intersecting.
Method GetRayDistance:Float()
Returnsfloat value of distance the ray travelled, 0 if there was no intersection.
DescriptionGet the distance from the ray origin to the instersection point.
Method GetRayIntersection:tlVector2()
Returnstlvector2.
DescriptionGet the intersection point of the raycast.
InformationIf 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()
Returnstrue if the last ray check originated inside the boundary.
DescriptionFind 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)
ReturnsNew tlVector2 with the resulting rebound vector.
DescriptionGet the rebound vector.
InformationWhen 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()
ReturnstlBox Or null if no collision occurred.
DescriptionGets the Source boundary of a collision check.
Method GetTargetBoundary:tlBox()
ReturnstlBox Or null if no collision occurred.
DescriptionGets the Target boundary of a collision check.
Method GetTranslationVector:tlVector2()
ReturnstlVector2.
DescriptionGet the translation vector of the collision.
InformationIf 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()
Returnstrue if there will be an intersection.
DescriptionFind out if the last collision check is intersecting.
Informationknowing 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
DescriptiontlLine for line collisions.
InformationThis 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlBox.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlCircle.
InformationUse 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)
ReturnsNew tlLine.
DescriptionCreate a tlLine.
InformationCreate 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with another tlLine.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlPoly.
InformationUse 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)
ReturnstlCollisionResult with the results of the collision.
DescriptionSee is a ray collides with this tlLine.
InformationYou 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
DescriptiontlPolygon for convex polygon collisions.
InformationThis 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlBox.
InformationUse 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)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlCircle.
InformationUse 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)
ReturnsNew tlPolygon, or Null if verts[] contained the wrong amount.
DescriptionCreate a tlPolygon.
InformationCreate 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)
ReturnsNew tlPolygon, or Null if verts[] contained the wrong amount.
DescriptionCreate a tlPolygon.
InformationCreate 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)
DescriptionDraw the polygon.
InformationYou can use this for debugging purposes. Pass true of false to draw the bounding box as well.
Method LineCollide:tlCollisionResult(Line:tlLine)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with a tlLine.
InformationUse 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)
ReturnsTrue if they do overlap.
DescriptionFind out if a point resides withing the tlPolygon.
InformationUse this to check if a point with the given coordinates lies within the polygon.
Method PolyCollide:tlCollisionResult(poly:tlPolygon)
ReturnstlCollisionResult type containing info about the collision.
DescriptionCheck for a collision with another tlpolygon.
InformationUse 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)
ReturnstlCollisionResult with the results of the collision.
DescriptionSee is a ray collides with this tlpolygon.
InformationYou 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)
DescriptionRotate the polygon.
InformationThis will rotate the polygon by the given amount.
Method SetAngle(_angle:Float)
DescriptionSet the angle of the polygon.
InformationThis will adjust the angle of the polygon by the given amount.
Method SetScale(x:Float, y:Float)
DescriptionSet the scale of the Polygon.
InformationThis sets scale of the polygon.

Type tlQuadTree
DescriptionQuadtree 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)
ReturnsFalse if the box doesn't overlap the qaudtree, otherwise True.
DescriptionAdd a new bounding box to the Quadtree.
InformationA 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)
ReturnsA new quadtree.
DescriptionCreate a new tlQuadTree.
InformationCreates 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)
DescriptionDraw the quadtree.
InformationThis 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)
ReturnsFalse if the line did not touch anything, otherwise True.
DescriptionQuery a quadtree with a tlLine.
InformationThis 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)
DescriptionQuery the Quadtree to find objects with an area.
InformationWhen 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)
DescriptionQuery the quadtree to find objects within a tlBox.
InformationThis 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)
DescriptionQuery the quadtree to find objects within a tlCircle.
InformationThis 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)
DescriptionQuery the quadtree to find objects within a certain radius.
InformationThis will query the quadtree and do a callback on any objects it finds within a given radius.
Method GetObjectsFound:Int()
ReturnsNumber of objects found.
DescriptionFind out how many objects were found on the last query.
InformationUse this to retrieve the amount of object that were found when the last query was run.
Method GetTotalObjects:Int()
ReturnsNumber of Total Objects in Tree.
DescriptionFind out how many objects are currently in the quadtree.
InformationUse 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()
DescriptionPerform some house keeping on the quadtree.
InformationThis will search the quadtree tree for any empty tlQuadTreeNodes and unpartition them if necessary.

Type tlQuadTreeNode
DescriptiontlQuadTreeNode type for containing objects within the QuadTree.
InformationThis 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)
DescriptionCreate a new tlQuadTreeNode.
InformationThis 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

AuthorPeter J. Rigby
CopyrightPeter J. Rigby 2009
PurposeProvide a way of testing for collisions between boxes, circles, polygons and lines with the added option of using quadtrees
Version1.01
History20.06.10 - Fixed a bug with velocity not being taken into account after querying a quadtree which was causing tunnelling to occurr.
History06.01.10 - Initial Release