Collision Detection/Resolution

I am making a 2D top-down game and I am looking for some help in regards to the collision resolution between two moving (circular) objects.

Basically, what I am trying to achieve is the effect of large groups of enemies which "cluster" behind one another naturally rather than moving through or on top of each other. I'm not looking for anything sophisticated like boids or actual grouping mechanics-- just enough to make it so enemies collide properly.

Using a bounding circle approximation is accurate enough for my purposes, and so actually detecting a collision is simple. What I need is to only allow the objects to move far enough until there is a collision and then stop.

Thank you for any help or assistance you have.

Ok, if you are only going to do it approximately, you only have to check each frame whether they are touching by measuring the distance between them. Which, we use pythagora's rule of c^2 = a^2 + b^2
So, basically, if "c" is less than or equal to the sum of the radii of the circles, then they are touching or intersecting.

PHP Code:

---

var a:Number = 0 //this will be the difference in x position of the two circles
var b:Number = 0 //this will be the difference in y position of the two circles
//inside your function that is done each frame put something along the lines of; 
a = circle2.x-circle1.x
b = circle2.y-circle2.y
c = Math.sqrt(a*a+b*b)
if (c <= (circle1.width+circle2.width)) {
      /*collision calculation code goes here*/
} 


---

Then, for the collision calculation code, see the latest thread, other than this one in this forum.

If you want the exact time that they collide, I use this; (it's like graphing the change in c, depending on the speeds of the two circles which will be constant, plotted against time, then using the quadratic formula to find the exact amount of time it takes.)

PHP Code:

---

xdif = circ2.x-circ1.x
ydif = circ2.y-circ1.y
    
xSpdDif = circ2xSpd-circ1xSpd
ySpdDif = circ2ySpd-circ1ySpd
    
mag = (circ1.width/2+circ2.width/2)
    
a = (xSpdDif*xSpdDif + ySpdDif*ySpdDif) //note; these are different a, b and c's
b = (2*xSpdDif*xdif + 2*ySpdDif*ydif)
c = (xdif*xdif + ydif*ydif - mag*mag)
discriminant = (b*b - 4*a*c)
    
if (discriminant>0) {
        
    time = ((b*-1) - Math.sqrt(discriminant))/(2*a)
        
} 


---

and then if time is less than 1 and more than 0 they will collide in the next framestep, and so you can tell how far they would go before colliding.

Hope that helped and didn't confuse you. I'll be happy to clarify anything if you want it.

EDIT: You have them in an array, right?

Ah, excellent. Thank you!

I am indeed trying to determine the time t at which they collide (to adjust velocity vectors accordingly).

I haven't tried your math yet. I did put together a separate testing scenario that lets me see the velocity vectors and the collision response in action. Currently I am trying this, which looks like it may be very similar to what you have posted.

I implemented your method along with a couple others I found. I think it works for the most part... Tell me what you think. I'm including the source as well so check it out!

http://noscopecomics.com/~storage/collision

EDIT: I did notice that you are doing an initial check for a collision before you move the objects. This is not a good thing, because it prevents you from detecting collisions along the way (ex: if your velocity vector is long enough to pass over the other object. A collision would still have occurred, but because the objects are not physically colliding at that exact moment, it is never handled).

Cool, I have my own method?
Yeah. It's flawed in the timing, but the math is fine. I was going to go in and fix up the timing somewhat. In fact I will do that now! (As a side note, at the moment I have them move each frame, but when they collide, they "move twice" 'cause it works out how far they would move based on their velocities)
But you are wrong about it able to go over the top. It checks every frame how many frames it would take for them to collide. I need to make that more efficient and that website you linked in your first reply has helped with that.
So... umm... thank you? Also, congrats on being able to understand the whole thing so quickly. You saw how long it took me...

Yeah, I actually took the collision check out and added a couple checks to be sure t is bound to 0,1 and that the objects are facing each other. Now it seems to work flawlessly (I don't know about the exact timing, but the gamastura one is jerky and the tonypa one doesn't work 100% of the time-even on his website).

PHP Code:

---

private function ResOverlap(circ1, circ2):Boolean { 
    var xdif:Number = circ2.orig.x - circ1.orig.x;
    var ydif:Number = circ2.orig.y - circ1.orig.y;
            
    var xSpdDif:Number = circ2.vel.x - circ1.vel.x;
    var ySpdDif:Number = circ2.vel.y - circ1.vel.y;
            
    var mag:Number = (circ1.orig.radius + circ2.orig.radius);
            
    var a:Number = (xSpdDif*xSpdDif + ySpdDif*ySpdDif);
    var b:Number = (2*xSpdDif*xdif + 2*ySpdDif*ydif);
    var c:Number = (xdif*xdif + ydif*ydif - mag*mag);
    var discriminant:Number = (b*b - 4*a*c);
            
    if (b >= 0) return false; // must be facing each other

    if (discriminant > 0) {
        var time:Number = (-b - Math.sqrt(discriminant))/(2*a);
                
        if (time > 1 || time < 0) return false; // must be in the current frame
                
        if (time < circ1.t) circ1.t = time;
        if (time < circ2.t) circ2.t = time;
                
        return true;
    }
    return false;
} 


