Collision Response Woes
Author
I've finally gotten my collision detection system for my game all finished--or at least that's what I thought. I'm doing swept sphere vs line segment intersection (it's actually 2D, so I guess I should call it swept circle), and after a little work I was able to get it working. I then implemented this into the game (there are lots of little circles moving with various velocities that can intersect with lots of little static line segments, some of which are connected into "triangle-like-shapes"). The problem though is that some of the circles "stick" to the line segments. After a while the stuck circles will break free, though sometimes the circle will break free on the other side of the line segment. Either way, it's bad if the circles get stuck.
Each circle's position is defined as C(t)=B+tD, where C(t) is the circle's center at time t, B it the circle's starting position, D is the circle's displacement vector, and t is a parametric value in the range [0, 1]. When a circle intersects a line segment, I get a parametric value that says exactly when they begin to intersect, and then I move the circle to the position where the intersection begins. Then I change the circle's velocity by reflecting it off the line segment, so the circle "bounces off" the line segment. I think the problem is caused by moving the circle to the position where the intersection begins, because, while it usually works just fine, sometimes on the next frame when I test for collisions again, the circle and the line segment are already intersecting (even though they shouldn't be because I handled their intersection in the last frame), causing it to go into a loop that takes some time to break out of.
Does anyone know of a way to fix this? I don't want my circles to get stuck on the line segments... that just makes the game seem retarded. Any help is greatly appreciated!
If your game is really just circles and lines, you can probably deal with the accidental intersections by calculating the penetration depth (radius - distance to line) and pushing the velocity vector along the line's normal vector by that amount, plus a bit more to make sure it actually fully separates.
Also, if you're sliding against the lines, you'll probably want to push the slide velocity vector away from the line a tiny bit to begin with, to reduce the chance of intersecting in the first place. Otherwise you might hit a line, then calculate your velocity parallel to the line, but due to accuracy it's angled slightly toward the line, so you hit it again, and keep on repeating until your recursion gives up.
Also, if you're sliding against the lines, you'll probably want to push the slide velocity vector away from the line a tiny bit to begin with, to reduce the chance of intersecting in the first place. Otherwise you might hit a line, then calculate your velocity parallel to the line, but due to accuracy it's angled slightly toward the line, so you hit it again, and keep on repeating until your recursion gives up.
Your problem is likely due to floating point errors. On top of what has been suggested, you should also compute a parametric value that is slightly less than the computed parametric value. I've never been able to get collision detection and response to work without post-processing the collisions and manually checking for penetrations.
You need to displace your circle's position a little bit away from the intersection so that no circle and line is ever intersecting at the start of a frame.
If you push the circle away from the intersection using the line segment's normal you're going to hit some problems because you may be pushing your circle into another line (imagine two lines forming an acute angle). Likewise, if you just multiply t (time of collision) by 0.99~ when computing your circles new position you're problem will reoccur whenever a constant force is pushing your circle against a wall, because with each successive frame the distance between the line and the resulting circle position will get smaller until you overload the accuracy of whatever data type you are using for your maths.
Thus, I would suggest you subtract your vector D, sized to some graphically-insignificant number (eg 0.01), from your intersection position when calculating your circle's new position. This is essentially moving the circle back along it's path by a fixed amount.
Of course, this only minimises the problem whereby your circle may be displaced into a collision with another line segment. It may still occur when the distance between the original position and the intersection position is smaller that your 0.01. Unfortunately, simply choosing the minimum between that distance and the 0.01 as your displacement will not do due the inaccuracies that come when dealing with tiny numbers.
To fix this problem, then, you need to repeat your swept-circle intersection test using the circle's original position and the circle's new position once your finished dealing with collisions. If an intersection is occurring, you simply leave the circle in it's original position. This is one advantage of ensuring that your circle is always collision-free at the start of a frame - if all else fails you can always fall back on the original position. This tends to happen when you're trying to force the circle into a complicated corner, and produces no noticeable effects because the circle really should not move anyway.
Out of curiosity, how are you dealing with multiple collisions in one frame? For realistic resluts, this method assumes that you are doing this correctly.
If you like I can send you a small working demo, which features a circular character moving around a complicated polygon world.
Hope this helps,
Jackson Allan
If you push the circle away from the intersection using the line segment's normal you're going to hit some problems because you may be pushing your circle into another line (imagine two lines forming an acute angle). Likewise, if you just multiply t (time of collision) by 0.99~ when computing your circles new position you're problem will reoccur whenever a constant force is pushing your circle against a wall, because with each successive frame the distance between the line and the resulting circle position will get smaller until you overload the accuracy of whatever data type you are using for your maths.
Thus, I would suggest you subtract your vector D, sized to some graphically-insignificant number (eg 0.01), from your intersection position when calculating your circle's new position. This is essentially moving the circle back along it's path by a fixed amount.
Of course, this only minimises the problem whereby your circle may be displaced into a collision with another line segment. It may still occur when the distance between the original position and the intersection position is smaller that your 0.01. Unfortunately, simply choosing the minimum between that distance and the 0.01 as your displacement will not do due the inaccuracies that come when dealing with tiny numbers.
To fix this problem, then, you need to repeat your swept-circle intersection test using the circle's original position and the circle's new position once your finished dealing with collisions. If an intersection is occurring, you simply leave the circle in it's original position. This is one advantage of ensuring that your circle is always collision-free at the start of a frame - if all else fails you can always fall back on the original position. This tends to happen when you're trying to force the circle into a complicated corner, and produces no noticeable effects because the circle really should not move anyway.
Out of curiosity, how are you dealing with multiple collisions in one frame? For realistic resluts, this method assumes that you are doing this correctly.
If you like I can send you a small working demo, which features a circular character moving around a complicated polygon world.
Hope this helps,
Jackson Allan
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
