Collision detection on a pixel by pixel basis?

[Volte6]

I'm trying to make my first 'game' of sorts, as a learnign project. The problem i'm up against right now is I want the levels to be able to be a series of bitmaps... one for the background (road), and one to indicate where they can drive, etc...

For example, white is drivable, and black is not. So, I can test for a black pixel, and stop their movement, but I'd prefer that they rebound off of a wall. If all walls were merely horizontal/vertical, this would be easy to do, but how can I detect the angle of a wall when they hit it? If it's a 45 degree angle, 20 degree angle, rounded, etc.? I'd like to be able to test and respond accordingly.

Hope that makes sense, thanks!

[mlepage]

You have certainly hit upon exactly the problem you just described. Congratulations.

Personally, I'd look into augmenting your data structures with some additional info telling it the angles at places. For example, a polygon mesh.

What you are thinking of, is trying to figure out this extra data at runtime, when you have collided.

Instead, figure it out when you make your level, so it's just there when you collide.

Additionally, everyone seems obsessed about "pixel perfect" collisions. I wouldn't worry too much over it. What's the point of calculating the exact pixel, the exact angle of rebound, if you aren't also calculating the moment of inertia and rotational acceleration at the same time?

The point is, where does it end? Presumably the idea of being pixel perfect is to be more realistic. But it's not realistic to go flying off at another angle just because a pixel collided in a certain way, without spinning and friction and compression and doing other physics things. So if you can't be realistic anyways, don't worry about that extra pixel.

Just get something within a few pixels and you'll be fine. For example, say you have a ship that is mostly round. You can approximate it mathematically by a circle. Easy to calculate rebounds. It might be off by a pixel or two in some places, but it will be close enough and you will save a lot by not storing or calculating something more complicated.

[Volte6]

Still not sure how to go about it, but I'll look up "Polygon Mesh", thanks

[mlepage]

Think about Quake. It's levels are composed of polygon 3D models. The engine knows when you hit a polygon's face.

Quake doesn't care about the textures (images). In fact, on the server, there are no images at all, yet it still knows when you have collided and how to respond.

So I'm saying to develop a model of your level that is independent of your images. It can still be as flexible as you like.

Then, once your model is working, worry about drawing it. You need not draw exactly the model, just something close. For example, your image might be a smooth curve but the model might be a series of straight lines approximating that curve. Your objects will still bounce away in roughly the expected direction and people won't notice any discrepancy.

BTW this is just standard software design. Abstract your model away from your view. Ideally, you should be able to run your entire game without graphics at all. If you can do that, you know you have done a good job.

[mlepage]

[Volte6]

[mlepage]

[fzammetti]

[fast_rx]

If you pre-calculate the angles, you can use that angle as the "color" of the pixel instead of just using white and black...

Of course, calculating that angle is the problem in the first place, but doing it this way offloads the calculations to the level editor, not your app.


To calculate the angles, can you take a pixel that is a collision point, then examine the surrounding pixels... seems like the vertical disrtibution vs. the horizontal distribution would give you a vector that would be close to the normal of the collision surface you want.

[Volte6]

[Presto]

[Dan East]

[Pam]

You might also want to check this somewhat relevant thread on GameDev.net:

Pam

[Volte6]

I considered that, but I'm not sure that would accurately reflect what the surface looks like large-scale. It might look like 45 degrees but that might not be realistic. I'd have to keep sampling to get more and more accurate, I think.

[Dan East]

You wouldn't have to sample too many. A few on each side would be enough.

The very best method would be a preprocessor that takes the bitmap and converts it into geometric primitives. In this case simple lines representing the edges of solid areas. I would store each line as a normal (perpendicular vector) and distance to origin, then do a dot product against it to find the reflected velocity vector. It wouldn't even require any trig at runtime, and would give you much better accuracy. You would also need to store the endpoints of each line, assuming you weren't going to do something as advanced as a solid bsp.

Dan East