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].

• If Use Quadtree is enabled, every objects is only checked against objects from the same node(s).
• If Use Quadtree is disabled, every object is checked against ever other object.

The following code is reduced to the most important parts. View the full script.js of this example on GitHub.

HTML

<canvas id="canvas" width="640" height="480"></canvas>

JS

// Create a new Quadtree
const tree = new Quadtree({
	width: 640,
	height: 480,
});

// Store all objects in an array
const myObjects = [];

// Create some objects
for(let i=0;i<200;i++) {
    const rectangle = new Quadtree.Rectangle({
        x: Math.random() * 640,
        y: Math.random() * 480,
        width: 4 + Math.random() * 28,
        height: 4 + Math.random() * 28,

        // Custom data: velocity for x and y, 
        // and a check boolean to flag colliding objects
        data: {
            vx: -0.5 + Math.random(),
            vy: -0.5 + Math.random(),
            check: false,
        },
    });

    myObjects.push(rectangle);
}

// Enable/disable Quadtree
let useQuadtree = true;
document.querySelector('#toggle-quadtree').addEventListener('click', () => useQuadtree = !useQuadtree);

// Main loop
function loop() {
    
    // [1] Clear the tree
    if(useQuadtree) {
        tree.clear();
    }
    
    // [2] Update myObjects and insert them into the tree again
    myObjects.forEach(obj => {

        // Update the position
        obj.x += obj.data.vx;
        obj.y += obj.data.vy;

        // Reset retrieve flag
        obj.data.check = false;
        
        if(useQuadtree) {
            tree.insert(obj);
        }
    });

    // [3] now that the tree is filled, we have to check each object for collisions
    for(let i=0;i<myObjects.length;i++) {

        const myObject = myObjects[i];

        // [4] first, get all candidates that share nodes with myObject
        // (or all objects, if useQuadtree is false)
        const candidates = useQuadtree ? tree.retrieve(myObject) : myObjects;

        // [5] let's check them for actual collision
        for(let k=0;k<candidates.length;k++) {

            const 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 for actual intersection
            const 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
            }
        }
    }

    // Draw scene
    draw();
    
    window.requestAnimationFrame(loop);
};

loop();

To see the full example code please check the page source or visit this page on github.