multiple DIV collision detection in Javascript/JQuery

Question

Working on a little "zombies" or "tag you're it" or "ew! you got cooties"-styled game where each AI object (a person, basically) runs around randomly. There is an initial object that is "it" or "infected" and as it moves about the screen and touches/overlaps/collides with another object it should change the touched object to the same color as the object that touched it. Newly infected objects can continue to infect other objects they randomly collide with, until - in principle - the whole population is the same color as the first infected object. (I'll worry about fancier AI where infected actively hunt nearby objects or healthy objects can avoid infected objects, later).

But after looking at various similar questions in StackOverflow that generally deal with 2 DIVs colliding, or use some sort of jQuery draggable detection trick, I'm still at a bit of a loss as to how to build upon those ideas to scale up a simple "if I am touching/overlapping/colliding with another object it should get infected too" that can be applied to a large number of elements on the page, say... less than 100 so as not to drag the browser down.

I basically get as far as determining position and widths/heights of the objects so that I know how much space they take, but then the brain goes 'bzzzzt' when trying to develop a function that checks over all the population for collisions.

Got the population moving around randomly without trouble - see JSFiddle https://jsfiddle.net/digitalmouse/5tvyjhjL/1/ for the related code. Affected function should be in the 'animateDiv()', seen below to make the stackoverflow question asking editor happy that I included some code in my question. :)

 function animateDiv($target) {
     var newq = makeNewPosition($target.parent());
     var oldq = $target.offset();
     var speed = calcSpeed([oldq.top, oldq.left], newq);

     // I believe collision should be dealt with here,
     // just before moving an object

     $target.animate({
         top: newq[0],
         left: newq[1]
     }, speed, function () {
         animateDiv($target);
     });
 }

Any hints, tricks, adaptations, or code snippets that push me in the right direction are appreciated.

Answer 1

a quick, down and dirty solution (there are more complex algorithms) would be to use:

document.elementFromPoint(x, y);

It gets the element at the position specified. The full spec can be found here.

Assuming your 'zombies' are rectangular, you could call this for each corner, and if you get a hit, that isn't the background or the element you're checking, you've got a collision...

EDIT:

An alternate method, even 'downer and dirtier' than above, but stupidly quick, would be to get the centre points of the two objects to check, then find their absolute displacements in X and Y. If the differences are less than the sum of half their widths and heights then they are overlapping. It's by no means pix perfect, but it should be able to handle a large number objects really quickly.

EDIT 2:

First off, we need to get the centres of each object (to check)

// Values for main object
// pop these in vars as we'll need them again in a sec...
hw = object.style.width >> 1; // half width of object
hh = object.style.height >> 1; // (bit shift is faster than / 2)

cx = object.style.left + hw; // centre point in x
cy = object.style.top + hh; // and in y

// repeat for secondary object

If you don't know / store the width and height you can use:

object.getBoundingClientRect();

which returns a 'rect' object with the fields left, top, right and bottom.
Now we check proximity...

xDif = Math.abs(cx - cx1); // where cx1 is centre of object to check against

if(xDif > hw + hw1) return false; // there is no possibility of a collision!

// if we get here, there's a possible collision, so...

yDif = Math.abs(cy - cy1);

if(yDif > hh + hh1) return false; // no collision - bug out.
else {
    // handle collision here...
}

Danny