---

However, everything falls apart when you have three or more objects, which is crucial for me. I tried making it so it each ball would check every other ball and only use the smallest t value, and that helps, but the situation where all three are trying to converge near a point still causes issues. Updated testing scenario to see what I mean.

EDIT3: Yeah, read this part first. What you are going to eventually have to do is put all of the circles into an array and then check each circle against each other. I'm too tired to explain how to explain it. Hell I don't even know properly myself, all I've got is the

PHP Code:

---

for (i>/*something or other and other stuff*/) { /*variable "i" is now every different object in the array, changing each time it runs, it runs once for each different thing in the array per frame, so you add circle1 to the array, and then since that's the only thing in it, yourArray[i] will refer to circle1. Next time it runs, it will refer to whatever it was that was also in the array. Look it up if you don't get it.*/
} 


---

I have been thinking about that too. I have a fix... but it's probably gonna be messy... and not so great. I'm just sharing my thoughts on it here, atm.
Ok, I don't know about you, but I've used the global variable "time" as an exact modifier for the Velocity to determine how far the it is until the actual collision. So, once you have recalculated the Velocities of the using whatever code you have for that. Run ANOTHER check on all of the objects in the array using a different variable. Re-run the "ResOverlap" function between each of the two collided circles and the "rest" of them and using the remaining time modifier to the velocities added to the positions. So what I'm thinking is instead of what you did in the beginning, of:

PHP Code:

---

var xdif:Number = circ2.orig.x - circ1.orig.x; 


---

Have:

PHP Code:

---

var xdif:Number = (circ2.orig.x+(circ2.vel.x*(1-time))) - (circ1.orig.x+(circ1.vel.x*(1-time))) 


---

EDIT2: OH! And you should also use the (1-time) modifier on the xSpdDif variable calculations. And, it's (1-time) because they've already moved the length of time, and 1 = one frame, so the difference is how far they have yet to move. Also. I am using a model where they currently bounce around to build mine, instead your "one-step-projection" thing that is probably better, but I notice that you haven't put in the final positions, so all of this is probably irrelevant... Oh, I see... you just stop them based on where they are GOING to be. So the reason it looks like they are going into each other is because it's only taking into account where they are going to be.

And that SHOULD detect 1 more subsequent collision. If it were to collide twice this would also fall down... hmmm... Thinking on the spot now; we need some function that works out when two circles will collide, what the subsequent velocities would be, and whether there would be another collision, and if there was start again, so it's kind of using the last collision as a reference point. I'm thinking maybe have global variables that can act as temporary velocity holders for any of the circles, so that you can plug in the velocities during several collisions without modifying the actual velocities. I will figure out how to do that this weekend. (w00 4-day weekend! Making next week a 3-day week!) So hopefully I won't be almost unconscious while trying to do it!

EDIT: The good thing about having the time variable is that you can work out exactly which one will collide first, even if it's a minute difference.

EDIT4: Yeah, I'm tired. Sorry if I've confused...

Surprisingly, what you wrote made a good deal of sense to me.

Specifically,

Quote:

---

And that SHOULD detect 1 more subsequent collision. If it were to collide twice this would also fall down... hmmm... Thinking on the spot now; we need some function that works out when two circles will collide, what the subsequent velocities would be, and whether there would be another collision, and if there was start again, so it's kind of using the last collision as a reference point.

---

A recursive function was MADE for this type of thing. Right now the issue stems partly from the fact that it thinks the "final" position is just the initial position + original velocity, but we may be modifying the velocity of different objects between iterations of the function...

EDIT: When you are colliding two objects, you do a for() loop on the array inside of itself, so each one is checked against every other one. There is a way to optimise that, since a lot of the calculations will be the same as other ones, but for now, just fix the collisions, I think.

Thinking about it today, this is what I came up with.
You make a function that does the for() loop on the array once to check if they will collide. But in each case, it records the shortest so far by:

PHP Code:

---

if (time<ShortestTimeSoFar) {
ShortestTimeSoFar = time
circle1InArray = i /*or whatever variable you've used for the array*/
circle2InArray = j
}
/*then, after the function*/
time = ShortestTimeSoFar 


---

The two circle variables will tell us which ones that collide. Then, we use this information to make the right ones collide. Then we run it again, if there is a collision. Then, we move the ones that haven't collided by a for() loop in the Enter_Frame type of function.

There is probably some minor issues with making it do the exact same function again. But I think that should work if it's put in properly.