Pruning collision detection with a 1D sort

Recently I was trying out Phaser.io. It’s a nifty little HTML5/JS game development framework for 2D games with graphics, audio, physics, etc. It’s free, and MIT licensed.

Anyway, I ran into a limitation in its physics optimization. You can collide object-to-object, or entire groups of objects to other groups. Colliding entire groups at a time gets some optimization — not sure the details, but much faster than pairwise testing each element. However, the limitation is that groups also affect render z-order, and I have other plans for z-order.

It permits array-to-array tests, but that was slow; I’d guess it’s just a pairwise test underneath.

So, I remembered a 1D sort I wrote up a few years back. I coded it up, and it ended up outperforming groups on the benchmark I threw together. Here’s the core code:

function leftOfBody(b) { return b.x - b.halfWidth; }
function rightOfBody(b) { return b.x + b.halfWidth; }
function sortedCollide(game, arr) {
  arr.sort(function(a,b) { 
    return leftOfBody(a.body) - leftOfBody(b.body);
  })
  for (var i = 0; i < arr.length; ++i){
    var elem_i = arr[i]

    for (var j = i + 1; j < arr.length; ++j) {
      var elem_j = arr[j]
      if (rightOfBody(elem_i.body) < leftOfBody(elem_j.body)) { 
          // bail early. All elements right of 'j' are also entirely right of 'i'
          break; 
      }
      game.physics.arcade.collide(elem_i, elem_j)
    }
  }
}

By sorting in one dimension, we can bail out early from the loop. Once we see an element that is too far right to collide, we know that the rest of the elements in the array are also too far right.

For a typical 2D platformer, most of the world is either entirely to your right or left, so the inner loop runs effectively a constant number of iterations. This brings collision detection down from O(n**2) to O(n), plus the cost of the sort. The sort itself can be optimized to O(n) as well given reasonable assumptions about game mechanics, but I’ll leave that for another post.

You can try it out yourself at http://jsfiddle.net/cwgbxss5/1/.

If you want to use the above code, I’m making available under the WTFPL license. Enjoy.