How I implemented 2D collision detection in Pistol Slut
maryrosecook.com
maryrosecook.com
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.
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.
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]
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?
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 :)
Essentially this makes the intersection calculation easier at the expense of computing the Minkowski sum. However, computing the Minkowski sum is trivial in certain cases, and the axis-aligned square "grenade" intersecting with a line segment is one of them:
You can treat the grenade as a point and inflate the line segment by the grenade's dimensions in x and y to make a rectangle. Then you can sweep the point to make a line segment representing the grenade's movement and intersect it with the rectangle. This gives you the exact intersection point, much as in the case of the bullet/bin intersection, without needing to incrementally search along the grenade's path.
(Also, a quadtree would be more efficient for this kind of solution).
(edit for another little thing I missed)
edit: mrcharles in the child comment has it right, testing 4 squares is sufficient. In this case you will detect the collision from B's point of view instead of A's which is fine.
For object redirection, just figure out which side of your grenade crosses another object first. You can do this simply by making your grenade a point (at the center) and adding half its size to every other object (in your calculations), effectively, taking the Minkowski sum of your grenade with every object you check. This eliminates the "which corner do I use" problem, and really simplifies your code. Then, suppose it crosses a vertical line defining another object, going from ticked position A to C. No need to find B, just subtract the x-coordinate of C and the vertical line, and subtract twice that from the x-coordinate of the grenade.
Something like this: https://gist.github.com/786255
Hopefully you can read my faked python, and have segment intersection and point-in-rectangle tests. Careful on the corners of boxes.
In your axis-aligned case, you would project the objects you test on both axes (x and y). If the do not overlap on any one of the axes, they do not collide, otherwise they do. To handle movement you project each objects movement vector on the axes as well and add that to the objects projected interval.
To find out which grid squares that are covered by a polygon amounts to resterization, which you can find many tutorials for with google.
Axis aligned boxes are trivial to rasterize. For more complex shapes you write a rasterizer for triangles and handle arbitrary polygons by breaking them up into triangles (google "ear clipping").
For example, instead of grid-based preliminary collision detection you could use distance-based one, i.e. if object coordinates are farther away than obj1.saferadius + obj2.saferadius then they don't collide.
In an actual game you probably want something like:
safedist = (obj1.saferadius + obj2.saferadius)
if (abs(ob1.x - box2.x) < safedist)
if (abs(ob1.y - box2.y) < safedist)
if (faster_test(ob1,ob2)//aproximates square roots
if (full_test(ob1,ob2))//slow, but avoids bugs
{do stuff...}However, in games you frequently want to check the intersection of lines, or spheres with plains, cubes etc. And for those equations you often have to deal with the inverse square root function.
PS: Anyway, my point was more abut the process. First you try A, which culls 90% of your objects, then you try B which culls 95% of the objects then you do the full and actuate solution if you have time. http://en.wikipedia.org/wiki/Ragdoll_physics takes a lot of CPU time, and now days games need to be even more realistic.
Pistol Slut, for example, doesn't introduce any special handling for environmental collisions(platforms, ledges, etc.) because it doesn't focus on that kind of platforming gameplay. In a distance game like Toss the Turtle or Hedgehog Launch, resolving fast-moving collisions by constructing swept polygons becomes a very good idea. In an game like an RTS where you have lots of unit movement, collision may take place with points on the tile-map, building on the pathfinding algorithms, rather than by handling a separate set of collision structures. In a game like Prince of Persia: Sands of Time, you have to develop some kind of history of object state, including collision, so that the game works properly when time is reversed. In a game spanning very large distances you have to account for numeric precision(i.e. you can't just throw in a floating-point type and be done). In a networked game you have to include some interpolation, prediction, and compensation for latency so as to improve the feel of hit registration. And so on...
In all cases, a substantial part of gameplay rests upon technical assumptions. Trying to combine every collision feature you can conceive of into one universal system will increase your effort into the man-years range very quickly, so it's not done that way.