Sign in to follow this  

Sprite-to-surface collision detection.. still stuck

This topic is 4855 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

The image above basically shows what I'm trying to do. The grey space represents the area the character has covered in 1 time segment/frame. The brown tiles are the ones that have to be checked for collision. The red parts are where collisions would occur. Both shades of blue are the character's bitmask. The yellow is space I DON'T want to test. I really can't think of a good algorithm to do this, and here's a few problems I'm stuck on: 1. How would I create a bitmask of the grey+blue+light blue area? (ie, can I create a dynamic bitmask) 2. How could I efficiently test the area he has covered, as he moves along this grey area, with the goal being to find the red pixel he touches first? (ie, I don't just want to test for collision, I want to find where the first possible collision happened, even if he went through it, so simple tile-sprite bitmasking isn't enough) 3. Even if I wasn't using a perfect bitmask on the character (I must use a bitmask on the surface tiles), how could I even do it using BBs, circles, or ovals? If my whole approach is way off, feel free to suggest anything.

Share this post


Link to post
Share on other sites
ouch... per-pixel swept test collision...

With non pixel-based collisions, where surfaces are approximated with polygons, segments or spheres, it's easy enough, but you don't want to do that...

To keep things simple, you can keep a mask-based system, and step the object through the map (like move the object 3 pixels at a time, test, found collision, track back, test again, until you found a 1-pixel deep collision or whatever). The advantage is, it should scale well with objects either moving fast or slowly, easy to implement from an ordinary per-pixel engine, should be quick(ish) if you don't have that many large sweeping objects (like in a Sonic game), and well documented. You can set the stepping as much as you want, depending on the accuracy you want and the speed. Typically, the maximum stepping should be something like a 25% of the size of the object. This would also work well for object-object collisions.

Another way, totally from the top of my head, is to do exactly what the picture tells. You generate a collision mask using the original sprite and extruding it towards it's end-position. Then test overlapping pixels (red pixels), and using the position of the pixel in the extrusion, calculate back the time of collision. For object-object collision, the same system can be used, if you use the relative velocity of one object against another.

Share this post


Link to post
Share on other sites
Ah thanks.. didn't think of stepping through and tracking back at all. And using time calculations to work out who hit first I hadn't thought of either.

But I don't know how to generate that grey collision mask if I choose that approach. *Googling*

And thanks for actually attempting the question, I get alot of "Nah just change the game instead" lately.

Share this post


Link to post
Share on other sites

See:
http://www24.brinkster.com/freydev/Collision_Detection_2.png

I've drawn in extra lines on your original image, the white one representing the line from the previous sprite centre to the current sprite centre. The black lines represent the boundary lines for the sprite.

My idea is simple: each of those lines represents a 'solid' (ie. masked) point on the sprite as it moves. Simply trace along the line from start to finish (using something like bresenhams line algorithm) and do per-pixel checks if that line hits the map area. If you decide to use bresenhams line algorithm, you will only need to keep track of the deltas for 1 line (since all the lines are parallel and they only differ in origin)

You can dynamically create and test more or less lines between the 2 outer ones depending on performance. Obviously, the more lines, the better the accuracy.

Hope that helped

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by FReY

See:
http://www24.brinkster.com/freydev/Collision_Detection_2.png

I've drawn in extra lines on your original image, the white one representing the line from the previous sprite centre to the current sprite centre. The black lines represent the boundary lines for the sprite.

My idea is simple: each of those lines represents a 'solid' (ie. masked) point on the sprite as it moves. Simply trace along the line from start to finish (using something like bresenhams line algorithm) and do per-pixel checks if that line hits the map area. If you decide to use bresenhams line algorithm, you will only need to keep track of the deltas for 1 line (since all the lines are parallel and they only differ in origin)

You can dynamically create and test more or less lines between the 2 outer ones depending on performance. Obviously, the more lines, the better the accuracy.

Hope that helped







Even more fun (and line projections) if you are doing a 3D collision (moving object height vs terrain path heigths).


Breaking terrain into rough chunks and do a circle/ sphere(if 3D) leazy evaluation to eliminate most terrain features
-- using a simple chunk center to movig_object distance check
(you can even throw out the square root)

if distance > chunk_radius+object_radius then doesnt collide.
else do more accurate test




Share this post


Link to post
Share on other sites

This topic is 4855 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this