Help required with Math of Collision Detection/Response
Ok, folks. So I must admit, while I whine and complain about the complexity of collision detection and response, I never do that much about solving my problems. And there's this game that I really, really really want to program. And I'm tired of getting stuck in projects. So I'm starting this one with collision detection. I want to make sure I understand it in theory before implementing it  that way, I won't get bogged down in some bug I don't understand.
So what does a good geek do? Read up, of course! I poured over collision detection documentation, tutorials, and (*egads*) doctoral dissertations. All this left me with a few basic ideas, namely:
There are two situations that I will face in my game where I will need to detect and respond to collisions. For now, let's concentrate on the first, as I believe it is the easier of the two, and it will allow me to, first and foremost, make something that actually works, albeit in a rudimentary form (a very important goal).
The situation in question is as such (ooh, diagram!):
C1 and C2 are Circle 1 and Circle 2, respectively. R1, R2, and R3 are different radii, although R3 is an artificial Radius conceived simply for accurate collisions.
As it stands, the steps to take in order to detect a collision are the following (in very pseudocode):
Does this seem like a reasonable approach? It's not like I'll have thousands of C2's  maybe 810 at the absolute maximum. It seems like a relatively efficient routine, especially given that most of them will likely not get past the if statement.
Now what I need help with: you'll notice that the code quickly gets sketchy. For the life of me, I don't understand how to step backwards to find the exact collision point, and I have absolutely NO clue how to detect the resulting vector or adjust it accordingly to account for the stepping back. Anyone have some sample code for this, or a good tutorial that explains it with source code (the implementation details are important here). Thanks in advance...
So what does a good geek do? Read up, of course! I poured over collision detection documentation, tutorials, and (*egads*) doctoral dissertations. All this left me with a few basic ideas, namely:
 How the general collision system works
 What one has to do in order to predict and respond to collisions in a way that the end user doesn't feel neglected
 Implementing a full, realistic physics simulation is unnecessary, and will actually make the game less playable. In short, code only what you need.
 The absolute, sheer complexity of the math involved
