Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In one of my projects I have a game area in the shape of a circle. Inside this circle another small circle is moving around. What I want to do is keep the small circle from moving outside the bigger one. Below you can see that in frame 2 the small circle is partly outside, I need a way to move it back to just before it is about to move outside. How can this be done?

Basic example

Also, I need the collision point along the arc of the big circle so that I can update the small circle's velocity. How would one go about calculating this point?

What I would like to do is before moving the small circle, I predict its next position and if it is outside I find the time of collision between t=0 and t=1 (t=1 full time step). If I have the collision time t then I just move the small circle during t instead of a full time step. But again, the problem is I don't know how to detect at that time the collision occurs when it comes to two circles and one being inside the other.

Thanks in advance.

EDIT:

Example of collision point (green) I want to find. Maybe the picture is a bit off but you get the idea.

enter image description here

share|improve this question
add comment

4 Answers 4

up vote 10 down vote accepted

Let's assume the large circle has centre A and radius R and the small circle has centre B and radius r moving towards location C.

There is an elegant way to solve this problem, using Minkovski sums (subtractions, actually): replace the disc of radius R with a disc of radius R-r, and the disc of radius r with a disc of radius 0, ie. a simple point located at B. The problem becomes a line-circle intersection problem.

You then just need to check whether distance AC is smaller than R-r. If it is, the circles do not collide. If it is larger, just find the point D on BC at distance R-r of A and this is the new location of the centre of your small circle. This is equivalent to finding k such that:

  vec(BD) = k*vec(BC)
and
  norm(vec(AD)) = R-r

Substituting vec(AD) with vec(AB) + vec(BD) gives:

AB² + k² BC² + 2k vec(AB).vec(BC) = (R-r)²

Provided the initial position was inside the large circle, this quadratic equation in k has one positive root. Here is how to solve the equation, in pseudocode:

b = - vec(AB).vec(BC) / BC²    // dot product
c = (AB² - (R-r)²) / BC²
d = b*b - c
k = b - sqrt(d)
if (k < 0)
    k = b + sqrt(d)
if (k < 0)
    // no solution! we must be slightly out of the large circle

With this value of k, the small circle's new centre is at D such that BD = kBC.

Edit: add quadratic equation solution

share|improve this answer
    
Thanks, it does look elegant but I am not quite sure I understand. For example: "just find the point D on BC at distance R-r of A". I drew a picture to try to understand better. So if we start at B (A.X, A.Y-(R-r)) and C is where we will end up with the current velocity. The way I understand the quoted text: Find a point D on the line segment BC that is a distance of R-r away from A. But the way I see it on the picture I drew is that only exactly B is R-r away from A. All others points will be > R-r away from A. What am I missing? –  dbostream May 26 '12 at 17:04
    
@dbostream You aren't missing anything. If the two circles are already in contact then there is no real collision to detect: the collision happens in B, and k=0. Now if it is collision resolution you want, I haven't covered that in my answer because it would require knowledge about the physical properties of the objects. What is supposed to happen? Should the inner circle bounce inside? Or roll? Sweep? –  Sam Hocevar May 26 '12 at 20:31
    
I want the small circle to start sliding along the arc of the big circle. So if I am not mistaken I want the collision point on the arc of the big circle so I can use its normal to update the velocity. –  dbostream May 26 '12 at 22:49
    
@dbostream if the movement should be constrained in such a way then I suggest you follow that constraint as soon as possible: if the velocity is V, make the inner circle advance V*t along the circumference of the R-r circle. This means a rotation of angle V*t/(R-r) radians around point A. And the velocity vector can be rotated in the same way. No need to know the normal (which is always oriented towards the centre of the circle anyway) or to update the velocity in any other way. –  Sam Hocevar May 27 '12 at 1:37
    
I still need to move the small circle to the collision point before rotating. And when I tried to rotatate the position using a rotation matrix the new position was not exactly (but almost) R-r away from the center of the big circle, but that tiny difference was enough to make my collision test fail on the next run. Do I have to rotate the position to find the new one, is it not possible to use vector operations like you can if something collide with a straight wall? –  dbostream May 27 '12 at 16:22
show 7 more comments

Say the big circle is circle A and the small circle is circle B.

Check to see if B is inside A:

distance = sqrt((B.x - A.x)^2 + (B.y - A.y)^2))
if(distance > A.Radius + B.Radius) { // B is outside A }

If in frame n-1 B was inside A and in frame n B is outside A and the time between frames wasn't too big (aka B wasn't moving too fast) we can approximate the point of collision by just finding the Cartesian coordinates of B relative to A:

