Another way is to divide the screen into halves or thirds, then divide those into halves or thirds, and so on until you reach a minimum tile size. Whenever an object moves, you calculate recursively the smallest tile that completely encloses the object, and only check for collisions with other objects below that recursion depth. So, big objects will have potentially many calculations, but your more typical tiny objects hardly have any. This has the nice property of automatically handling the case when objects cross grid boundaries.
But the funny thing about most 2D games and processing power these days; most attempts to reduce the amount of computation done in collision detection is premature optimization. Even if you check every object against every other one, unless you have a bullet-hell shoot-em-up with a ton of objects on screen, the calculation takes much less time than refreshing the graphics.
We have machines that are thousands of times faster than the NES which handles this job just fine.
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.
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:
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.
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.
Comments
That's one way to do it.
Another way is to divide the screen into halves or thirds, then divide those into halves or thirds, and so on until you reach a minimum tile size. Whenever an object moves, you calculate recursively the smallest tile that completely encloses the object, and only check for collisions with other objects below that recursion depth. So, big objects will have potentially many calculations, but your more typical tiny objects hardly have any. This has the nice property of automatically handling the case when objects cross grid boundaries.
But the funny thing about most 2D games and processing power these days; most attempts to reduce the amount of computation done in collision detection is premature optimization. Even if you check every object against every other one, unless you have a bullet-hell shoot-em-up with a ton of objects on screen, the calculation takes much less time than refreshing the graphics.
We have machines that are thousands of times faster than the NES which handles this job just fine.
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:
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.