quadtree

Fast Quad-Tree 2D collision detection library, supporting all convex polygons.


Keywords
collision, detection, quad, quadtree, tree
License
MIT
Install
haxelib install quadtree 0.3.3

Documentation

Quadtree pipeline status coverage report license release

Fast, otpimized and configurable collision-detection library with Quad Trees. Efficient implementation of the GJK algorithm to support any convex polygon shape, with separate faster handling of specialized cases like between rectangles and points.

Installation

$ haxelib install quadtree

Usage

Colliding object types

Objects that will be checked for collisions, should implement one of the following interfaces:

  • Point
  • Rectangle
  • MovingPoint
  • MovingRectangle
  • Polygon
  • Circle
import quadtree.CollisionAreaType;
import quadtree.types.Collider;
import quadtree.types.Rectangle;

class Box implements Rectangle
{
    // Value denoting the object's type, to avoid reflection calls
    // for better performance.
    public var areaType: CollisionAreaType = CollisionAreaType.Rectangle;

    // Use this to temporarily disable an object's collision 
    // without removing it from whatever list it may be in.
    public var collisionsEnabled: Bool = true;

    public var x: Float = 0;
    public var y: Float = 0;
    public var width: Float = 100;
    public var height: Float = 100;

    public function onOverlap(other: Collider)
    {
        // Called when this object overlaps with another.
    }
}

Using the Quad Tree

The tree is static and should be re-built on every frame.

import quadtree.QuadTree;

To check an array of objects for collisions between themselves.

// Initialize a tree with set boundaries.
var qt: QuadTree = new QuadTree(x, y, width, height);
qt.load(objectList);
qt.execute();

To check an array of objects for collisions between them and another list of objects.

var qt: QuadTree = new QuadTree(x, y, width, height);
qt.load(objectList1, objectList2);
qt.execute();

Configurating the QuadTree

Being familiar with quad-trees, you can also configure its properties.

// The maximum depth of the tree.
// After it is reached, leaf nodes will simply be filled with all objects added to them.
// Quad trees with large boundaries (f.e world maps) may benefit from having a bigger maxDepth.
qt.maxDepth = 5;

// The amount of objects a node can hold before it is subdivided into quadrants.
// The amount of collision checks that happen on each node will be equal to this number squared.
// Quad trees with large boundaries (f.e world maps) may benefit from having less objects per node,
// this way the tree will be split more often and objects far-away from each other won't be checked against each other as much.
qt.objectsPerNode = 4;

// Set a custom function to further handle the overlapping of two objects.
// This callback will be called each time two objects overlap, and if it returns false
// the onOverlap() method of the objects will not be called.
qt.setOverlapProcessCallback(function(collisionResult: quadtree.helpers.CollisionResult)
{
    var obj0 = collisionResult.object0;
    var obj1 = collisionResult.object1;
    return true;
});

Collision Separation and Velocity

This library can also handle the separation of overlapping objects, as well as calculating their velocities according to momentum conservation.

A good place to perform this would be the overlap process callback, which is called before objects are notified of their collision.

import quadtree.Physics;
import quadtree.helpers.CollisionResult;

qt.setOverlapProcessCallback(function(collisionResult: CollisionResult)
{
    var obj0 = collisionResult.object0;
    var obj1 = collisionResult.object1;

    // First separate the objects.
    Physics.separate(collisionResult);
    
    if (collisionResult.separationHappened)
    {
        // If separation actually happened, we can also update their velocities.

        // First configure the collision result.
        collisionResult.obj1Velocity.set( ... );
        collisionResult.obj1Mass = ...;
        collisionResult.obj1Elasticity = ...;
        collisionResult.obj1Immovable = false;

        // Similary for object2.
        collisionResult.obj2Velocity.set( ... );

        // The next function will calculate the new velocity for each object,
        // and modify the two vectors, obj1Velocity and obj2Velocity.
        Physics.momentumConservationCollision(collisionResult);

        // Finally, update the velocities on the objects themselves.
        obj0.velocity = collisionResult.obj1Velocity;
        obj1.velocity = collisionResult.obj2Velocity;
    }

    return collisionResult.separationHappened;
});