How I implemented 2D collision detection in Pistol Slut(maryrosecook.com)
maryrosecook.com
How I implemented 2D collision detection in Pistol Slut
http://www.maryrosecook.com/post/how-to-do-2d-collision-detection
39 comments
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.
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 :)
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:
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?
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?
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.
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.
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.
http://en.wikipedia.org/wiki/Minkowski_addition
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.
http://en.wikipedia.org/wiki/Minkowski_addition
This page helped me understand the Minkowski sum visually: http://www.pfirth.co.uk/minkowski.html
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 http://realtimecollisiondetection.net/ and the blog on that site can be just as invaluable a source of information as the book itself.
Yes, that's a very nice book. I built a very rudimentary 2D physics engine in javascript based on it. Eberly's Game Physics is another nice book as well.
http://www.amazon.com/Game-Physics-Second-David-Eberly/dp/01...
Oh wow, I hadn't heard of that. Thanks a lot.
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.
(Also, a quadtree would be more efficient for this kind of solution).
(edit for another little thing I missed)
(Also, a quadtree would be more efficient for this kind of solution).
(edit for another little thing I missed)
You can insert object A to just the 4 squares, but you still need to check with collisions with objects in all 8 surrounding squares. There could be an object B whose top-left point is in the square northwest of A's square but still collides with A.
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.
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.
Unless I'm misunderstanding the algorithm, this is still handled with my suggestions, since you'd only test collisions against people in the same container as yourself, and someone who is northwest will be inserted in to my container regardless.
[deleted]
I don't think they have this in Javascript, but you want range trees, or, as drblast puts it, binary space partition, for detection.
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.
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.
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.
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").
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").
Great. I'll check out the separating axis test, too - thanks. Incidentally, I believe The Render Engine, the framework I used, has just introduced support for this technique.
You can also rotate the axes to align with one object's motion. Then the 'axis test' reduces to one axis, and collision is a line-segment test.
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.
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.
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.
The problem with that solution is it's slow and not that accurate.
In an actual game you probably want something like:
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...}There's no need to take square roots. sqrt(x) is monotone increasing, so comparing squared-distances is equivalent to comparing distances.
If all you want is distance between points
(x1-x2)^2+(y1-y2)^2+(z1-z2)^2 = dist^2 works.
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.
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.
No, you have to know your design before you can judge collision's needs properly, and you have to have some expectation that you'll get it wrong the first time and require iteration, because collision _is_ gameplay when we speak of games using a lot of spatial elements. Otherwise you are implicitly making the engine determine the design - which is acceptable in some circumstances, but increasingly likely to cause problems as you try to specialize the design. So it's OK to start with simple assumptions and wait for them to break. You aren't (yet) working with a live system where data is lost by changing collision. Let me give some examples.
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.
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.
Some sort of axis-aligned bounding box collision checking is the usual approach for a first preliminary pass.
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.
Thanks!
[deleted]
Looks like you got hacked (see bottom of page)
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.