Hacker News Reader

Comment by maryrosecook | Hacker News Reader

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.

View on HN

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?

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.

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).

Reply on news.ycombinator.com