How I implemented 2D collision detection in Pistol Slut

Re:How I implemented 2D collision detection in Pistol Slut by enjalot on Wednesday January 19, 2011 @09:38AM (#2119816)

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?

[ Parent | on HN ]

Re:How I implemented 2D collision detection in Pistol Slut by chipsy on Wednesday January 19, 2011 @05:50PM (#2121611)

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

[ Parent | on HN ]

Re:How I implemented 2D collision detection in Pistol Slut by maryrosecook on Wednesday January 19, 2011 @10:30AM (#2119995)

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.

[ Parent | on HN ]