There are two situations that I will face in my game where I will need to detect and respond to collisions. For now, let's concentrate on the first, as I believe it is the easier of the two, and it will allow me to, first and foremost, make something that actually works, albeit in a rudimentary form (a very important goal).
The situation in question is as such (ooh, diagram!):
C1 and C2 are Circle 1 and Circle 2, respectively. R1, R2, and R3 are different radii, although R3 is an artificial Radius conceived simply for accurate collisions.
As it stands, the steps to take in order to detect a collision are the following (in very pseudocode):
PHP Code:
initial position = C2.position;
projected position = C2.position + C2.distance_to_travel;
if ((distance from projected_position to center of C1) > R3 (we have gone past the bounds of C1))
{
recurse backwards until we find where C2 exactly hits C1;
store the distance backwards we had to step in order to find the exact collision point;
determine the collision response (i.e. the resulting direction vector for C2);
adjust C2's position so that it appears that it bounced off the wall (in other words, account for stepping backwards trying to find the exact collision point)
}
Now what I need help with: you'll notice that the code quickly gets sketchy. For the life of me, I don't understand how to step backwards to find the exact collision point, and I have absolutely NO clue how to detect the resulting vector or adjust it accordingly to account for the stepping back. Anyone have some sample code for this, or a good tutorial that explains it with source code (the implementation details are important here). Thanks in advance...
If you want to make things a little simpler for yourself, don't worry about finding the exact collision point just check if the projected position is outside of C1 and if so then don't move the object just change its velocity. This approximation is usually close enough unless your objects are moving very fast.
Now, the tough part is finding the appropriate velocity after bouncing, though I believe that has been discussed before on the boards. The basic idea is that you have the normal n of the surface the circle is bouncing off of (that is, find (C1.center  C2.center) and normalize it.) And you just want to reflect the velocity of the circle off of it.
If you know a bit of linear algebra, the description is fairly easy you break up the velocity of C2 into two components that which is going parallel to the normal n as listed above, and that which is going perpendicular to it. You would keep the part that's going parallel to n and reverse the part that's going perpendicular and you're done.
You can break that velocity into components using the dot product. If you take the dot product of n and the velocity, you get the magnitude of the component of the velocity parallel to n (also known as the projection of the velocity on n.)
If nobody has any tutorials I can post in detail how you can do this, but someone probably has already described this.
Now, the tough part is finding the appropriate velocity after bouncing, though I believe that has been discussed before on the boards. The basic idea is that you have the normal n of the surface the circle is bouncing off of (that is, find (C1.center  C2.center) and normalize it.) And you just want to reflect the velocity of the circle off of it.
If you know a bit of linear algebra, the description is fairly easy you break up the velocity of C2 into two components that which is going parallel to the normal n as listed above, and that which is going perpendicular to it. You would keep the part that's going parallel to n and reverse the part that's going perpendicular and you're done.
You can break that velocity into components using the dot product. If you take the dot product of n and the velocity, you get the magnitude of the component of the velocity parallel to n (also known as the projection of the velocity on n.)
If nobody has any tutorials I can post in detail how you can do this, but someone probably has already described this.
You don't really so much step back in time as you just calculate the collision point. http://www.flipcode.com/ has an article on it I believe, so try searching there.
I dont see why you would need stepping back in this simple case. Assuming you have 2 circles with radii r1 and r2, they collide
if d < r1 + r2
where D = C2  C1, d = length(D)
and the approximate point of collision is
X = C1 + D*r1/(r1+r2)
With circles, you dont really need the exact time of collision, as the collision normal (parallel to D, in this case) is independent of how much they intersect.
For collision response, you need to divide the velocity vectors into parts parellel and perpendicular to D, and leave those perpendicular to D alone (unless you have friction), and negate the other parts (or do more complex stuff if you have mass, etc).
Then, there is some fallbacks with this approach. First of all, if the circles are too fast, you won't get accurate results, as circles could miss each other, but as long as v_max*dt < r_min, you're on the safe side. If you only have a handful of objects, this restriction should not really matter, as you could make the time steps (dt) very small. If you want to detect absolutely all potential collisions, you have to venture into the domain of continous time collision detection, which is probably a little much for starters.
By the way, the above goes for circlecircle collisions. Circlewall collisions are not really more difficult, but a little tricky. *showtune* "Tune in next time...."
if d < r1 + r2
where D = C2  C1, d = length(D)
and the approximate point of collision is
X = C1 + D*r1/(r1+r2)
With circles, you dont really need the exact time of collision, as the collision normal (parallel to D, in this case) is independent of how much they intersect.
For collision response, you need to divide the velocity vectors into parts parellel and perpendicular to D, and leave those perpendicular to D alone (unless you have friction), and negate the other parts (or do more complex stuff if you have mass, etc).
Then, there is some fallbacks with this approach. First of all, if the circles are too fast, you won't get accurate results, as circles could miss each other, but as long as v_max*dt < r_min, you're on the safe side. If you only have a handful of objects, this restriction should not really matter, as you could make the time steps (dt) very small. If you want to detect absolutely all potential collisions, you have to venture into the domain of continous time collision detection, which is probably a little much for starters.
By the way, the above goes for circlecircle collisions. Circlewall collisions are not really more difficult, but a little tricky. *showtune* "Tune in next time...."
Wow, quick replies. Hold on while I attempt to digest what you've written...
DoG: The situation you're referring to would be two circle's collisions, correct? Not a circle within another circle?
DoG: The situation you're referring to would be two circle's collisions, correct? Not a circle within another circle?
There's an article on Gamasutra about physics for a pool game that shows how to perform collision detection and find the point of contact between two spheres, or circles in your case.
I always refer people to this, it has nice interactive diagrams.
blobbo Wrote:Wow, quick replies. Hold on while I attempt to digest what you've written...yes, two circles colliding. For a circle in a circle, you'd check
DoG: The situation you're referring to would be two circle's collisions, correct? Not a circle within another circle?
if d > r1  r2
and an approximate point of contact would be
X = C1 + D/d*r1
if r1 is the big circle.
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Optimize the collision detection  alaslipknot  1  5,752 
May 12, 2013 08:02 PM Last Post: SethWillits 

Collision detection tutorial  ThemsAllTook  7  27,438 
Nov 5, 2011 05:20 PM Last Post: SethWillits 

Help with Collision Detection..(i'm almost there)  carmine  1  6,556 
Jun 29, 2011 12:33 PM Last Post: ThemsAllTook 

Time Delta, collision detection  mk12  19  23,621 
Sep 8, 2010 06:40 PM Last Post: AnotherJake 

Collision detection for pinball game  johncmurphy  0  6,030 
Sep 6, 2009 02:46 PM Last Post: johncmurphy 