How to handle circle penetration

I've been working on circle to circle collision and have gotten the intersection method working correctly, but I'm having problems using the returned values to actually separate the circles from one another.

This is the method which calculates the depth of the circle collision

public static Vector2 GetIntersectionDepth(Circle a, Circle b)
{
float xValue = a.Center.X - b.Center.X;
float yValue = a.Center.Y - b.Center.Y;

Vector2 depth = Vector2.Zero;

float distance = Vector2.Distance(a.Center, b.Center);

{
depth.X = (float)Math.Cos(result);
depth.Y = (float)Math.Sin(result);
}

return depth;
}


This is where I'm trying to apply the values to actually seperate the circles.

Vector2 depth = Vector2.Zero;
for (int i = 0; i < circlePositions.Count; i++)
{
for (int j = 0; j < circlePositions.Count; j++)
{
Circle bounds1 = new Circle(circlePositions[i], circle.Width / 2);
Circle bounds2 = new Circle(circlePositions[j], circle.Width / 2);

if(i != j)
depth = CircleToCircleIntersection.GetIntersectionDepth(bounds1, bounds2);

if (depth != Vector2.Zero)
{
circlePositions[i] = new Vector2(circlePositions[i].X + depth.X, circlePositions[i].Y + depth.Y);
}
}
}


I think the way that makes more sense is to have each circle move back half of the depth, instead of moving only one of the circles.

That should be as easy as adding half of the penetration depth to each circle but in opposite directions:

circlePositions[i] -= depth / 2f;
circlePositions[j] += depth / 2f;


But that's assuming you're calculating the intersection depth correctly. Your method looks a bit shady though. For instance you're calculating those xValueand yValue variables but you're never using them. Either way, here's a simpler implementation:

public static Vector2 GetIntersectionDepth(Circle a, Circle b)
{
Vector2 direction = b.Center - a.Center;
float distance = direction.Length();
direction.Normalize();
return depth > 0 ? depth * direction : Vector2.Zero;
}


There's also a bigger problem at hand which is that when separating the circles you could be creating new intersections between circles that you already handled earlier in the loop.

And to close it off, here's a simplified and optimized version of your loop above (although it still doesn't solve the problem I just mentioned above):

float radius = circle.Width / 2f;
int count = circlePositions.Count;
for (int i = 0; i < count; ++i)
{
for (int j = i + 1; j < count; ++j)
{
Circle bounds1 = new Circle(circlePositions[i], radius);
Circle bounds2 = new Circle(circlePositions[j], radius);
Vector2 depth = GetIntersectionDepth(bounds1, bounds2);
if (depth != Vector2.Zero)
{
Vector2 halfDepth = depth / 2f;
circlePositions[i] -= halfDepth;
circlePositions[j] += halfDepth;
}
}
}

• The complexities of object physics is why we have box2d and other physics engines... because solving problems like this is hard! – Myrddin Emrys Apr 6 '12 at 16:15
• I've edited too many times already so I'll leave this as a comment. I've given all of this code a test run, and it works well. I also found out a quick hack for the problem I mentioned with new collisions being created when others are resolved. I found from experimentation that while calling the collision code only once would often result in the problem described, just by calling it two times in a row made the results a lot more stable. Still some inaccuracies here and there, but overall good enough (hopefully). If it isn't, look into a physics engine ;-) – David Gouveia Apr 6 '12 at 16:16
• Be careful of situations where the act of separating two circles (moving them) just causes new overlaps, which causes new movement, etc. This could turn into a crazy cascade of stuff with a bunch of tightly packed circles. – Tim Holt Apr 6 '12 at 18:37
• @TimHolt Come on, I mentioned that two times in the answer and once in the comments :-P – David Gouveia Apr 6 '12 at 18:49
• Heh - oops I didn't (fully) read the answer :/ Sorry. – Tim Holt Apr 6 '12 at 18:53