Simple QuadTree implementation to assist with broad-phase 2D collisions.
Static methods
staticinlineget(x:Float = 0, y:Float = 0, width:Float = 1, height:Float = 1):QuadTree
Gets an Quadtree from the pool, or creates a new one if none are available. Call put()
on the Quadtree to place it back in the pool.
Note - The X and Y positions represent the center of the Quadtree. To set the Quadtree from its Top-Left origin, Quadtree.get_from_min_max()
is available.
Parameters:
x | The centered X position of the Quadtree. |
---|---|
y | The centered Y position of the Quadtree. |
width | The width of the Quadtree. |
height | The height of the Quadtree. |
Returns:
Quadtree
Variables
children:Vector<QuadTree>
The child QuadTrees contained in the Quadtree. If this Vector is empty, the Quadtree is regarded as a leaf
.
contents:Array<QuadTreeData>
The QuadTreeData contained in the Quadtree. If the Quadtree is not a leaf
, all of it's contents will be dispersed to it's children QuadTrees (leaving this aryar emyty).
read onlycount:Int
Gets the total amount of QuadTreeData
contents in the Quadtree, recursively. To get the non-recursive amount, check quadtree.contents_count
.
read onlyleaf:Bool
A QuadTree is regarded as a leaf
if it has no QuadTree children (ie quadtree.children.length == 0
).
max_contents:Int = 10
The maximum amount of QuadTreeData
contents that a QuadTree leaf
can hold before becoming a branch and splitting it's contents between children Quadtrees.
Methods
insert(data:QuadTreeData):Void
Attempts to insert the QuadTreeData
into the QuadTree. If the QuadTreeData
already exists in the QuadTree, use quadtree.update(data)
instead.
query(aabb:AABB, result:Array<QuadTreeData>):Void
Queries the QuadTree for any QuadTreeData
that overlaps the AABB
.
Parameters:
aabb | The |
---|---|
result | An Array containing all |
remove(data:QuadTreeData, allow_shake:Bool = true):Bool
Attempts to remove the QuadTreeData
from the QuadTree.
shake():Bool
If the QuadTree is a branch (not a leaf
), this will check if the amount of data from all the child Quadtrees can fit in the Quadtree without exceeding it's max_contents
.
If all the data can fit, the Quadtree branch will "shake" its child Quadtrees, absorbing all the data and clearing the children (putting all the child Quadtrees back in the pool).
Note - This works recursively.
update(data:QuadTreeData, allow_shake:Bool = true):Void
Updates the QuadTreeData
in the QuadTree by first removing the QuadTreeData
from the QuadTree, then inserting it.
Parameters:
null | data |
---|