Javascript: Collision detection

Question

Hello,

could someone please help me to understand how collision detection works in JS? I can't use jQuery or gameQuery - already using prototype - so, I'm looking for something very simple. 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?

Answer 1

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 workout an easy solution..

Take a look to wikipedia page, it can give you some hints.

Answer 2

The first thing to have is the actual function that will detect whether you have a collision between the ball and the object.

For the sake of performance it will be great to implement some rude collision detecting technique, e.g. bounding rectangles and a more accurate one if needed in case you have collision detected.
So you'll end up with a little bit quicker but exactly the same loop.

Another option that can help increasing performance is to do some preprocessing with the objects you have. For example you can break the whole area into cells like a generic table and store the appropriate object that are contained within the particular cells. Therefore to detect the collision you are detecting the cells occupied by the ball, get the objects from those cells and use your collision-detecting function.

To speed it up even more you can implement 2d-tree, quadtree or R-tree.

Answer 3

//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);