Help required with Math of Collision Detection/Response

Member
Posts: 196
Joined: 2003.10
Post: #1
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:
  • 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
This is where you, oh wise students and professionals who continued in math classes past the age of 17 (rather than pursue artistic dreams of symphony playing and assorted other nonsense), come in.

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!):
[Image: physicsdiagram.gif]

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 pseudo-code):
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.ethe 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)

Does this seem like a reasonable approach? It's not like I'll have thousands of C2's - maybe 8-10 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...
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #2
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.
Quote this message in a reply
Puzzler183
Unregistered
 
Post: #3
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.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #4
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 circle-circle collisions. Circle-wall collisions are not really more difficult, but a little tricky. *showtune* "Tune in next time...."
Quote this message in a reply
Member
Posts: 196
Joined: 2003.10
Post: #5
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?
Quote this message in a reply
Member
Posts: 156
Joined: 2002.11
Post: #6
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.
Quote this message in a reply
Sage
Posts: 1,487
Joined: 2002.09
Post: #7
I always refer people to this, it has nice interactive diagrams.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #8
blobbo Wrote: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?
yes, two circles colliding. For a circle in a circle, you'd check
if d > r1 - r2
and an approximate point of contact would be
X = C1 + D/d*r1
if r1 is the big circle.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Optimize the collision detection alaslipknot 1 5,258 May 12, 2013 08:02 PM
Last Post: SethWillits
  Collision detection tutorial ThemsAllTook 7 26,562 Nov 5, 2011 05:20 PM
Last Post: SethWillits
  Help with Collision Detection..(i'm almost there) carmine 1 6,190 Jun 29, 2011 12:33 PM
Last Post: ThemsAllTook
  Time Delta, collision detection mk12 19 21,437 Sep 8, 2010 06:40 PM
Last Post: AnotherJake
  Collision detection for pinball game johncmurphy 0 5,811 Sep 6, 2009 02:46 PM
Last Post: johncmurphy