DynamicTree <T>

The DynamicTrees provides a spatial partitioning data structure for quickly querying for overlapping bounding boxes for all tracked bodies. The worst case performance of this is O(n*log(n)) where n is the number of bodies in the tree.

Internally the bounding boxes are organized as a balanced binary tree of bounding boxes, where the leaf nodes are tracked bodies. Every non-leaf node is a bounding box that contains child bounding boxes.

Index

Constructors

• constructor

Properties

• nodes
• root
• worldBounds

Methods

• debug
• getHeight
• getNodes
• query
• rayCastQuery
• trackCollider
• untrackCollider
• updateCollider

Constructors

constructor

• new DynamicTree<T>(_config: Required<{ boundsPadding?: number; velocityMultiplier?: number }>, worldBounds?: BoundingBox): DynamicTree<T>

• Type parameters

  • T: ColliderProxy<Entity<any>>

  Parameters

  • _config: Required<{ boundsPadding?: number; velocityMultiplier?: number }>

  • worldBounds: BoundingBox = ...

  Returns DynamicTree<T>

Properties

publicnodes

nodes: {}

Type declaration

• [key number]: TreeNode<T>

publicroot

root: TreeNode<T>

publicworldBounds

worldBounds: BoundingBox = ...

Methods

publicdebug

• debug(ex: ExcaliburGraphicsContext): void

• Parameters

  • ex: ExcaliburGraphicsContext

  Returns void

publicgetHeight

• getHeight(): number

• Returns the internal height of the tree, shorter trees are better. Performance drops as the tree grows

  ---

  Returns number

publicgetNodes

• getNodes(): TreeNode<T>[]

• Returns TreeNode<T>[]

publicquery

• query(collider: T, callback: (other: T) => boolean): void

• Queries the Dynamic Axis Aligned Tree for bodies that could be colliding with the provided body.

  In the query callback, it will be passed a potential collider. Returning true from this callback indicates that you are complete with your query and you do not want to continue. Returning false will continue searching the tree until all possible colliders have been returned.

  ---

  Parameters

  • collider: T

  • callback: (other: T) => boolean

  Returns void

publicrayCastQuery

• rayCastQuery(ray: Ray, max?: number, callback: (other: T) => boolean): void

• Queries the Dynamic Axis Aligned Tree for bodies that could be intersecting. By default the raycast query uses an infinitely long ray to test the tree specified by max.

  In the query callback, it will be passed a potential body that intersects with the raycast. Returning true from this callback indicates that your are complete with your query and do not want to continue. Return false will continue searching the tree until all possible bodies that would intersect with the ray have been returned.

  ---

  Parameters

  • ray: Ray

  • max: number = Infinity

  • callback: (other: T) => boolean

  Returns void

publictrackCollider

• trackCollider(collider: T): void

• Tracks a body in the dynamic tree

  ---

  Parameters

  • collider: T

  Returns void

publicuntrackCollider

• untrackCollider(collider: T): void

• Untracks a body from the dynamic tree

  ---

  Parameters

  • collider: T

  Returns void

publicupdateCollider

• updateCollider(collider: T): boolean

• Updates the dynamic tree given the current bounds of each body being tracked

  ---

  Parameters

  • collider: T

  Returns boolean