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.
Visit the projects GitHub IO Page and play around.
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.
- include the quadtree2.min.js
var Vec2 = require('vec2');
var Quadtree2 = require('quadtree2');
If you want to submit a bugfix, push a test for it as well (should fail without the fix).
- test with mocha (after
grunt watchif you want to run the tests on every change in source files
- test with browser by opening the index.html
- build it with
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.
var // Variable to save the collisionsalicesCollisionsbobsCollisionsbobsDeadlyCollisions// This will initialize a quadtree with a 100x100 resolution,// with an object limit of 3 inside a quadrant.quadtree = 100 100 3// Alice will be staying fierce in the top left ...alice =pos_ : 20 20rad_ : 3// ... with his rocket luncher, gonna try to shoot bob ...rocket =pos_ : 20 20rad_ : 5// ... however there is a bunker on the field ...bunker =pos_ : 50 50rad_ : 10// ... will it save bob?bob =pos_ : 80 80rad_ : 3;// Add all of our beloved character to the quadtree.quadtree;// On the start Alice collides with her own rocket.alicesCollisions = quadtree;// Object.keys(alicesCollisions).length;// >> 1;// Bob is just sitting and waiting.bobsCollisions = quadtree;// Object.keys(bobsCollisions).length;// >> 0;// The rocket flys over to bobrocketpos_x = 78;rocketpos_y = 78;// Update our data structurequadtree;// Lets get the deadly hitbobsDeadlyCollisions = quadtree;// Object.keys(bobsDeadlyCollisions).length;// >> 1;