Circle-Rectangle collision and angle
Author
First of all, Hi! :)
My question is, I hope, quite simple. If I have a circular ball of position bX:bY and radius RAD, moving in direction DIR, and Rectangle of position wX:wY and size WID:HEI how can I most effectively detect if the ball hits the rectangle, and if it hits, which side or corner it hit, and then how to calculate the new angle of ball?
There is no gravity and no speed change of the ball (Like in most arkanoids/breakouts). I know it could be worked on with help of some physics libraries but there is nothing typically physical I need other than that, so including library would be a waste of time.
If you can point me to or give solution it would be nice, if you can point me to some relatively simple and straightforward articles/stuff about that it would be nice too :).
Thanks in advance.
the general solution for spheres/ circles works like this :
1) find closest point (not necessary a vertex) on the rectangle to the ball centre.
2) if that point is inside the ball radius, you have a collision.
3) collide the ball with that point, by reflecting the ball direction along the normalised vector (ball.centre - point).
that might be a bit too advanced.
also, for an arkanoid clone, you may need to use more of a ray-tracing technique, so the ball wont go past a brick if it goes too fast. but that's a bit more involved.
1) find closest point (not necessary a vertex) on the rectangle to the ball centre.
2) if that point is inside the ball radius, you have a collision.
3) collide the ball with that point, by reflecting the ball direction along the normalised vector (ball.centre - point).
that might be a bit too advanced.
also, for an arkanoid clone, you may need to use more of a ray-tracing technique, so the ball wont go past a brick if it goes too fast. but that's a bit more involved.
Author
Ray Tracing, hmm. I've been playing with it a lot so it isn't too much of a problem. The only problem with Ray tracing is that these are... Rays instead of circle. Look at the picture:
The black ball is the Ball, rectangle the Brick, the lines represent the Rays i have to cast to make it so I won't miss anything. So the center Ray was the closest and the red ball represents where the ball will land. As you can see, it partially overlaps the brick which means the collision detection failed, and there can be problems.
As for detecting whether collision happened or not I can simply do geometrical Line vs Circle like it is Here. In fact I done it long ago, but sole detecting if collision happened is not a problem. The thing is I have to determine whether the ball hit the side of the brick, or stuck onto corner, in which case its direction should be reflected on 45/-45 degree Axis to make it at least semi realistic. But because of many different situations it gets problematic to determine which case it is. That's why I though of taking a bit more advanced way to do it, also as part of increasing my knowledge in game making :).
The black ball is the Ball, rectangle the Brick, the lines represent the Rays i have to cast to make it so I won't miss anything. So the center Ray was the closest and the red ball represents where the ball will land. As you can see, it partially overlaps the brick which means the collision detection failed, and there can be problems.
As for detecting whether collision happened or not I can simply do geometrical Line vs Circle like it is Here. In fact I done it long ago, but sole detecting if collision happened is not a problem. The thing is I have to determine whether the ball hit the side of the brick, or stuck onto corner, in which case its direction should be reflected on 45/-45 degree Axis to make it at least semi realistic. But because of many different situations it gets problematic to determine which case it is. That's why I though of taking a bit more advanced way to do it, also as part of increasing my knowledge in game making :).
I'm not sure that's the algo you want. to be more precise, you would need a ray vs capsule test. If you consider the segment, and add around it a radius equal to the sphere, then you can trace a point from the sphere centre along the sphere direction, and intersect with the capsule. That will give you the time of collision.
furthermore, once you have move the sphere to the point of impact, you can use the method I described to compute the reflected velocity of the ball.
furthermore, once you have move the sphere to the point of impact, you can use the method I described to compute the reflected velocity of the ball.
For intersection tests, you can always check out the gd.net wiki. Although no one seems to have added anything after I started that page, it still lists quite a few resources. There's a test that could be just right for you, if you do not fear maths : a 3D AABB/Sphere swept test. Just take one dimension away and you've got your 2D test =).
Author
If I understand the Capsule idea correctly, Capsule is a line segment with radius, and to check intersection, I have to find the closest point on that line to the shape I want to test intersection against. Then, do a shape-circle test with circle at that closest point position. Basically something like that.
That, though, still leaves me with one problem regarding ray tracing. If I guess correctly, the capsule should be used to get the "Ball's Movement" (sorry for using such experimental terminology). But still if I wanted to do a raycast, I would end up with a problem. All bricks are stored in a grid for increased performance during the collision checks. If the ball is of size 1 pixel I could easily use classical Ray Tracing to determine whether it hits brick or not. But if the ball radius is, let's say, 6 pixels, the ray (going from the centre) would go through empty space at position 2x2, but there is a brick on 1x2 which in theory should be hit, but the ray didn't detect it. So how could I possibly achieve a um, CapsuleRay-Trace? I just can't get it (of course I could do it with 3 or even 2 raycast, but it seem unsatisfying).
Thanks for the advice until now by the way :).
That, though, still leaves me with one problem regarding ray tracing. If I guess correctly, the capsule should be used to get the "Ball's Movement" (sorry for using such experimental terminology). But still if I wanted to do a raycast, I would end up with a problem. All bricks are stored in a grid for increased performance during the collision checks. If the ball is of size 1 pixel I could easily use classical Ray Tracing to determine whether it hits brick or not. But if the ball radius is, let's say, 6 pixels, the ray (going from the centre) would go through empty space at position 2x2, but there is a brick on 1x2 which in theory should be hit, but the ray didn't detect it. So how could I possibly achieve a um, CapsuleRay-Trace? I just can't get it (of course I could do it with 3 or even 2 raycast, but it seem unsatisfying).
Thanks for the advice until now by the way :).
Author
Hm, that I got. The problem is with detecting which grids are affected while doing Ray Trace. Look:
There you have a grided playfield, a Ball and few bricks. The green capsule shows where the ball goes, and the white line shows the ray. Red circles show position of intersection, and violet-colored grid space indicates which grid fields are checked for collision ie, the ones ray travels on. As you can clearly see, even though the ball should hit the leftmost bottom block, the ray doesn't detect it. This could be fixed by instead of sending one ray from the middle of the ball, send two rays from the edges, like here:
Though I am not a big fan of these kind workarounds, so I was wondering if there is some better solution to that problem.
There you have a grided playfield, a Ball and few bricks. The green capsule shows where the ball goes, and the white line shows the ray. Red circles show position of intersection, and violet-colored grid space indicates which grid fields are checked for collision ie, the ones ray travels on. As you can clearly see, even though the ball should hit the leftmost bottom block, the ray doesn't detect it. This could be fixed by instead of sending one ray from the middle of the ball, send two rays from the edges, like here:
Though I am not a big fan of these kind workarounds, so I was wondering if there is some better solution to that problem.
I suppose that would involve expanding the cell dimensions by the ball radius, so you would have overlapping cells, but then a DDA/bresendham algorythm wouldn't work anymore.
However, the two ray-trace will work (as long as the ball radius is < the grid size).
Another method, is just to grab the complete bounding rectangle of the ball trajectory (from start to end), and just find the cells inside that rectangle. It's unlikely the rectangle will cover more than a handful of cells every frame.
There will be a few false positives, but it shouldn't matter.
[Edited by - oliii on June 12, 2008 10:50:12 AM]
However, the two ray-trace will work (as long as the ball radius is < the grid size).
Another method, is just to grab the complete bounding rectangle of the ball trajectory (from start to end), and just find the cells inside that rectangle. It's unlikely the rectangle will cover more than a handful of cells every frame.
There will be a few false positives, but it shouldn't matter.
[Edited by - oliii on June 12, 2008 10:50:12 AM]
Author
I think I'll just check both double-raytrace and this rectangle method and see which one is faster :).
Thanks for all your replies and for these resources. Hopefully next time I stumble upon some difficult problem I'll be able to solve by myself :).
Thanks for all your replies and for these resources. Hopefully next time I stumble upon some difficult problem I'll be able to solve by myself :).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
