Libraries.Game.Collision.DynamicBoundingVolumeTree2D Documentation

DynamicBoundingVolumeTree2D is the tree structure for storing the bounding boxes for collidable Item2D objects. The tree is a complete binary tree and stores the bounding boxes in a hierarchal structure with the parent node containing a bounding box that bounds the bounding boxes of both of its children. This class is used internally by BroadphaseCollision2D.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
use Libraries.Game.Collision.BoundingBox2D
use Libraries.Game.Collision.Item2DNode

    DynamicBoundingVolumeTree2D tree
    BoundingBox2D boundingBox1
    BoundingBox2D boundingBox2

    Item2DNode item1
    Item2DNode item2
    
    integer id1 = tree:CreateNode(boundingBox1, item1)
    integer id2 = tree:CreateNode(boundingBox2, item2)
    output "Tree has height " + tree:GetHeight()

    tree:DestroyNode(id2)
    output "After removing node 2 , tree has height " + tree:GetHeight()

Inherits from: Libraries.Language.Object

Summary

Variable Summary Table

VariablesDescription
integer NULL_NODE

Actions Summary Table

ActionsDescription
Compare(Libraries.Language.Object object)This action compares two object hash codes and returns a CompareResult.
ComputeHeight()This action computes the height of the tree
CreateNode(Libraries.Game.Collision.BoundingBox2D boundingBox, Libraries.Game.Collision.Item2DNode node)This action creates a new node for the Dynamic Bounding Volume Tree with the given BoundingBox and given Item and inserts the new node as a leaf in the tree.
DestroyNode(integer nodeID)This action removes from the Dynamic Bounding Volume Tree the node with the given node ID.
DestroyNode(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node)This action removes the given node from the tree.
Equals(Libraries.Language.Object object)This action determines if two objects are equal based on their hash code values.
GetBoundingBox(integer nodeID)This action returns the bounding box contained in the tree node with the given ID.
GetBoundingBox(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node)This action returns the bounding box contained in the given tree node.
GetHashCode()This action gets the hash code for an object.
GetHeight()This action returns the height of the tree
GetItemNode(integer nodeID)This action returns the Item2DNode contained in the tree node with the given ID This is an internal action.
GetItemNode(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node)This action returns the Item2Dcontained in the given tree node This action is used internally
GetMaximumBalance()This action computes the maximum balance of the tree.
GetNodeCount()This action returns the number of nodes in the DynamicBoundingVolumeTree2D.
GetPerimeterRatio()This action computes the ratio of the sum of the node perimeters to the root perimeter.
MoveNode(integer nodeID, Libraries.Game.Collision.BoundingBox2D boundingBox, Libraries.Compute.Vector2 displacement)This action moves the Item2DNode contained in the node with the given node ID by the given displacement vector.
MoveNode(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node, Libraries.Game.Collision.BoundingBox2D boundingBox, Libraries.Compute.Vector2 displacement)This action moves the object.
Query(Libraries.Game.Collision.BroadphaseCollision2D broadphase, Libraries.Game.Collision.BoundingBox2D boundingBox)This action queries the tree for bounding boxes that overlap with the given bounding box and returns all leafs whose bounding boxes intersect the given bounding box in a list.

Actions Documentation

Compare(Libraries.Language.Object object)

This action compares two object hash codes and returns a CompareResult. The compare result is either larger if this hash code is larger than the object passed as a parameter, smaller, or equal.

Example Code

use Libraries.Language.Support.CompareResult
        Object o
        Object t
        CompareResult result = o:Compare(t)

Parameters

Return

Libraries.Language.Support.CompareResult: The Compare result, Smaller, Equal, or Larger.

ComputeHeight()

This action computes the height of the tree

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)
        output "Tree has height " + tree:ComputeHeight()

        tree:DestroyNode(id2)
        output "After removing node 2 , tree has height " + tree:ComputeHeight()

Return

integer: the height of the tree

CreateNode(Libraries.Game.Collision.BoundingBox2D boundingBox, Libraries.Game.Collision.Item2DNode node)

This action creates a new node for the Dynamic Bounding Volume Tree with the given BoundingBox and given Item and inserts the new node as a leaf in the tree. This action is used internally.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox

        Item2DNode item

        output "This item was added to node number " + tree:CreateNode(boundingBox, item)

Parameters

Return

integer: The integer id of the new tree node

DestroyNode(integer nodeID)

This action removes from the Dynamic Bounding Volume Tree the node with the given node ID. This action is used internally.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox

        Item2DNode item
        integer id = tree:CreateNode(boundingBox, item)
        output "This item was added to node number " + id

        tree:DestroyNode(id)
        output "Node number " + id + " was removed from the tree."

Parameters

DestroyNode(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node)

This action removes the given node from the tree. Only leaf nodes will be removed. This action is used internally.

Parameters

Equals(Libraries.Language.Object object)

This action determines if two objects are equal based on their hash code values.

Example Code

use Libraries.Language.Object
        use Libraries.Language.Types.Text
        Object o
        Text t
        boolean result = o:Equals(t)

Parameters

Return

boolean: True if the hash codes are equal and false if they are not equal.

GetBoundingBox(integer nodeID)

This action returns the bounding box contained in the tree node with the given ID. Note that this bounding box is slightly larger than the bounding box of the item contained in this node. This action is used internally.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)

        BoundingBox2D result
        result = tree:GetBoundingBox(id2)

Parameters

Return

Libraries.Game.Collision.BoundingBox2D: the specified BoundingBox2D

GetBoundingBox(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node)

This action returns the bounding box contained in the given tree node. Note that this bounding box is slightly larger than the bounding box of the item contained in this node. This action is used internally.

Parameters

Return

