Collision Detection -- Once again...
Hi,
I am doing a "simple" 2D collision detection between a ball (which the player controls) and some rectangular objects. So far so easy: I simply do an overlap check of a circle and a box.
But: What happens on slow machines where the framerate is going down and the ball might accidentally hop from one side of the rectangle to the the other side, without actually overlapping it?
Is there a way of a "sweep" check for spheres (or circles in my case) and rectangles? Something like: "If the ball is on one side of the box and in the next frame, it is on the other side, then a collision has occured. So, first draw the ball at the box and then reflect it."
One thing I found was a sweep test for spheres and planes. The basic idea being: you have two distances d0 and d1, d0 ist the distance between the sphere and the plane in frame 0, d1 is the distance between the sphere and the plane in frame 1. Now, if I had the normal vector, I could do something like if d0 > radius and d1 < radius then the sphere passed through the plane.
Can I somehow adapt this to rectangles? How do I compute the normal vectors (yes, my linear algebra is pretty lousy---that's why I went for 2D first ;-)).
Thanks for any pointers/hints or complete source fragments ;-)) [just kidding: Any help is greatly appreciated! Thanks!!]
Beren
The simple method is overlap test, this doesn't work if the objects are small and their speed is high as eg. a ball can be on one side of a wall in one frame and completely on the other side the next frame.
The traditional approach is to make a line segment between old position and new position and then to test whether this line segment intersects any of the objects bounding box/bounding sphere.
The traditional approach is to make a line segment between old position and new position and then to test whether this line segment intersects any of the objects bounding box/bounding sphere.
Method 1:
The ideal way of doing this is to do an interpolation by velocity and time of each object from where they are now and to where they will be next frame. If they collide at any point along that line, a collision will occur (called time gradient collision detection). This is, however, very tricky and time consuming.
Method 2:
Another way of doing this (described above) is to construct a line between the current and future positions and if the lines cross between the line segments, a collision is likely to have occurred. The problem with this is it treats these objects as points and interpolates them at the incorrect velocity. (So they might actually not hit each other, but it will probably look like they could hit each other)
Method 3:
Another algorithm I used about 3 years ago might be more applicable to you, treat one object as "stationary" (i.e. a low velocity object which is unlikely to jump/teleport much in one frame) and the other (high velocity) object as a point. Create the line segment from where the object is and where it will be and check the line segment for collision with the "stationary" object.
I'll describe the most accurate algorithm (Method 1) in more detail (requires some vector math):
(Note a prefix of 'v' is a vector, all other values are scalar)
Let's say we have two circles/spheres with position vP1 and vP2, velocity vV1 and vV2 radius R1 and R2.
The line segments between where they are and where they will be can be described by the lines:
vL1 = vP1 + t * ( vV1 )
vL2 = vP2 + t * ( vV2 )
where t is the delta-time. (The segment where the sphere collision will be tested is t such that t is between 0 & 1)
Let there be a point X1 on L1 and a point X2 on L2 at time t = T. Therefore if |vX2 - vX1| <= R1 + R2 for any value of t such that (0 < t < 1) the spheres have collided on that line segment.
i.e. |vX2 - vX1| - R1 - R2 <= 0
Therefore since X2 - X1 = P2 - P1 + T * ( V2 - V1 )
Set |vX2 - vX1| - R1 - R2 = 0
therefore |P2 - P1 + T * ( V2 - V1 )| - R1 - R2 = 0
Expand and simplify.
If T is between 0 and 1, a collision has occured in the last frame.
There are similar collision detection algorithms for bounding boxes and points.
The simpler algorithm which may be more appropriate for you follows (Method 3):
Let's say we have an object which can be described as a sphere but we will treat as a point for simplicity, with position vP1 and velocity vV1.
Now construct the line segment for the moving point:
vL1 = vP1 + t * ( vV1 )
Then lets say we have an axis aligned bounding box with bounds vMin(x1, y1) and vMax(x2, y2).
Let's also create two more points to simplify the calculations:
vTopLeft(x1, y2)
vBottomRight(x2, y1)
From this we construct line segments representing each of the edges of the bounding boxes:
vTop = vTopLeft + x * ( vMax - vTopLeft )
vBottom = vMin + x * ( vBottomRight - vMin )
vLeft = vTopLeft + x * ( vMin - vTopLeft )
vRight = vMax + x * ( vBottomRight - vMax )
where x is an arbitrary interpolation variable. (The segment where the collision will be tested is x such that x is between 0 & 1)
Now simply test whether any of the line segments intersect between the values of 0 < x < 1.
Ask if you need any more help (there is also a non-vector based definition of Method 3, if you are uncomfortable with vector math but it's more messy).
If anyone thinks this is wrong, please correct me, it's been a while since I last had to write a collision detection algorithm and I don't really have my code handy atm.
I couldn't find any really good articles on the subject but here's what I found:
http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.gamedev.net/reference/articles/article735.asp
http://www.gamedev.net/reference/articles/article736.asp
http://graphics.idav.ucdavis.edu/research/VADOP
[Edited by - Leo_E_49 on August 23, 2005 7:18:16 AM]
The ideal way of doing this is to do an interpolation by velocity and time of each object from where they are now and to where they will be next frame. If they collide at any point along that line, a collision will occur (called time gradient collision detection). This is, however, very tricky and time consuming.
Method 2:
Another way of doing this (described above) is to construct a line between the current and future positions and if the lines cross between the line segments, a collision is likely to have occurred. The problem with this is it treats these objects as points and interpolates them at the incorrect velocity. (So they might actually not hit each other, but it will probably look like they could hit each other)
Method 3:
Another algorithm I used about 3 years ago might be more applicable to you, treat one object as "stationary" (i.e. a low velocity object which is unlikely to jump/teleport much in one frame) and the other (high velocity) object as a point. Create the line segment from where the object is and where it will be and check the line segment for collision with the "stationary" object.
I'll describe the most accurate algorithm (Method 1) in more detail (requires some vector math):
(Note a prefix of 'v' is a vector, all other values are scalar)
Let's say we have two circles/spheres with position vP1 and vP2, velocity vV1 and vV2 radius R1 and R2.
The line segments between where they are and where they will be can be described by the lines:
vL1 = vP1 + t * ( vV1 )
vL2 = vP2 + t * ( vV2 )
where t is the delta-time. (The segment where the sphere collision will be tested is t such that t is between 0 & 1)
Let there be a point X1 on L1 and a point X2 on L2 at time t = T. Therefore if |vX2 - vX1| <= R1 + R2 for any value of t such that (0 < t < 1) the spheres have collided on that line segment.
i.e. |vX2 - vX1| - R1 - R2 <= 0
Therefore since X2 - X1 = P2 - P1 + T * ( V2 - V1 )
Set |vX2 - vX1| - R1 - R2 = 0
therefore |P2 - P1 + T * ( V2 - V1 )| - R1 - R2 = 0
Expand and simplify.
If T is between 0 and 1, a collision has occured in the last frame.
There are similar collision detection algorithms for bounding boxes and points.
The simpler algorithm which may be more appropriate for you follows (Method 3):
Let's say we have an object which can be described as a sphere but we will treat as a point for simplicity, with position vP1 and velocity vV1.
Now construct the line segment for the moving point:
vL1 = vP1 + t * ( vV1 )
Then lets say we have an axis aligned bounding box with bounds vMin(x1, y1) and vMax(x2, y2).
Let's also create two more points to simplify the calculations:
vTopLeft(x1, y2)
vBottomRight(x2, y1)
From this we construct line segments representing each of the edges of the bounding boxes:
vTop = vTopLeft + x * ( vMax - vTopLeft )
vBottom = vMin + x * ( vBottomRight - vMin )
vLeft = vTopLeft + x * ( vMin - vTopLeft )
vRight = vMax + x * ( vBottomRight - vMax )
where x is an arbitrary interpolation variable. (The segment where the collision will be tested is x such that x is between 0 & 1)
Now simply test whether any of the line segments intersect between the values of 0 < x < 1.
Ask if you need any more help (there is also a non-vector based definition of Method 3, if you are uncomfortable with vector math but it's more messy).
If anyone thinks this is wrong, please correct me, it's been a while since I last had to write a collision detection algorithm and I don't really have my code handy atm.
I couldn't find any really good articles on the subject but here's what I found:
http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.gamedev.net/reference/articles/article735.asp
http://www.gamedev.net/reference/articles/article736.asp
http://graphics.idav.ucdavis.edu/research/VADOP
[Edited by - Leo_E_49 on August 23, 2005 7:18:16 AM]
It looks like Leo gave you the circle-circle swept test, which may also be useful to you. Circle-rectangle is a little more complicated, but not too much. I can tell you more about that if you're interested.
In short, swept tests for circles and rectangles are quite practical both in terms of implementation and performance, so don't hesitate to add them to your game.
In short, swept tests for circles and rectangles are quite practical both in terms of implementation and performance, so don't hesitate to add them to your game.
Hi,
thanks for your replies (especially yours, Leo! That's what I need to get me started.)
@jyk: Yes, I am interested :) -- If you have the time to post the Sphere/Rectangle algorithm, that would be great! Otherwise, I have plenty of material to play around with already... (In my head a Collision class is forming and I see some static methods in it... ;-)).
Great work guys!
Thanks again!
thanks for your replies (especially yours, Leo! That's what I need to get me started.)
@jyk: Yes, I am interested :) -- If you have the time to post the Sphere/Rectangle algorithm, that would be great! Otherwise, I have plenty of material to play around with already... (In my head a Collision class is forming and I see some static methods in it... ;-)).
Great work guys!
Thanks again!
Ok, I'll give the circle-rectangle collision detection a go (just off the top of my head). Again, it's been a while, so if anyone here sees it as wrong, please correct me. (Note, this is for use with oriented bounding boxes)
To start with, we have to define how a sphere collides with a line segment.
Let's say we have a sphere with position vP1, velocity vV1 and radius R1.
We have a line segment between two points vL1 and vL2, defined by:
vLS = vL1 + x * ( vL2 - vL1 )
where x is an arbitrary interpolation variable. ( 0 <= x <= 1 ).
The line vL of the sphere's centre at any given time t is given by:
vL = vP1 + t * ( vV1 )
where t is the time delta. (where 0 <= t <= 1 is the line segment for testing in the next frame)
Let vX be the position of the sphere's centre at time T.
A collision will have occurred if the perpendicular distance from the line segment to the sphere's centre is <= R1.
I am assuming that you know the following formula, I am listing it for reference purposes however, in case a beginner at vector math wishes to understand this principle. (It's also good revision for me [grin])
In order to find the perpendicular distance we need to have an arbitrary line and point vP: (Also note, the sphere's radius is denoted by R)
vA = vB + s * ( vC - vB )
Let vQ be a point on the line such that s = S.
For the perpendicular distance, the vector ( vP - vQ ) must be perpendicular to the line vA. Therefore ( vP - vQ ) . ( vC - vB ) = 0, giving us a value for S.
Then the resulting distance | vP - vQ | is the perpendicular distance from the point to the line. If this is <= R then a collision may have occurred. Because we are testing a line segment, if S is outside the range 0 <= S <= 1 we can do a further check of whether
| vP - vB | <= R and
| vP - vC | <= R for the ends of the segment. If all of these fail, we reject the collision. You can substitute the formula for vX in here to get the exact value of T (and thus the position of vX) on collision. (i.e. Let | vX - vQ | - R1 = 0 or | vX - vL1 | - R1 = 0 or | vX - vL2 | - R1 = 0 respectively)
Let's assume we've already calculated this forumula for the above case and the resulting vX is at a position where it's perpendicular distance from the line is = R1. If the value of T is such that 0 <= T <= 1, a collision will occur at position vX in the next frame.
This test should be repeated for each of the four line segments which makes up the sides of the bounding box. As with the circle-circle collision check, we don't have to worry about overlap or the sphere moving through the line because we always receive the exact (time based) point of collision from this test.
A similar test can be done for a plane segment in 3D but I won't go into detail on that. Basically, you just substitute a sphere-plane segment collision test for the circle-line collision test and repeat 6 instead of 4 times.
Also, there are similar bounding box-bounding box collision algorithms but they get slightly tricky and I'm not sure I could accurately describe them on the forum. I'm sure someone here has a website on them though.
There is another (simpler and more efficient) formula which deals with axis aligned bounding boxes but I felt that this approach would be more educational, I'm sure after taking a look at this you will have no problem in extrapolating the simpler algorithm. Also, my algorithm is probably not the best out there, it's quite inefficient. If anyone knows of a better algorithm, I would be very interested in hearing it. I'm still quite an amateur at this sort of thing.
[Edited by - Leo_E_49 on August 23, 2005 9:48:11 PM]
To start with, we have to define how a sphere collides with a line segment.
Let's say we have a sphere with position vP1, velocity vV1 and radius R1.
We have a line segment between two points vL1 and vL2, defined by:
vLS = vL1 + x * ( vL2 - vL1 )
where x is an arbitrary interpolation variable. ( 0 <= x <= 1 ).
The line vL of the sphere's centre at any given time t is given by:
vL = vP1 + t * ( vV1 )
where t is the time delta. (where 0 <= t <= 1 is the line segment for testing in the next frame)
Let vX be the position of the sphere's centre at time T.
A collision will have occurred if the perpendicular distance from the line segment to the sphere's centre is <= R1.
I am assuming that you know the following formula, I am listing it for reference purposes however, in case a beginner at vector math wishes to understand this principle. (It's also good revision for me [grin])
In order to find the perpendicular distance we need to have an arbitrary line and point vP: (Also note, the sphere's radius is denoted by R)
vA = vB + s * ( vC - vB )
Let vQ be a point on the line such that s = S.
For the perpendicular distance, the vector ( vP - vQ ) must be perpendicular to the line vA. Therefore ( vP - vQ ) . ( vC - vB ) = 0, giving us a value for S.
Then the resulting distance | vP - vQ | is the perpendicular distance from the point to the line. If this is <= R then a collision may have occurred. Because we are testing a line segment, if S is outside the range 0 <= S <= 1 we can do a further check of whether
| vP - vB | <= R and
| vP - vC | <= R for the ends of the segment. If all of these fail, we reject the collision. You can substitute the formula for vX in here to get the exact value of T (and thus the position of vX) on collision. (i.e. Let | vX - vQ | - R1 = 0 or | vX - vL1 | - R1 = 0 or | vX - vL2 | - R1 = 0 respectively)
Let's assume we've already calculated this forumula for the above case and the resulting vX is at a position where it's perpendicular distance from the line is = R1. If the value of T is such that 0 <= T <= 1, a collision will occur at position vX in the next frame.
This test should be repeated for each of the four line segments which makes up the sides of the bounding box. As with the circle-circle collision check, we don't have to worry about overlap or the sphere moving through the line because we always receive the exact (time based) point of collision from this test.
A similar test can be done for a plane segment in 3D but I won't go into detail on that. Basically, you just substitute a sphere-plane segment collision test for the circle-line collision test and repeat 6 instead of 4 times.
Also, there are similar bounding box-bounding box collision algorithms but they get slightly tricky and I'm not sure I could accurately describe them on the forum. I'm sure someone here has a website on them though.
There is another (simpler and more efficient) formula which deals with axis aligned bounding boxes but I felt that this approach would be more educational, I'm sure after taking a look at this you will have no problem in extrapolating the simpler algorithm. Also, my algorithm is probably not the best out there, it's quite inefficient. If anyone knows of a better algorithm, I would be very interested in hearing it. I'm still quite an amateur at this sort of thing.
[Edited by - Leo_E_49 on August 23, 2005 9:48:11 PM]
Leo, I didn't make it all the way through your example, but I thought I'd throw a couple of things out. Although circle-line intersections can probably be formulated in the way you describe, the OP may have an easier time with an alternate approach which is quite a bit easier.
With boxes (oriented or axis aligned), we typically have the unit-length basis vectors available, and therefore the unit-length normals to the edges. Given this information, intersection between a circle and a line can be reduced to some very simple (and efficient) algebra.
If the circle hits the (infinite) line past one of the endpoints of the segment, a further swept test must be done to determine whether the circle will hit the corner of the box. A swept circle vs. point test can be formulated as a quadratic equation which gives the first time of intersection.
I don't know that I have any circle/box code handy at the moment, otherwise I'd post an example. My suggestion though would be to start with the circle vs. infinite line test and get that working first, as that will be the basis for your circle/box test.
With boxes (oriented or axis aligned), we typically have the unit-length basis vectors available, and therefore the unit-length normals to the edges. Given this information, intersection between a circle and a line can be reduced to some very simple (and efficient) algebra.
If the circle hits the (infinite) line past one of the endpoints of the segment, a further swept test must be done to determine whether the circle will hit the corner of the box. A swept circle vs. point test can be formulated as a quadratic equation which gives the first time of intersection.
I don't know that I have any circle/box code handy at the moment, otherwise I'd post an example. My suggestion though would be to start with the circle vs. infinite line test and get that working first, as that will be the basis for your circle/box test.
Oh, ingenious! [grin] Certainly better than my way of doing things. Although I do use a line-circle intersection too, so you can use that code the way jyk described.
Btw I didn't finish the above algorithm [embarrass], it assumes the bounding box is stationary or low velocity. However when you have a high velocity box, a number of things change:
Firstly, let's say we have a bounding box described by a position vPB, and two vectors vW and vH as well as a velocity vVB.
The motion of the box is described such that:
vL = vPB + t * ( vVB )
where t is the time delta.
Let vR be the position of the box at time t = T.
To get the corner points of the bounding box we must use the vW and vH vectors:
vTL = vR - vW + vH
vTR = vR + vW + vH
vBL = vR - vW - vH
vBR = vR + vW - vH
Then we can substitute these swept values for the corners of the bounding boxes into the above formulae in place of vL1 and vL2.
This should make the above formulae applicable for use when the bounding box is travelling at high velocity as well.
[Edited by - Leo_E_49 on August 24, 2005 2:45:03 AM]
Btw I didn't finish the above algorithm [embarrass], it assumes the bounding box is stationary or low velocity. However when you have a high velocity box, a number of things change:
Firstly, let's say we have a bounding box described by a position vPB, and two vectors vW and vH as well as a velocity vVB.
The motion of the box is described such that:
vL = vPB + t * ( vVB )
where t is the time delta.
Let vR be the position of the box at time t = T.
To get the corner points of the bounding box we must use the vW and vH vectors:
vTL = vR - vW + vH
vTR = vR + vW + vH
vBL = vR - vW - vH
vBR = vR + vW - vH
Then we can substitute these swept values for the corners of the bounding boxes into the above formulae in place of vL1 and vL2.
This should make the above formulae applicable for use when the bounding box is travelling at high velocity as well.
[Edited by - Leo_E_49 on August 24, 2005 2:45:03 AM]
Great! Thanks for all the help!
I have implemented a first version of the intersection test and it (seems to) work(s). :-)
I will do some more testing but up to now, I could not find any problems *knock on wood*.
Thanks again!
Beren
I have implemented a first version of the intersection test and it (seems to) work(s). :-)
I will do some more testing but up to now, I could not find any problems *knock on wood*.
Thanks again!
Beren
Hey guys,
very informative post you have going here...
I'm working on something pretty similar at the moment (2d spaceship fighter thingy).
In the answers you've given, you've only mentioned working with bounding boxes/circles. Can the methods you've described work (easily) with pixel perfect collision?
I'm working on something that seems to be goign ok at the moment, but it would be nice to hear of something better from people who clearly know what they're talking about.
Cheers,
James
P.S. or maybe i should be considering using bounding boxes? i just dont want situations where bullets collide with space....
very informative post you have going here...
I'm working on something pretty similar at the moment (2d spaceship fighter thingy).
In the answers you've given, you've only mentioned working with bounding boxes/circles. Can the methods you've described work (easily) with pixel perfect collision?
I'm working on something that seems to be goign ok at the moment, but it would be nice to hear of something better from people who clearly know what they're talking about.
Cheers,
James
P.S. or maybe i should be considering using bounding boxes? i just dont want situations where bullets collide with space....
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement