Deflection calculation with collision detection?

This topic is 3015 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Share on other sites
If your asteroids are just simple circles...then simple circle -> circle collision detection would work. It would be rather quick to test for as well.

Share on other sites
Wouldn't it cause overdetection?
Take this example: the 2 circles overlap a little bit say by 3 units when the first detection occurs.
When the 2 circles start to move away from each other wouldn't there be a few more detections as well as the 2 circles start to not overlap?
I hope this question makes sense.

Share on other sites
yes, but the dot product of the direction of the collision (the direction from one sphere centre to another, and the relative velocity of the spheres, the velocity of one sphere minus the other) will be positive.

In short, the sphere will start moving away from each other. That's where you can ignore them for collision.

It looks like you need to brush up on some basic vector maths and physics.

- Vectors.

- Rigid Body Dynamics.

It is potentially a vast subject, but if you are familliar with basic newtonian physics, It's not that hard.

In fact, the collision detection and response of two massive moving spheres could be summed up in a few lines of code. Understanding what is actually happening is the tricky part (see Chris Hecker's articles).

Quote:
 struct Asteroid{ Vector position; Vector velocity; float mass; float radius;};void move_asteroid(Asteroid& a, float dt){ a.position += a.velocity * dt;}bool collide_asteroids(Asteroid& a, Asteroid& b){ // distance between asteroids (squared). Vector delta(a.position - b.position); float distance_squared = delta.dot_product(delta); // radius of the asteroids. float combined_radius = (a.radius + b.radius); float combined_radius_squared = (combined_radius * combined_radius); // object distance (squared) great than radius (squared). no collision. if(combined_radius_squared < distance_squared) return false; // what is the direction of the collision float distance = sqrt(distance_squared); Vector collision_normal = delta / distance; // how far the objects intersect float intersection_depth = (combined_radius - distance); // compute inverse of masses for both asteroids. float inverse_mass_a = (a.mass <= 0.0000001f)? 0.0f : 1.0f / a.mass; float inverse_mass_b = (b.mass <= 0.0000001f)? 0.0f : 1.0f / b.mass; // separate asteroids so they stop intersecting a.position += collision_normal * (intersection_depth * inverse_mass_a / (inverse_mass_a + inverse_mass_b)); b.position -= collision_normal * (intersection_depth * inverse_mass_b / (inverse_mass_a + inverse_mass_b)); // how hard the objects impact Vector combined_velocity = (a.velocity - b.velocity); float impact_speed = combined_velocity.dot_product(collision_normal); // object are moving away from each other. ignore collision response. if(impact_speed > 0.0f) return true; // how much the asteroids should bounce off each other. const float collision_elasticity = 0.7f; // the instantaneous collision impulse. float collision_impulse_magnitude = -(1.0f + collision_elasticity) * impact_speed / (inverse_mass_a + inverse_mass_b); Vector collision_impulse = collision_impulse_magnitude * collision_normal; // the change in momentum to each asteroids (change in velocity from collision). a.velocity += collision_impulse * inverse_mass_a; b.velocity -= collision_impulse * inverse_mass_b; return true;}

It's basically very simple billiards physics.

EDIT : fixed a bug.

[Edited by - oliii on March 21, 2010 5:06:19 PM]

Share on other sites
Quote:
 Original post by roidgamerWouldn't it cause overdetection?Take this example: the 2 circles overlap a little bit say by 3 units when the first detection occurs. When the 2 circles start to move away from each other wouldn't there be a few more detections as well as the 2 circles start to not overlap?I hope this question makes sense.

Quote:
 Original post by oliiiyes, but the dot product of the direction of the collision (the direction from one sphere centre to another, and the relative velocity of the spheres, the velocity of one sphere minus the other) will be positive.

The other common way to deal with this is to, in addition to modifying your objects' velocities in response to collision, actually project them out of collision as well (usually plus some small "epsilon" tolerance) so that they will not be colliding at the next timestep.

Share on other sites
Unfortunately the forums were offline for a while, so sorry for the late response.

Thank you guys for the responses. Indeed I need to brush up on the vectors (as I have never learned them in any way or the other). :)
I am reading the articles that oliii wrote. :) Good stuff and explains a lot of things. Eg. dot products end so on. :)

One more thing that I might add:
After playing around with simple circle detection I have noticed that circle A and B are getting 2 collisions. Meaning A is colliding with B and B with A. As these 2 are completly the same I started thinking how I could prevent that.

In short:
I keep a simple data structure up to date of the possible collisions. Say I have got 5 asteroids that can collid with each other. Without removing the duplicates that is 5x4 collisions. With removing the duplicates the (n*(n-1))/2 formula applies.

Here is how I keep track of the possible collisions:
http://pastebin.com/P39XFbxq
The code might not work, I just wrote it quickly out of my head.
Will check once I am home. :)

PS: aren't BBcodes work on these forums? O_o

Share on other sites
Quote:
 poss_roid_colls[n].roid1 = &roid_objs;poss_roid_colls[n].roid1 = &roid_objs[j];

I think you meant

Quote:
 poss_roid_colls[n].roid1 = &roid_objs;poss_roid_colls[n].roid2 = &roid_objs[j];

But that's pretty much the way you test all objects against each other only once. I've got a demo with 100 spheres, I'll paste the code later on in a source window.

EDIT : BB tags are... [ code ] [ /code ], and [ source ] [ /source ].
I use [ quote ][ code ].... [ /code ][ /quote ]. It's a nice code block for long code samples.

[Edited by - oliii on March 22, 2010 9:06:29 AM]

Share on other sites
Thanks for the tips.

I have began to update my game engine to utilize vectors. It's going quite good but I have bumped into a problem.

This structure for the ship:
Quote:
 typedef struct { float x; float y; float z;} vector_t;typedef struct { vector_t position; vector_t orientation; vector_t velocity;} ship_t;ship_t ship;

The magnitude (length?) of the orientation vector is always 1 and points to the direction in which the ship is facing (ship will move along this vector). The velocity is the vector with which the ship's position is getting advanced time period.

When I try to rotate the ship by an angle (in degs) I get weird results. It can't be rotated over 180 degrees. (12 o'clock is 0deg) Here are some orientation vectors with degrees:
Quote:
 0 = ( 0, 1,0) 90 = ( 1, 0,0)180 = ( 0,-1,0)270 = ( -1,0,0)

So if I wanted to rotate my ship by +5 degrees (from 0 - facing up) I'd have to update the x, y orientation vectors (2D app, so no z value).
Quote:
 current_angle = vector_angle(&vector_up, &ship.orientation);angle = current_angle + 5;ship.orientation.x = sin(angle * PI / 180);ship.orientation.y = cos(angle * PI / 180);

vector_angle function returns the angle (in degs) between 2 vectors. current_angle is the angle between direction up [ vector(0,1,0) ] and the ship's orientation.

Question:
can you see the problem why this solution will never go over 180 degs? Could it be because the period of sin and cosine is 180 (PI)?

Share on other sites
vector_angle could be doing a simple acos(), which has a range between (0, 180).

the angle of a direction vector should be

angle = atan2(vector.y, vector.x) * 180.0f / PI;

Oh, and I'd usae cos(angle) for x, and sin(angle) for y, else in your case, the angle will be atan2(vector.x, vector.y);

You could also store your ship orientation as just an angle value, update that angle, and the direction your ship is pointing would be Vector(cos(orientation), sin(orientation));

So basically, the direction vector is only a by-product of your ship angular orientation, and not the other way round. Could make it easier that way.

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• Forum Statistics

• Total Topics
631429
• Total Posts
3000033
×