That's one way to do it.<p>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.<p>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.<p>We have machines that are thousands of times faster than the NES which handles this job just fine.
The intersection point of two moving 2D objects is equivalent to the intersection of a moving point with the Minkowski sum of the two objects -- the shape you get when you "inflate" one object by the other's shape. So, for instance, the intersection point of two moving circles of radius r is equivalent to the intersection of a moving point and a circle of 2r. If you reformulate the problem this way, you can sweep the moving point into a line segment (of length equal to the objects' relative movement) and find the exact intersection point.<p>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:<p>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.<p><a href="http://en.wikipedia.org/wiki/Minkowski_addition" rel="nofollow">http://en.wikipedia.org/wiki/Minkowski_addition</a>
Christer Ericson's book "Real-time Collision Detection" covers all this and much, much more in a very readable (IMO) fashion. The companion website for the book is at <a href="http://realtimecollisiondetection.net/" rel="nofollow">http://realtimecollisiondetection.net/</a> and the blog on that site can be just as invaluable a source of information as the book itself.
Another issue noticed with the algorithm is that you pick a grid square by the top left point, but then insert it in to the 8 surrounding squares. In reality, you only need to insert it in the right, bottom, and bottom right square. Because there is no chance your object can be higher or more left than it's top left point. So you can save yourself 5 grid inserts and a boatload of compares. Assuming you stick with the limitation of an object not being larger than an individual grid square, in which case this is still true, but you then need to expand further down and right.<p>(Also, a quadtree would be more efficient for this kind of solution).<p>(edit for another little thing I missed)
I don't think they have this in Javascript, but you want range trees, or, as drblast puts it, binary space partition, for detection.<p>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.<p>Something like this: <a href="https://gist.github.com/786255" rel="nofollow">https://gist.github.com/786255</a><p>Hopefully you can read my faked python, and have segment intersection and point-in-rectangle tests. Careful on the corners of boxes.
You might want to google for "separating axis test", it is a very simple technique that allows you to detect collisions between any two convex polygons. It can also handle continous collisions detection for translation (your moving grenades) very easily.<p>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.<p>To find out which grid squares that are covered by a polygon amounts to resterization, which you can find many tutorials for with google.<p>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").
Some of these solutions place significant constraints on gameplay (e.g. bullet speeds vs object thickness). That's ok for a small game experiment that you have clearly defined in advance and are not going to develop much further, but most games are not developed like that. Usually you don't have a clear idea of all aspects of your game in advance, and you want more general solutions.<p>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.
I don't know much in the way of 2D collision, but I did want to say that I played Pistol Slut a bit this morning, and besides having an awesome name, I really enjoyed it. Great work.