### Author Topic: Asteroid collisions  (Read 3173 times)

0 Members and 1 Guest are viewing this topic.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Asteroid collisions
« on: December 15, 2010, 01:47:12 PM »
Hello,

I'm working on a new level.

It has gravity and Infected AI.
My problem is that I want the asteroids to bounce off each other, instead of passing straight through one another.

This problem is twofold:

1) I need a collision engine to detect when asteroids have collided, and which two asteroids were involved in the collision.
2) Then I need to decide how the asteroids will bounce.  To do that, I need to modify the MomentumX and MomentumY values for those asteroids in a way that is appropriate to the force, relative size, and direction that each roid is travelling in, as well as the angle at which they strike one another.

I am pleased to say that I have part 1 totally sorted.
I use pythagoras to work out the distance between the centres of both asteroids.  Then, if that distance is less than Asteroid 1 Radius + Asteroid 2 Radius, they have collided.
This code works fine.

For part 2, I am struggling.
I am having real difficulty figuring out the formal rules of collision here, and how I express what happens when say, 2 billiard balls collide, in LUA.
I've no clue what sort of equations I should be modelling, or any of the maths that is involved.

Here's a diagram showing the limitations of my current understanding.

For my examples, I assume all objects are of the same size, density, and elasticity/bounciness - though I will also need to gain an understanding of the role these parameters play.

Help with this would be very much appreciated.
« Last Edit: December 15, 2010, 02:08:04 PM by annikk.exe »

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Asteroid collisions
« Reply #1 on: December 15, 2010, 03:04:52 PM »
I found some useful equations here.  Hopefully they will work good...

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Asteroid collisions
« Reply #2 on: December 15, 2010, 04:04:18 PM »
My notes:

Code: [Select]
`1. Get a normal vector for the 2 colliding roids. nvectorX = CoordX[1] - CoordX[2] nvectorY = CoordY[1] - CoordY[2]2. Next we need a unit vector (or "normalised" vector). That's a vector with a length of 1. To find this, we divide each vector component by the length of the vector. So: unitvectorX = normal vector X / length of normal vector unitvectorY = normal vector Y / length of normal vector uvectorX = nvectorX / math.sqrt((CoordX[1] * CoordX[1]) + (CoordY[2] * CoordY[2])) uvectorY = nvectorY / math.sqrt((CoordX[1] * CoordX[1]) + (CoordY[2] * CoordY[2]))3.  Now we have the Unit Vector, we need the Unit Tangent Vector. utanvectorX = nvectorY * -1 utanvectorY = nvectorX4.  Now we require the speed that each asteroid is travelling. To do this we use Pythagoras triangular shenanigans on the MomentumX and MomentumY values. speed of first asteroid = math.sqrt((MomentumX[1] * MomentumX[1]) + (MomentumY[1] * MomentumY[1])) speed of secnd asteroid = math.sqrt((MomentumX[2] * MomentumX[2]) + (MomentumY[2] * MomentumY[2]))5. Now we need a dot product. To find the dot product of these two vectors: (10,-5) (4,7) We would use this calculation: (10 * 4) + (-5 * 7) = 40 + (-35) = 5 This result is a SCALAR because it expresses an amount only, and not a direction! The calculations we need are: vfirstroidnormal = (unitvectorX * speed of first asteroid) + (unitvectorY * speed of first asteroid) vfirstroidtan    = (utanvectorX * speed of first asteroid) + (utanvectorY * speed of first asteroid) vsecndroidnormal = (unitvectorX * speed of first asteroid) + (unitvectorY * speed of first asteroid) vsecndroidtan    = (utanvectorX * speed of first asteroid) + (utanvectorY * speed of first asteroid)6.  Now we can find the new velocities (as scalars - only speed, no direction specified yet) bouncedvelocity1 = vfirstroidnormal * (roid 1 mass - roid 2 mass) + (2 * roid 2 mass * vsecndroidnormal) / (roid 1 mass + roid 2 mass) bouncedvelocity2 = vsecndroidnormal * (roid 2 mass - roid 1 mass) + (2 * roid 1 mass * vfirstroidnormal) / (roid 1 mass + roid 2 mass) (mass is found by multiplying area by density.  area = pi * radius * radius)7.  `
unfinished..

