rigz.collision: | Functions | Types | Modinfo | Source |
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.
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. |
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. |
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. |
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 | 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) |
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:
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. |
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 |