quadtree-js

This is a Javascript Quadtree implementation of the Java Methods descriped in this tutorial: http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

This is not a collision engine, but an algorythm to narrow down objects of possible collision.

Please read the tutorial if you want to know more about Quadtrees.

There are two examples: simple and dynamic.

red squares represent Quadtree Nodes
empty white squares represent objects in our Quadtree
the cursor is the area we constantly test for
objects turned green are candidates for collision, returned from the recieve-function

How to use

Create a new Quadtree with default values for max_objects (10) and max_levels (4)

var myTree = new Quadtree({
	x: 0,
	y: 0,
	width: 400,
	height: 300
});

If you want to specify max_objects and max_levels on your own, you can pass them as a 2nd and 3rd argument

var myTree = new Quadtree({
	x: 0,
	y: 0,
	width: 800,
	height: 600
}, 5, 8);

Insert an element in the Quadtree

myTree.insert({
	x : 200,
	y : 150,
	width : 20,
	height : 20
});

Retrieve elements that "collide" with the given bounds

var elements = myTree.retrieve({
	x : 150,
	y : 100,
	width : 20,
	height : 20
});

Clear the Quadtree

myTree.clear();

Check out the examples for more information. Feel free to open an issue if you have any problems.

There is an alternative quadtree-js hitman branch available that allows you to update and remove single objects. This can be handy when most of the objects in your quadtree are static.

eddytheblack/quadtree-js

quadtree-js

How to use