#### Alex

• Ent
• Thank You
• -Given: 3
• Posts: 1,035
##### Re: Asteroid collisions
« Reply #3 on: December 15, 2010, 05:54:05 PM »

#### Pilchard123

• Tester
• Old Oak
• Thank You
• -Given: 0
• Posts: 899
• Eufloria: Yes
##### Re: Asteroid collisions
« Reply #4 on: December 15, 2010, 07:24:52 PM »

Ok, screeching done. Is this your big bang map? Momentum really gets fun when things join together.

IIRC, it's possible to just deal with the X and Y values for momentum separately, which may make your map easier.

'Kay,

Case 1 - dealt with.
Case 2 - momentum is always conserved, so the total momentum after the collision is 25 + (-75) = -50, so 50 kgm/s to the left.
Case 3 - X : 25 + (-75) = -50, so 50 kgm/s to the left.
Y : (-25) + 75 = 50, so 50 kgm/s to the to.
Case 4 - X : 25 + (-75) = -50, so 50 kgm/s to the left.
Y : 0 + 0 = 0, so as the two bodies have equal masses they must travel vertically at equal and opposite velocities.
« Last Edit: December 15, 2010, 08:45:19 PM by Pilchard123 »

#### Sniped50

• Sapling
• Thank You
• -Given: 0
• Posts: 97
##### Re: Asteroid collisions
« Reply #5 on: December 16, 2010, 09:24:07 PM »
@Pilchard123
Heh heh heh...   Eufloria doesn't use 3D asteroids you know. You're thinking of SPHERES. Eufloria only uses 2D CIRCLES, so annikk got it right the first time. Sorry to rain on your parade, though.

@Annikk.exe
Quick question, are these collisions going to be elastic (i.e. no kinetic energy is lost)? It would not only help to keep the map moving, but it would also stop the asteroids from clumping together in the centre because they lost most of their momentum AND because of gravity.
Just thought I'd mention it. It would be embarassing if you released a beta version of the map and THAT came up!
"Sometimes, the simplest solutions work the best."
- Mythbusters

"But the complex solutions look prettier."
- Me

• Global Moderator
• Seedling
• Thank You
• -Given: 0
• Posts: 38
##### Re: Asteroid collisions
« Reply #6 on: December 17, 2010, 05:24:05 PM »
It's 2D so the mass is equal to the area * density

Case 4.  Think of two pool balls striking each other in that way, glancing off each other.  Does your conclusion seem logical?  It does not, to me...  if they strike at an angle, they go bouncing off at an angle.

Also yes these are elastic collisions.

#### Pilchard123

• Tester
• Old Oak
• Thank You
• -Given: 0
• Posts: 899
• Eufloria: Yes
##### Re: Asteroid collisions
« Reply #7 on: December 17, 2010, 05:47:15 PM »
It is logical: the vertical components of the velocities will be equal, so the vertical speeds will be the same. Horizontally, the speeds could be totally different.

More stuff - it is possible to work it all out. Momentum is mass*velocity, kinetic (movement) energy is (mass*velocity*velocity)/2. Both must be conserved.

http://en.wikipedia.org/wiki/Elastic_collision#Two-_and_three-dimensional
« Last Edit: December 17, 2010, 05:57:18 PM by Pilchard123 »

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Asteroid collisions
« Reply #8 on: December 18, 2010, 03:16:38 AM »
Maybe it's not so clear from the diagram.  Case 4 differs from the others in that the balls don't strike head on.  Instead, they glance off each other by an unspecified amount.

Have you ever played pool?  Or snooker or something?  If a ball strikes another, but it doesn't hit it dead on, it causes the struck ball to spin off at an angle - and not the same angle as the striking ball was travelling in.  I don't know what the angle is, or what maths governs it..  but it's definitely an angle.

In the diagram in Case 4, after the collision I would expect the ball on the left to end up travelling north-west.  The ball on the right would be travelling south-west, I think.
The fact that they strike each other at an angle - and that they are both round - causes them to have vertical as well as horizontal components to their momentum following the collision.  I am having trouble trying to figure out the maths that governs these angles.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Asteroid collisions
« Reply #9 on: December 18, 2010, 03:29:38 AM »
This diagram from the wikipedia article you linked shows exactly what I mean :>

