JavaScript QuadTree Implementation

Last week I was playing around with a little EaselJS experiment which required me to do collision detection against all items on the screen. This worked fine with a small number of items, but of course, the more items I added, the slower everything became.

I knew that I needed to optimize the code, and pare down the number of collision checks. I have done this before with a grid (even held a contest for it) and was going to port that AS3 code to JavaScript. However, Ralph Hauwert suggested I look at implemented a QuadTree, which should be more efficient.

A QuadTree is a data structure in which the coordinate space is broken up into regions / nodes that contain items. If too many items are added into a node, then that node is divided into 4 sub-nodes. This can provide very fast lookup of items based on the coordinates and coordinates and dimensions.

There are a couple of implementations in both JavaScript and ActionScript (Michael Baczynski has a nice AS3 implementation), but I decided that I wanted to learn a bit more and implement one from scratch.

The result if a QuadTree implemented in JavaScript that works with both 2D coordinates (x,y) and well as regions / items with dimensions.

I’ve released all of the code under an MIT License, and you can download it from my GitHub repository.

Here is an example of the tree in action:

This example shows how to use the QuadTree to pare down the number of items that need to be tested for collision detection.

I have created a couple of other simple examples:

• Collision Detection (shown above)
• Inserting points
• Inserting items with bounds
• Retrieving points
• Retrieving items with bounds

The basic code is pretty simple. Here is an example showing using the QuadTree to store and retrieve points:

var pointQuad = true;
var bounds = {
    x: 0,
    y: 0,
    width: canvas.width,
    height: canvas.height,
};

var quad = new QuadTree(bounds, pointQuad);

//insert a random point
quad.insert({ x: 12, y: 25 });

var items = quad.retrieve({ x: 11, y: 20 });

And here is a simple example showing using the QuadTree to store and retrieve items with dimensions / bounds:

var bounds = {
    x: 0,
    y: 0,
    width: canvas.width,
    height: canvas.height,
};
var quad = new QuadTree(bounds);

//insert a random point
quad.insert({
    x: 12,
    y: 25,
    height: 10,
    width: 25,
});

var items = quad.retrieve({ x: 11, y: 20, height: 10, width: 20 });

Again, you can download all of the code from my GitHub Repository. It seems fairly solid at this point, but if you find any issues, or have any suggestions either fork the project, and submit the changes to me, or post them in the comments.

There is still a lot of room for optimization and improvement in the implementation, such as pre-allocating the nodes, but Ill leave that for another day.

Btw, big thanks to Ralph Hauwert for pointing me in the right direction for my project.

Post any questions or suggestions in the comments.