quadtree-js many-to-many example

This example shows how Quadtrees can be used for many-to-many checks. All objects can collide with each other. Two loops are neccessary to first insert all objects into the tree [2] and then check each object for collisions [3].

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

function loop() {

    //[1] First, we will clear the quadtree with every game loop. 
    //This is neccessary to keep the tree clean and accurate 
    //(due to its recursive nature).
    myTree.clear();

    //[2] Then we will update the positions of all objects 
    //and re-insert them into the tree.
    for(var i=0;i<myObjects.length;i++) {
        
        myObjects[i].x += myObjects[i].vx;
        myObjects[i].y += myObjects[i].vy;
        
        myTree.insert(myObjects[i]);
    }

    //[3] Now we loop over all objects again …
    for(var i=0;i<myObjects.length;i++) {

        var myObject = myObjects[i];

        //[4] … and retrieve all objects from the same tree node
        var candidates = myTree.retrieve(myObject);

        //[5] Check all collision candidates
        for(k=0;k<candidates.length;k++) {

            var myCandidate = candidates[k];

            //[6] since all objects are inside the tree, 
            //we will also retrieve the current object itself.
            //That's a collision case we want to skip.
            if(myObject === myCandidate) continue;

            //[7] check each candidate for real intersection
            var intersect = getIntersection(myObject, myCandidate);
            
            //[8] if they actually intersect, we can take further 
            //actions. In this script, colliding objects will turn 
            //green and change velocity 
            if(intersect) {
                // … take actions
            }
        }
    }

    //[9] finally, draw all objects and the quadtree
    drawQuadtree(myTree);
    drawObjects();
    
    //request next frame
    requestAnimFrame(loop);
}
			

To see the full example code please check the page source or visit GitHub.

Collision detection is beyond the scope of quadtree-js – this example uses a very basic collision algorithm that is not bullet-proof and won't fit all cases. Please research a collision system that will work for you.

The collision code in this example is based on Metanet's N Game Collision Tutorial, which may be a starting point if you are new to collision detection. There are many great tutorials out there.