It also kind of shows me how to work it out, I think...  The article gives the equations for if the second body is at rest, but I think I can see how I would combine it with another momentum vector.. :>

I just got back from an epic journey, though.  Sleep time now.  :>

#### Pilchard123

• Tester
• Old Oak
• Thank You
• -Given: 0
• Posts: 899
• Eufloria: Yes
##### Re: Asteroid collisions
« Reply #10 on: December 19, 2010, 01:00:24 PM »
Ooh - possible problem.

Your MomentumX and MomentumY - are they the velocities of the roids, or are they really the momentum? Could have a bearing on how you code, etc.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Asteroid collisions
« Reply #11 on: December 19, 2010, 02:59:20 PM »
There are three parameters that pertain to movement: Coord, Momentum and Acceleration:

CoordX[1]
CoordY[1]
MomentumX[1]
MomentumY[1]
AccelerationX[1]
AccelerationY[1]

Coords describe the X and Y position of an asteroid's centre.
Momentum describes how much that asteroid will move (X and Y) in the next cycle of the gravity engine.  Each cycle, the momentum is added (or subtracted) from the Coord, so as to give the new position of the asteroid.
Acceleration describes how much ADDITIONAL momentum will be added or subtracted from the corresponding Momentum value, based on gravity (and any bouncing) during the next cycle of the gravity engine.  Acceleration is zeroed each cycle and recalculated for the new positions and corresponding gravitational influence of all asteroids.

The velocity of an asteroid would be a scalar (magnitude only) obtained by finding the Hypotenuse of the triangle with sides MomentumX and MomentumY for the Adjacent and Opposite, for any given asteroid.  Converting between them shouldn't be a problem..

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
• Posts: 1,794
##### Re: Asteroid collisions
« Reply #12 on: December 19, 2010, 03:40:40 PM »
Not working :\

Code: [Select]
` -- first up, what's the total mass of these colliding objects? imass = math.pi * roidradius[i] * roidradius[i] jmass = math.pi * roidradius[j] * roidradius[j] totalmass = imass + jmass -- what proportion from 0 to 1 of the mass belongs to i? jprop = imass / jmass -- and what proportion of the mass belongs to j? iprop = jmass / imass -- change the momentums of both roids for the bounce. --Calculate the collision angle (A) by using atan2 applied to the difference of the coordinates of each object (x, y): A = math.atan2((CoordY[i] - CoordY[j]), (CoordX[i] - CoordX[j])) -- calculate the velocity of both roids -- i ivelocity = math.sqrt((MomentumX[i] * MomentumX[i]) + (MomentumY[i] * MomentumY[i])) -- j jvelocity = math.sqrt((MomentumX[j] * MomentumX[j]) + (MomentumY[j] * MomentumY[j])) -- Use the collision angle (A), the ball's initial velocity (u) and ball's initial direction (D) to derive it's x/y velocity in the new rotated coordinate system: Di = math.tan(CoordX[i] / CoordY[i]) Dj = math.tan(CoordX[j] / CoordY[j]) v1x = ivelocity * math.cos(Di - A) v1y = ivelocity * math.sin(Di - A) v2x = jvelocity * math.cos(Dj - A) v2y = jvelocity * math.sin(Dj - A) -- Now that we have the collision aligned along the x-axis, all we have to do is apply the 1D collision equation to vx. We will call the final x-velocities for each ball f1x and f2x: f1x = (v1x * (imass - jmass) + (2 * jmass * v2x)) / totalmass f2x = (v2x * (imass - jmass) + (2 * jmass * v1x)) / totalmass -- Now that we we have the final x and y velocities in the rotated coordinate system, we must convert everything back to a normal Cartesian coordinate system, as follows: v1 = math.sqrt((f1x * f1x) + (v1y * v1y)) v2 = math.sqrt((f2x * f2x) + (v2y * v2y)) D1 = math.atan2(v1y,f1x) + A D2 = math.atan2(v2y,f2x) + A -- Now we have the final angle and momentum as a hypotenuse... we can calculate the opposite and adjacent to obtain new momentumX and momentumY MomentumY[i] = v1 * math.cos(D1) MomentumX[i] = v1 * math.sin(D1) MomentumX[j] = v2 * math.cos(D2) MomentumY[j] = v2 * math.sin(D2)`