collision.X = B.X - A.X;
collision.Y = B.Y - A.Y;

We can then convert this points to an angle:

collision.Normalize(); //not 100% certain if this step is necessary     
radians = atan2(collision.Y, collision.X)

If you want to know more exactly at what t B is outside A for the first time you could do a ray-circle intersection every frame and then compare if the distance from B to the point of collision is bigger then the distance B can travel given it's current speed. If so you can calculate the exact time of collision.

share|improve this answer
    
Thanks, but is it really correct to shoot a ray from the center of the small circle when doing that intersection test? Won't we end up with the scenario in the middle of this picture? I mean the first point on the arc of the small circle to collide with the big circle is not necessarily the one on the arc in the direction of speed. I think I need something like in the bottom scenario of the picture I linked to. I have added a new picture in the first post showing an example of what I think I need. –  dbostream May 26 '12 at 14:31
    
Hmm I suppose that scenario is possible. Maybe test with a new circle C that has B.Radius + the max movement of B this frame, check if that collides with A and then workout the point on C that is furthers from A. (Haven't tried this btw) –  Roy T. May 26 '12 at 16:50
3  
Using less words: if(distance(A,B)) > (Ra-Rb) a collision happens and you just move the small circle to get a distance equal to Ra-Rb. Else you move the small circle normally. By the way @dbostream you are using something similar to a simplified form of Speculative Contacts, try searching for that. –  Darkwings May 26 '12 at 22:45
    
@Darkwings +1 you're so absolutely right, and that makes it sound much simpler! –  Roy T. May 27 '12 at 9:18
    
It sounds simple because I stripped off all the base geometry needed. Instead of naming it 'collision' you could have named it boundAB since that's what it actually is: the free vector AB bound to (0,0). Once you normalize it you get both the equation for the parallel to AB bundle of straight lines and also a useful unit vector. Then you can multiply that unit vector for any distance D and add the newly found paramenters to A finding the collision point you need: C(Ax+Dx, Ay+Dy). Now it sounds more complicated but it's the same thing :P –  Darkwings May 27 '12 at 12:36
show 7 more comments

Let (Xa,Ya) the position of the big circle and it's radius R, and (Xb,Yb) the position of the smaller circle and it's radius r.

You can check if these two circles collide if

DistanceTest = sqrt(((Xa - Xb) ^ 2) + ((Ya - Yb) ^ 2)) >= (R - r)

To find out the position of collision, find the exact time moment when the circles collide, by using a binary search but with a fixed number of steps. Depending on how your game is made, you can optimize this part of the code (i provided this solution to be independent of how the small ball behaves. If it has constant acceleration, or constant speed, this part of the code can be optimized and replaced with a simple formula).

left = 0 //the frame with no collision
right = 1 //the frame after collision
steps = 8 //or some other value, depending on how accurate you want it to be
while (steps > 0)
    checktime = left + (right - left) / 2
    if DistanceTest(checktime) is inside circle //if at the moment in the middle of the interval [left;right] the small circle is still inside the bigger one
        then left = checktime //the collision is after this moment of time
        else right = checktime //the collision is before
    steps -= 1
finaltime = left + (right - left) / 2 // the moment of time will be somewhere in between, so we take the moment in the middle of interval to have a small overall error

Once you know the collision time, compute the positions of the two circles at the final time and the final collision point is

CollisionX = (Xb - Xa)*R/(R-r) + Xa
CollisionY = (Yb - Ya)*R/(R-r) + Ya
share|improve this answer
add comment

I've implemented a demo of a ball bouncing in a circle on jsfiddle using the algorithm described by Sam Hocevar:

http://jsfiddle.net/klenwell/3ZdXf/

Here's the javascript that identifies the point of contact:

find_contact_point: function(world, ball) {
    // see http://gamedev.stackexchange.com/a/29658
    var A = world.point();
    var B = ball.point().subtract(ball.velocity());
    var C = ball.point();
    var R = world.r;
    var r = ball.r;

    var AB = B.subtract(A);
    var BC = C.subtract(B);
    var AB_len = AB.get_length();
    var BC_len = BC.get_length();

    var b = AB.dot(BC) / Math.pow(BC_len, 2) * -1;
    var c = (Math.pow(AB_len, 2) - Math.pow(R - r, 2)) / Math.pow(BC_len, 2);
    var d = b * b - c;
    var k = b - Math.sqrt(d);

    if ( k < 0 ) {
        k = b + Math.sqrt(d);
    }

    var BD = C.subtract(B);
    var BD_len = BC_len * k;
    BD.set_length(BD_len);

    var D = B.add(BD);
    return D;
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.