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.
Sprite-to-surface collision detection.. still stuck
Author
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.
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.
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.
Author
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.
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.
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
Author
Thanks.. thinking through that. The idea of testing a few lines sounds much nicer (as well as defining them). Just have to think about how intricate the surface design wants to be.
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
