Mike Chambers

code = joy

JavaScript QuadTree Implementation

with 11 comments

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:

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.

Written by mikechambers

March 21st, 2011 at 9:24 am

Posted in General

Tagged with , , , ,

«
»

11 Responses to 'JavaScript QuadTree Implementation'

Subscribe to comments with RSS or TrackBack to 'JavaScript QuadTree Implementation'.

  1. Cool. The earlier github link simply links back to this blog page.

    Troy Gilbert

    21 Mar 11 at 9:33 am

  2. @troy

    Good catch. I just fixed the link.

    Thanks…

    mike chambers

    mesh@adobe.com

    mikechambers

    21 Mar 11 at 9:37 am

  3. Nice!

    Now you just need to implement RequestAnimationFrame ;)
    http://mrdoob.com/lab/javascript/requestanimationframe/

    Mr.doob

    21 Mar 11 at 11:26 am

  4. @Mr.doob

    >Now you just need to implement RequestAnimationFrame

    For EaselJS? Yeah, that is something we have discussed and is on the roadmap. Current priorities are working on basic touch support, and item bounds.

    mike chambers

    mesh@adobe.com

    mikechambers

    21 Mar 11 at 12:39 pm

  5. I’m a bit confused by the “Retrieving items with bounds”. What is it supposed to do? When I click on a boundary it highlights rectangles all over the place. Is that how it’s supposed to work? And if so what is the purpose?

    Björn Ritzl

    22 Mar 11 at 1:09 am

  6. _stuckChildren could be optimized no ? currently it seems to collect any BoundNode which cross a square boundary, even if this boundary is on the other side of the space…

    if the world is large, it can add up quite a bit and reduce the scalability.

    Jerome Etienne

    22 Mar 11 at 9:05 pm

  7. Was planning to make one for quite a while and finally got inspired to do so thanks to your work :)

    Check it out at http://provoke.it/p

    What I’ve found disappointing – in a way at least – was that brute force nested for loops were producing similar results for up to ~500 objects and only past that quadtree reindexed every update frame started showing real improvements in results vs brute force. Any idea how to speed up the tree reindexing for dynamic objects? It’s great for static objects when you don’t need to reindex the tree every update tick but otherwise the reindexing adds a lot. I was thinking about giving an option to reposition only nodes which moved out of their bounding rects and maybe reinsert them bottom-up (check if they fit parent’s other subnodes, -> parent’s parent subnodes and so on) but dunno – haven’t tried that yet – but with small objects it could be actually faster I imagine.

    Also check my Timer.js that the demos are running on – it uses deterministic model based game loop/update loop and uses requestAnimationFrame method Mr. doob mentioned. Deterministic model will allow you to have more consistent results of yours app’s logics – not sure what type you are using for your EaselJS.

    If you had any ideas with tweaking the quadtree let me know @ tomasztunik@gmail.com

    regards,
    Tom

    tomasztunik

    11 Apr 11 at 1:21 am

  8. Hi,

    I found one bug. Max Depth is not propagated to children in subdivide(). When you call this._classConstructor() you should send both depth and this._maxDepth.

    Marcin Ignac

    11 Jul 11 at 11:59 am

  9. Node deletion part seems to be missing.

    digitalpbk

    1 Aug 11 at 10:37 am

  10. @marcin ignac
    yeah it took me a while to notice that too, Max depth and Max children are not propagated, every other node than root, its subdivided when reaching 4 children
    there should be something like this:

    //top left
    this.nodes[Node.TOP_LEFT] = new this._classConstructor({
    x:bx,
    y:by,
    width:b_w_h,
    height:b_h_h
    },
    depth,this.maxDepth,this.maxChildren); //<-

    for each each of the 4 "nodes"

    luis

    7 Dec 11 at 8:04 am

  11. [...] This javascript quadtree example shows how a QuadTree can be efficient to detect collision with lots of objects. [...]

    QuadTree for 2D Collision Detection with static not-moving objects | YARG – Yet Another RPG Game

    20 Feb 12 at 5:32 pm

Leave a Reply