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

collision, detection, quad, quadtree, tree
haxelib install quadtree 0.3.3


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.


$ haxelib install quadtree


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);

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);

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.
    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.

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

    return collisionResult.separationHappened;