[javascript] JavaScript: Collision detection

How does collision detection work in JavaScript?

I can't use jQuery or gameQuery - already using prototype - so, I'm looking for something very simple. I am not asking for complete solution, just point me to the right direction.

Let's say there's:

<div id="ball"></div>
and
<div id="someobject0"></div>

Now the ball is moving (any direction). "Someobject"(0-X) is already pre-defined and there's 20-60 of them randomly positioned like this:

#someobject {position: absolute; top: RNDpx; left: RNDpx;}

I can create an array with "someobject(X)" positions and test collision while the "ball" is moving... Something like:

for(var c=0; c<objposArray.length; c++){
........ and code to check ball's current position vs all objects one by one....
}

But I guess this would be a "noob" solution and it looks pretty slow. Is there anything better?

Here's a very simple bounding rectangle routine. It expects both a and b to be objects with x, y, width and height properties:

function isCollide(a, b) {
    return !(
        ((a.y + a.height) < (b.y)) ||
        (a.y > (b.y + b.height)) ||
        ((a.x + a.width) < b.x) ||
        (a.x > (b.x + b.width))
    );
}

To see this function in action, here's a codepen graciously made by @MixerOID.

This is a lightweight solution I've come across -

function E() { // Check collision
    S = X - x;
    D = Y - y;
    F = w + W;
    return (S * S + D * D <= F * F)
}

The big and small variables are of two objects, (x coordinate, y coordinate, and w width)

From here.

Mozilla has a good article on this, with the code shown below.

2D collision detection

Rectangle collision

if (rect1.x < rect2.x + rect2.width &&
   rect1.x + rect1.width > rect2.x &&
   rect1.y < rect2.y + rect2.height &&
   rect1.height + rect1.y > rect2.y) {
    // Collision detected!
}

Circle collision

if (distance < circle1.radius + circle2.radius) {
    // Collision detected!
}

An answer without jQuery, with HTML elements as parameters:

This is a better approach that checks the real position of the elements as they are being shown on the viewport, even if they're absolute, relative or have been manipulated via transformations:

function isCollide(a, b) {
    var aRect = a.getBoundingClientRect();
    var bRect = b.getBoundingClientRect();

    return !(
        ((aRect.top + aRect.height) < (bRect.top)) ||
        (aRect.top > (bRect.top + bRect.height)) ||
        ((aRect.left + aRect.width) < bRect.left) ||
        (aRect.left > (bRect.left + bRect.width))
    );
}

hittest.js; detect two transparent PNG images (pixel) colliding.

Demo and download link

HTML code

<img id="png-object-1" src="images/object1.png" />
<img id="png-object-2" src="images/object2.png" />

Init function

var pngObject1Element = document.getElementById( "png-object-1" );
var pngObject2Element = document.getElementById( "png-object-2" );

var object1HitTest = new HitTest( pngObject1Element );

Basic usage

if( object1HitTest.toObject( pngObject2Element ) ) {
    // Collision detected
}

This is a simple way that is inefficient, but it's quite reasonable when you don't need anything too complex or you don't have many objects.

Otherwise there are many different algorithms, but most of them are quite complex to implement.

For example, you can use a divide et impera approach in which you cluster objects hierarchically according to their distance and you give to every cluster a bounding box that contains all the items of the cluster. Then you can check which clusters collide and avoid checking pairs of object that belong to clusters that are not colliding/overlapped.

Otherwise, you can figure out a generic space partitioning algorithm to split up in a similar way the objects to avoid useless checks. These kind of algorithms split the collision detection in two phases: a coarse one in which you see what objects maybe colliding and a fine one in which you effectively check single objects. For example, you can use a QuadTree (Wikipedia) to work out an easy solution...

Take a look at the Wikipedia page. It can give you some hints.

bcm's answer, which has 0 votes at this time, is actually a great, under-appreciated answer. It uses good old Pythagoras to detect when objects are closer than their combined bounding circles. Simple collision detection often uses rectangular collision detection, which is fine if your sprites tend to be, well, rectangular. If they are circular (or otherwise less than rectangular), such as a ball, an asteroid, or any other shape where the extreme corners are usually transparent, you may find this efficient routine to be the most accurate.

But for clarity, here is a more fully realized version of the code:

function doCollide(x1, y1, w1, x2, y2, w2) {
    var xd = x1 - x2;
    var yd = y1 - y2;
    var wt = w2 + w1;
    return (xd * xd + yd * yd <= wt * wt);
}

Where the parameters to pass in are the x,y and width values of two different sprite objects.

//Off the cuff, Prototype style. 
//Note, this is not optimal; there should be some basic partitioning and caching going on. 
(function () { 
    var elements = []; 
    Element.register = function (element) { 
        for (var i=0; i<elements.length; i++) { 
            if (elements[i]==element) break; 
        } 
        elements.push(element); 
        if (arguments.length>1)  
            for (var i=0; i<arguments.length; i++)  
                Element.register(arguments[i]); 
    }; 
    Element.collide = function () { 
        for (var outer=0; outer < elements.length; outer++) { 
            var e1 = Object.extend( 
                $(elements[outer]).positionedOffset(), 
                $(elements[outer]).getDimensions() 
            ); 
            for (var inner=outer; inner<elements.length; innter++) { 
                var e2 = Object.extend( 
                    $(elements[inner]).positionedOffset(), 
                    $(elements[inner]).getDimensions() 
                ); 
                if (     
                    (e1.left+e1.width)>=e2.left && e1.left<=(e2.left+e2.width) && 
                    (e1.top+e1.height)>=e2.top && e1.top<=(e2.top+e2.height) 
                ) { 
                    $(elements[inner]).fire(':collision', {element: $(elements[outer])}); 
                    $(elements[outer]).fire(':collision', {element: $(elements[inner])}); 
                } 
            } 
        } 
    }; 
})(); 

//Usage: 
Element.register(myElementA); 
Element.register(myElementB); 
$(myElementA).observe(':collision', function (ev) { 
    console.log('Damn, '+ev.memo.element+', that hurt!'); 
}); 
//detect collisions every 100ms 
setInterval(Element.collide, 100);

You can try jquery-collision. Full disclosure: I just wrote this and released it. I didn't find a solution, so I wrote it myself.

It allows you to do:

var hit_list = $("#ball").collision("#someobject0");

which will return all the "#someobject0"'s that overlap with "#ball".