ID:107895
 
I just put a proof of concept demo for performing pixel-perfect collision detection onto the hub. I explained how it works in this thread and will get the source up soon!

Edit 2/8: I just found this on Google Code. If you're interested in pixel collision, take a look at it. Anyone know who Albinoamsel is on BYOND?
I can dig it.
Very nice. I cannot wait to see the code.
^^
Albro1 wrote:
Very nice. I cannot wait to see the code.

I imagine what he's doing is actually simpler than approximating the shape of the object. Just take two 'density lists', offset one, and see if there are any collisions between them.

Toadfish wrote:
Albro1 wrote:
Very nice. I cannot wait to see the code.

I imagine what he's doing is actually simpler than approximating the shape of the object. Just take two 'density lists', offset one, and see if there are any collisions between them.

Pretty much, it's explained in the forum post I linked to.
Toadfish wrote:
I imagine what he's doing is actually simpler than approximating the shape of the object.

It doesn't get easier than the rectangle example I gave. "return !(x1>r.x2 || x2<r.x1 || y1>r.y2 || y2<r.y1)"

And circle collision detection is also simple. Approximating collision detection by using shapes is very easy. Checking every pixel in one sprite against every pixel in another is also not difficult, but it's still not as easy as simple shapes.

Circle detection is also 1 line: "return (x-o.x)*(x-o.x)+(y-o.y)*(y-o.y) < (r+o.r)*(r+o.r)"

If you want to get into any other shapes, it can get more complicated, but you generally only use more complicated shapes because they approximate your object better than simpler shapes, and even checking more complicated shapes is still way, way faster than checking every pixel.

A decent compromise is to combine the best of every scheme. Surround objects with approximate rectangles, and check the rectangles first, which is close to 0 time required to check. If that fails, you know there cannot be a collision, so stop. Otherwise, check against some other shape, such as a circle or an ellipse or triangle or n-side polygon or whatever. If that fails, you know there cannot be a collision so stop, otherwise, THEN you check against every pixel, though by this time you know that there probably is a collision anyway, and the pixel-perfect detection just confirms that 90% of the time, and the other 1 in 10 it catches those close calls that are almost a hit but not quite.

Have you ever wondered why, even in major commercial video games you get odd graphical issues such as your arm going partway through a door, or that thing that pisses you off when you can plainly see that something did not actually hit you but it still counted as a hit? That's because they only vaguely approximate the collision with rectangles, and they don't even do that very well.

Collision detection is an art and a science in its own right.
Detecting a collision is often just part of the story. When a collision occurs, what do you do? In my sidescroller library objects have rectangular bounding boxes. Not only does it make collisions easy to detect, it makes them easy to resolve. Because objects are rectangles you can easily determine how much they overlap and how much an object needs to move to resolve the collision. With "pixel-perfect" collisions you cannot make any assumptions about the shape of the object and these situations are harder to resolve.

I haven't had a chance to look at this demo yet, but detecting a collision is often a small part of a larger process. Simple bounding shapes are used to simplify the entire process, not just the collision detection.
Currently what I am doing is moving the mob back to its last position if a collision occurs. There is some some information online about collision response for pixel-perfect collisions, though this isn't one of the method's strong points. In many cases, this doesn't matter. For example, when a projectile collides with an object, it is destroyed and no response is needed. Since bounding boxes are used, one could use the same method for resolving collisions that you mention, however it wouldn't always look smooth and might defeat the purpose of using per-pixel collisions in the first place.

Anyway, the purpose of this demo is just to prove that it can be done, not to imply that all games should be using this method. As Loduwijk has mentioned both in the comments and in the forum thread I linked to, there are numerous ways of detecting collisions. Which one is best depends entirely upon your game.
I was discussing the general case, Loduwijk. Pixel-by-pixel detection is by no means more efficient than shape approximation, but general shape approximation is more algorithmically and mathematically complex (although there are, if you don't care for optimization, still some simple algorithms for it, especially in 2D, I must say).
Toadfish wrote:
Pixel-by-pixel detection is by no means more efficient than shape approximation, but general shape approximation is more algorithmically and mathematically complex (although there are, if you don't care for optimization, still some simple algorithms for it

You said "simpler," meaning "easy to do or to make." That is what I was replying to. Commonly used shape approximation collision detections are easier than checking each pixel.

As for shapes being "algorithmically and mathematically complex" in comparison, either you typo'ed and meant to say that the other way around or you are mistaken. Checking every pixel has an n^2 complexity. Simple shapes have a complexity of 1. Arbitrary shapes have complexity greater than 1, but I don't recall what ballpark they are in, though I highly doubt it is greater than n^2, especially the ones that don't suck.

especially in 2D, I must say).

I hope you're not using 3D bitmaps and checking each point in a 3D game. That would be even worse complexity. ;)

Back to the original topic though, if you were to create only an outline of a picture and check only the specific points that lie on that outline, you could greatly increase the speed. It would still be slow in comparison to other things, but since we generally use 32x32 pixel icons in Byond, we could estimate a liberal average of about 70 points to check for each object, so that would be 70*70 checks of one pixel against another, so that would be equivalent to checking 35 full rectangle collisions but getting practically perfect accuracy. That could be worth it.
Look, perhaps I am not being clear. I was not talking about time and space complexity, I was talking about the complexity of the concepts. Quicksort is more difficult to write and understand than bubble sort. Checking if a point is inside a complex polygon using a ray casting algorithm is more complex than offsetting a point against a density map. Mathematically, checking if a point is in an outlined area is more complex than checking whether a point can be found in a set (assuming the set is given as a collection of points rather than say, a drawing on the plane).

(As for the complexity, by the way, I'm pretty sure the best complex polygon algorithm is O(n), but you can wind it down to an extremely efficient O(log n) for classes of polygons, say with an inclusion test for convex ones. Of course, since you are concerned about efficiency, note that time complexity is not necessarily the be-all end-all, and that you may very well opt for an O(n) algorithm with low constants in certain cases.)