Giant Quadtree is 2D collision Detection Without Boundaries
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.
An Example
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
Use
For plain JavaScript applications, use the dist/quadtree.js, which will inject the Quadtree object to the global scope. If you're using NodeJS (or any system that uses the export/require pattern), use dist/quadtree-module.js, as it exports the Quadtree object.
API
In the API Quadtree
(capitalized) refers to the module object and quadtree
(lowercase) refers to a
Quadtree instance which is created via Quadtree.create
.
Quadtree.create(opt_width, opt_height)
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
quadtree.insert(rectangle)
Inserts a rectangle to the quadtree. A rectange is any object which has a width
, height
, left
, and top
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;
quadtree.get(left, top, width, height)
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
quadtree.reset()
Clears the quadtree of all objects.
var myTree = Quadtree;myTree;myTree;var boxes = myTree;console; // 2myTree;var boxes = myTree;console; // 0
quadtree.prune(left, top, width, height)
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)