Infinite 2D collision detection
A quadtree is a data structure which segments 2D space to reduce the cost of collision detection. Generally, a quadtree subdivides space as more elements occupy it. Giant Quadtree does this and adds a little twist: it grows outwards whenever an element is added outside the current boundaries. This means collision detection without boundaries.
In this example, we'll insert a box to the quadtree, and then check an area which the box overlaps for objects to retrieve it again.
var tree = Quadtree;var myBox = left: 0 top: 0 width: 100 height:100 ;tree;var objs = tree;console; // outputs true
In the API
Quadtree (capitalized) refers to the module object and
quadtree (lowercase) refers to a
Quadtree instance which is created via
Constructor function which returns a new Quadtree instance. By default, the starting height and width are 10,000 pixels.
var myTree = Quadtree;// 1. add a bunch of rectangles using myTree.insert// 2. find a bunch of collisions using myTree.get// 3. clear the tree for the next step using myTree.clear// repeat steps 1 to 3
Inserts a rectangle to the quadtree. A rectange is any object which has a
property. This object may have any other properties (none of them will be modified by the Quadtree).
var myTree = Quadtree;// Add a 100x100 box with the top left corner at 0,0myTree;// Add a 100x100 box overlapping the previous with the top left corner at 50,50myTree;
Returns all rectangles which intersect the given dimensions. This method useful for finding collisions.
var myTree = Quadtree;myTree;myTree;var boxes = myTree;// boxes will contain both of the inserted boxes since they intersect the boundaries of the get query
Clears the quadtree of all objects.
var myTree = Quadtree;myTree;myTree;var boxes = myTree;console; // 2myTree;var boxes = myTree;console; // 0
Clears the quadtree, but retains any elements that fall within the given dimensions.
var myTree = Quadtree;myTree;myTree;var boxes = myTree;console; // 2myTree; // keep everything that's contained in these boundariesvar boxes = myTree;console; // 1 (the first box that was inserted)