The recursive technique you talk about is a nice one I hadn't heard of - thanks.

I actually find that collision detection does affect performance. For example, in Pistol Slut, when an exploding grenade throws out forty pieces of shrapnel, there was a noticeable slow-down before I did some optimisation.

Incidentally, you've invented space partitioning: http://en.wikipedia.org/wiki/Collision_detection#Spatial_par...

If you divide each area into four, recursively, then its a quad-tree and its a fairly standard partitioning scheme (in 3D, you would need to partition in 3D so each node generally has 8 children: an oct-tree): http://en.wikipedia.org/wiki/Quadtree

I don't have time to read your approach right now, but I look forward to finding out how you solved the collision detection "problem" later :)

Collision detection absolutely affects performance, if you can run with 100 objects naively, but you can run with 10000 objects by being efficient, your performance has been affected. Computational power is never enough!

How are you storing your objects in the grid container, is it actually a container or just an array with an index pointing to the object in some kind of object array? It's possible to do the grid without actually creating it as a datastructure, you just "hash" the point you are at:

  px = (int)(p.x-grid_min.x)*grid_delta.x;
  py = (int)(p.y-grid_min.y)*grid_delta.y;
  hash = px + py * grid_width
  cell_list[hash] += [p.index]

Where p is your object and grid_delta is the cell size. The cell_list could be implemented a couple ways, but if you think of it as a hash table with each entry as a list of objects in the cell, then all you need to do to get potential colliders is calculate the hash of an object and get back all the indices.

This is a technique we are using to speed up neighbor checks in some 3D particle simulation code, it works quite well on the GPU but its simple and you already have a grid in your code.

Another option would be a quadtree, I haven't looked, are there not JS implementations already out there?

The performance may or may not be important. In a particle sim, it's very important. In a platforming game, maybe not. I would instead point towards other features of collision, like how deep the physical model goes(e.g. correctly ejecting actors from the environment when they jump against a platform - a guarantee of good results almost requires storing an acceleration and testing into the future, rather than relying on a heuristic to guess the right way out of an extant interpenetration.), or how relative positions(camera, planetary orbits, etc.) are synchronized(I ended up building a tree structure with explicit parents so that these movements are always resolved in the correct order).

That's a nice idea. The grid stuff is actually done by the Render Engine. If I remember correctly, it's a spatial grid implemented as an array of arrays where the indexes are the row/column numbers of the nodes.

On the other hand, the NES games' collision routines were with 99.6% certainly done in hand-written assembly; this article is about a JavaScript-based game engine.

It is a peculiar property of the software industry that "advance" means "able to do the same things as before, but more slowly".

Able to do the same things as before, but in a week instead of a year.

But much easier on the programmers.

As far as I know there were no high level compilers for either the NES or the SNES.

Sweep and prune( http://en.wikipedia.org/wiki/Sweep_and_prune ) is the "minimum sufficient" 2D broadphase algorithm, I'm surprised you didn't mention it. You do want some kind of broadphase because an exhaustive check is O(n^2), which means that around 40-50 objects you start to feel the performance plummet like a stone.

One last bit, partitioning the world like that is not free. A 3d world may only need to be tracked in 1 or 2 dimensions to reduce the number of comparisons to a manageable level. (3,000+)^2 will crush you, 7^2 is not that big a deal.