QuadTree

View source
arcade.QuadTree (Class)

A QuadTree implementation. The original code was a conversion of the Java code posted to GameDevTuts. However I've tweaked it massively to add node indexing, removed lots of temp. var creation and significantly increased performance as a result. Original version at https://github.com/timohausmann/quadtree-js/

Instance Members

arcade
busy: Bool

A flag used to know if this quad tree is currently busy and should not be used by something else.

arcade
maxObjects: Int

The maximum number of objects per node.

arcade
maxLevels: Int

The maximum number of levels to break down to.

arcade
level: Int

The current level.

arcade
boundsX: Float

The x position of the quadtree bounds.

arcade
boundsY: Float

The y position of the quadtree bounds.

arcade
boundsWidth: Float

The width of the quadtree bounds.

arcade
boundsHeight: Float

The height of the quadtree bounds.

arcade
boundsSubWidth: Float

The sub-width of the quadtree bounds.

arcade
boundsSubHeight: Float

The sub-height of the quadtree bounds.

arcade
boundsRight: Float

The right edge of the quadtree bounds.

arcade
boundsBottom: Float

The bottom edge of the quadtree bounds.

arcade
objects: Array<Body>

Array of quadtree children.

arcade
nodes: Array<QuadTree>

Array of associated child nodes.

arcade
recycle(): Void
arcade
reset(x: Float, y: Float, width: Float, height: Float, ?maxObjects: Int = 10, ?maxLevels: Int = 4, ?level: Int = 0): Void

Resets the QuadTree.

Name Type Default Description
x Float The top left coordinate of the quadtree.
y Float The top left coordinate of the quadtree.
width Float The width of the quadtree in pixels.
height Float The height of the quadtree in pixels.
maxObjects Int 10 The maximum number of objects per node.
maxLevels Int 4 The maximum number of levels to iterate to.
level Int 0 Which level is this?
arcade
populate(group: Group): Void

Populates this quadtree with the children of the given Group. In order to be added the child must exist and have a body property.

Name Type Description
group Group The Group to add to the quadtree.
arcade
split(): Void

Split the node into 4 subnodes

arcade
insert(body: Body): Void

Insert the object into the node. If the node exceeds the capacity, it will split and add all objects to their corresponding subnodes.

Name Type Description
body Body The Body object to insert into the quadtree.
arcade
getIndex(left: Float, top: Float, right: Float, bottom: Float): Int

Determine which node the object belongs to.

Name Type Description
left Float The left edge of the bounds to check.
top Float The top edge of the bounds to check.
right Float The right edge of the bounds to check.
bottom Float The bottom edge of the bounds to check.
Returns Description
Int Index of the subnode (0-3), or -1 if rect cannot completely fit within a subnode and is part of the parent node.
arcade
retrieve(left: Float, top: Float, right: Float, bottom: Float): Array<Body>

Return all objects that could collide with the given bounds.

Name Type Description
left Float The left edge of the bounds to check.
top Float The top edge of the bounds to check.
right Float The right edge of the bounds to check.
bottom Float The bottom edge of the bounds to check.
Returns Description
Array<Body> Array with all detected objects.
arcade
clear(): Void

Clear the quadtree.

arcade
new(?pool: QuadTreePool, x: Float, y: Float, width: Float, height: Float, ?maxObjects: Int = 10, ?maxLevels: Int = 4, ?level: Int = 0): Void
Name Type Default
pool QuadTreePool (optional)
x Float
y Float
width Float
height Float
maxObjects Int 10
maxLevels Int 4
level Int 0

Private Members