« Last Edit: December 19, 2010, 03:48:01 PM by annikk.exe »

#### Widget

• Sapling
• Thank You
• -Given: 0
• Posts: 98
##### Re: Asteroid collisions
« Reply #13 on: December 19, 2010, 03:51:34 PM »
Ack, I wish I could help but I've not used any maths worthy of the name in the last decade. It's a really exciting idea but well over my head.

#### annikk.exe

• Achiever
• Ent
• Thank You
• -Given: 0
` -- check if there has been a collision -- if collision = true then comboradius = roidradius[i] + roidradius[j] if collision[i] ~= true then collision[i] = false end if collision[j] ~= true then collision[j] = false end if math.sqrt(((CoordX[j] - CoordX[i])^2 + (CoordY[j] - CoordY[i])^2)) < comboradius then -- a collision has occurred! -- modify momentum for bounce values collision[j] = true collision[i] = true -- first up, what's the total mass of these colliding objects? imass = math.pi * roidradius[i] * roidradius[i] jmass = math.pi * roidradius[j] * roidradius[j] totalmass = imass + jmass -- change the momentums of both roids for the bounce. dx = MomentumX[i] - MomentumX[j] dy = MomentumY[i] - MomentumY[j] collision_angle = math.atan2(dy, dx) magnitude_1 = math.sqrt((MomentumX[i] * MomentumX[i]) + (MomentumY[i] * MomentumY[i])) magnitude_2 = math.sqrt((MomentumX[j] * MomentumX[j]) + (MomentumY[j] * MomentumY[j])) direction_1 = math.atan2(MomentumY[i], MomentumX[i]) direction_2 = math.atan2(MomentumY[j], MomentumX[j]) new_xspeed_1 = magnitude_1 * math.cos(direction_1 - collision_angle) new_yspeed_1 = magnitude_1 * math.sin(direction_1 - collision_angle) new_xspeed_2 = magnitude_2 * math.cos(direction_2 - collision_angle) new_yspeed_2 = magnitude_2 * math.sin(direction_2 - collision_angle) final_xspeed_1 = ((imass - jmass) * new_xspeed_1 + (jmass + jmass) * new_xspeed_2) / totalmass final_xspeed_2 = ((imass + imass) * new_xspeed_1 + (jmass - imass) * new_xspeed_2) / totalmass final_yspeed_1 = new_yspeed_1 final_yspeed_2 = new_yspeed_2 MomentumX[i] = math.cos(collision_angle) * final_xspeed_1 + math.cos(collision_angle + math.pi / 2) * final_yspeed_1 MomentumY[i] = math.sin(collision_angle) * final_xspeed_1 + math.sin(collision_angle + math.pi / 2) * final_yspeed_1 MomentumX[j] = math.cos(collision_angle) * final_xspeed_2 + math.cos(collision_angle + math.pi / 2) * final_yspeed_2 MomentumY[j] = math.sin(collision_angle) * final_xspeed_2 + math.sin(collision_angle + math.pi / 2) * final_yspeed_2 else -- else if there wasn't a collision then -- ..add the appropriate amount of acceleration as normal AccelerationX[i] = AccelerationX[i] + (NormalisedVectorX * Fgx / ((roidradius[i] * roidradius[i]) * math.pi) * density[i]) AccelerationY[i] = AccelerationY[i] + (NormalisedVectorY * Fgy / ((roidradius[i] * roidradius[i]) * math.pi) * density[i]) xdiff = CoordX[i] - CoordX[j] ydiff = CoordY[i] - CoordY[j] NormalisedVectorX = xdiff / vectorlength NormalisedVectorY = ydiff / vectorlength AccelerationX[j] = AccelerationX[j] + (NormalisedVectorX * Fgx / ((roidradius[j] * roidradius[j]) * math.pi) * density[j]) AccelerationY[j] = AccelerationY[j] + (NormalisedVectorY * Fgy / ((roidradius[j] * roidradius[j]) * math.pi) * density[j]) end`