Libraries.Game.Collision.BoundingBox2D: the specified BoundingBox2D

GetHashCode()

This action gets the hash code for an object.

Example Code

Object o
        integer hash = o:GetHashCode()

Return

integer: The integer hash code of the object.

GetHeight()

This action returns the height of the tree

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)
        output "Tree has height " + tree:GetHeight()

        tree:DestroyNode(id2)
        output "After removing node 2 , tree has height " + tree:GetHeight()

Return

integer: the height of the tree

GetItemNode(integer nodeID)

This action returns the Item2DNode contained in the tree node with the given ID This is an internal action.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)

        Item2DNode result
        result = tree:GetItemNode(id2)

Parameters

Return

Libraries.Game.Collision.Item2DNode: The specified Item2DNode

GetItemNode(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node)

This action returns the Item2Dcontained in the given tree node This action is used internally

Parameters

Return

Libraries.Game.Collision.Item2DNode: The specified Item2DNode

GetMaximumBalance()

This action computes the maximum balance of the tree. The maximum balance is the maximum difference of the heights of the two children of any node. Attributes: Returns the maximum balance of the tree Atributes: Example use Libraries.Game.Collision.DynamicBoundingVolumeTree2D use Libraries.Game.Collision.BoundingBox2D use Libraries.Game.Collision.Item2DNode DynamicBoundingVolumeTree2D tree BoundingBox2D boundingBox1 BoundingBox2D boundingBox2 BoundingBox2D boundingBox3 Item2DNode item1 Item2DNode item2 Item2DNode item3 integer id1 = tree:CreateNode(boundingBox1, item1) integer id2 = tree:CreateNode(boundingBox2, item2) integer id3 = tree:CreateNode(boundingBox3, item3) output "Tree has maximum balance " + tree:GetMaximumBalance()

Return

integer:

GetNodeCount()

This action returns the number of nodes in the DynamicBoundingVolumeTree2D. This action is used internally.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)

        output "The tree has " + tree:GetNodeCount() + " nodes."

Return

integer: the number of nodes in the DynamicBoundingVolumeTree2D

GetPerimeterRatio()

This action computes the ratio of the sum of the node perimeters to the root perimeter.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode
    use Libraries.Compute.Vector2

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Vector2 minimum1
        Vector2 minimum2
        Vector2 maximum1
        Vector2 maximum2

        minimum1:Set(0, 0)
        minimum2:Set(0.5, 0.5)
        maximum1:Set(1, 1)
        maximum2:Set(1.5, 1.5)
        boundingBox1:Set(minimum1, maximum1)
        boundingBox2:Set(minimum2, maximum2)

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)
    
        output "The perimeter ratio is " + tree:GetPerimeterRatio()

Return

number: the perimeterRatio of the tree

MoveNode(integer nodeID, Libraries.Game.Collision.BoundingBox2D boundingBox, Libraries.Compute.Vector2 displacement)

This action moves the Item2DNode contained in the node with the given node ID by the given displacement vector. If the node moves outside of its existing bounding box, then the object is removed from the tree, a new bounding box is calculated, and it is reinserted into the tree. Otherwise, the node is left where it is in the tree. This action is used internally.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode
    use Libraries.Compute.Vector2

        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox
        Vector2 displacement

        Item2DNode item
        integer id = tree:CreateNode(boundingBox, item)
        output "This item was added to node number " + id

        displacement:Set(1, 5)
        if not tree:MoveNode(id, boundingBox, displacement)
            output "The item in node number " + id + " did not need reinserted"
        end

Parameters

Return

boolean: whether the item was removed and reinserted into the tree

MoveNode(Libraries.Game.Collision.DynamicBoundingVolumeTreeNode2D node, Libraries.Game.Collision.BoundingBox2D boundingBox, Libraries.Compute.Vector2 displacement)

This action moves the object. If the object moves outside of its existing big bounding box, then the object is removed from the tree, a new bounding box is calculated, and it is reinserted into the tree. Otherwise, the action returns immediately.

Parameters

Return

boolean: Whether the item is reinserted into the tree

Query(Libraries.Game.Collision.BroadphaseCollision2D broadphase, Libraries.Game.Collision.BoundingBox2D boundingBox)

This action queries the tree for bounding boxes that overlap with the given bounding box and returns all leafs whose bounding boxes intersect the given bounding box in a list.

Example Code

use Libraries.Game.Collision.DynamicBoundingVolumeTree2D
    use Libraries.Game.Collision.BoundingBox2D
    use Libraries.Game.Collision.Item2DNode
    use Libraries.Compute.Vector2
    use Libraries.Game.Collision.BroadphaseCollision2D

        BroadphaseCollision2D broadphase
        DynamicBoundingVolumeTree2D tree
        BoundingBox2D boundingBox1
        BoundingBox2D boundingBox2

        Vector2 minimum1
        Vector2 minimum2
        Vector2 maximum1
        Vector2 maximum2

        minimum1:Set(-1,-1)
        minimum2:Set(-2, -2)
        maximum1:Set(0, 0)
        maximum2:Set(-1, -1)
        boundingBox1:Set(minimum1, maximum1)
        boundingBox2:Set(minimum2, maximum2)

        Item2DNode item1
        Item2DNode item2

        integer id1 = tree:CreateNode(boundingBox1, item1)
        integer id2 = tree:CreateNode(boundingBox2, item2)

        output "The tree has " + tree:GetNodeCount() + " nodes."

        BoundingBox2D overlap
        Vector2 minimumOverlap
        Vector2 maximumOverlap
        minimumOverlap:Set(-1.5, -1.5)
        maximumOverlap:Set(-0.5, -0.5)
        overlap:Set(minimumOverlap, maximumOverlap)

        tree:Query(broadphase, overlap)

Parameters