Quadtree2.js

is a Node.js npm-package / JavaScript implementation of two dimensional quadtree for collision detection. Exported for client side use with the help of browserify. It is a work in progress, look for the first stable release if interested.

Important notes

After experimenting around with performance tests, the current implementation does not justify the use in game projects. I've started the grid2.js project for collision detection and ray casting calculations in two dimensional space. It is not scaling structure, but performs lot better at the moment in browser games. Give it a try, if that is your use case.

Try it!

Visit the projects GitHub IO Page and play around.

If you notice incorrect behavior please click on the "Log" button, copy the stuff and post it in the issues and describe the problem (or see the contribute section).

About

A quadtree is a scaling data structure for collision detection. You can find theory on the WIKI.

A simple example usecase would be a two dimensional game, with some moving objects like bullets and players. You want to know when a collision occours. Could easly just compare all the objects position with each other, but if there are a lot of them, that is not the right thing to do.

Upon adding objects to the quadtree you either specify the unique number identifier attribute of the objects, like id, or the quadtree will do this automatically.

Install

• browser
  • include the quadtree2.min.js
• Node.js
  • var Vec2 = require('vec2');
  • var Quadtree2 = require('quadtree2');

Contribute

If you want to submit a bugfix, push a test for it as well (should fail without the fix).

• test with mocha (after npm install) grunt test or grunt watch if you want to run the tests on every change in source files
• test with browser by opening the index.html
• build it with grunt

If you've played around on the GitHub IO Page and noticed some incorrect behavior click on the "Log" button, copy the code and create a test case in the test/demos.js file. I'm glad for just a test without any fix as well.

Please follow the git flow branching model.

Use

var
  // Variable to save the collisions
  alicesCollisions,
  bobsCollisions,
  bobsDeadlyCollisions,

  // This will initialize a quadtree with a 100x100 resolution,
  // with an object limit of 3 inside a quadrant.
  quadtree = new Quadtree2({
    'size'        : new Vec2(100, 100),
    'objectLimit' : 3
  }),

  // Alice will be staying fierce in the top left ...
  alice = {
    'pos' : new Vec2(20, 20),
    'rad' : 3
  },

  // ... with his rocket luncher, gonna try to shoot bob ...
  rocket = {
    'pos' : new Vec2(20, 20),
    'rad' : 5
  },

  // ... however there is a bunker on the field ...
  bunker = {
    'pos' : new Vec2(50, 50),
    'rad' : 10
  },

  // ... will it save bob?
  bob = {
    'pos' : new Vec2(80, 80),
    'rad' : 3
  };


// Add all of our beloved character to the quadtree.
quadtree.addObjects([alice, rocket, bunker, bob]);

// On the start Alice collides with her own rocket.
alicesCollisions = quadtree.getCollidings(alice);

// Object.keys(alicesCollisions).length;
// >> 1;

// Bob is just sitting and waiting.
bobsCollisions = quadtree.getCollidings(bob);

// Object.keys(bobsCollisions).length;
// >> 0;

// The rocket flys over to bob
rocket.pos.x = 78;
rocket.pos.y = 78;

// Update our data structure
quadtree.updateObject(rocket);

// Lets get the deadly hit
bobsDeadlyCollisions = quadtree.getCollidings(bob);

// Object.keys(bobsDeadlyCollisions).length;
// >> 1;

License

MIT License