Pruning collision detection with a 1D sort

Recently I was trying out 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'
      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

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

(Mostly) Imperative Packrat Parsing

I’ve been tinkering with monadic parser combinators combined with continuations (see Monads, Mother of All), but my latest toy simplifies all that by using PEG grammars. PEGs and CFGs are nearly interchangable for most parsing of computer languages, and can be parsed in linear time and space by packrat parsing — parsing with backtracking, but uses memoization to bound backtracking cost to a constant factor as parsing work is not repeated.

The end result will be succinctly:

def number():
  x = digit()
  while test(digit):
    x = x*10 + digit()
  return x

print parse(number, "15")

Continue reading

Rootbeer – Red Arrow

Red Arrow


The ingredients include “Essences of wintergreen and licorice.” That sums it up in the best way possible. Would buy again.

Rootbeer – Sprecher

Sprecher Fire-Brewed Root Beer


Nice tone. It’s got just enough bite, reminds me a bit of XXX Rootbeer. It has a sweetness that doesn’t linger too long, possibly due to the glucose syrup. In any case, I like it quite a bit.


KSP – Budget (Challenge)

This gallery contains 9 photos.

It’s time for another Weekly Challenge: Budget Crisis. This time, Reddit challenges us to visit a Kerbin moon in 15 parts or less. The part about deadly reentry is real. I have an unofficial tweak to the Deadly Reentry mod, … Continue reading

Non-determinism from generators

UPDATE(7/3/2013) I’ve found an earlier use of this technique written about on a blog, Valued Lessons – Monads in Python from 2008. Please read it too!


I was tinkering a bit tonight with simulating nondeterminism a-la McCarthy’s Amb operator — in Python. This is peculiar as Amb is usually implemented using either first class continuations or syntactic abstractions. Python supports neither.

So what is non-deterministic programming? Continue reading

Rootbeer – Sioux City Sarsaparilla

Sioux City Sarsaparilla


Mild sarsaparilla, and well balanced. Probably great as a first time sarsaparilla.

Rootbeer – Snake River

Snake River Sarsaparilla


Sharp and licoricey, punchy and ends softly. A very well balanced beverage. Definitely will buy again.

Awaiting JavaScript

Funny diversions in continuations seen this week. They’re not new, but new to me.

Continue reading

A little Call/cc in C#

Yesterday, I wanted to show someone how CallCC works in C#/async, but I couldn’t find any examples in my web search results. C#/async has been out in the world for some time, I’d be surprised if this hasn’t been done before, but just in case here’s a quick implementation.


Continue reading