Deflection calculation with collision detection?
Author
Hello everyone!
My first post yay!
So here I am, the newest wannabe :) I wrote a simple asteroid game like thing in C+OpenGL+Glut.
Thing is, opengl part works ok, but when it comes to complex things, such as collision detection and calculating how the asteroids will bounce off of each other, I struggle;
Here is a list of information I know of the asteroids in the game (they are simple circles):
- x, y coords (only 2D app)
- orientation (the angle in which they move)
- speed (by how many pixels [that is the unit in this app] the roid will advance/frame)
- radius (the radius of the asteroid)
The coordinate system of world space is set up in a way that the bottom left corner of the window is O(0,0) and the top right corner of the window is R(win.width, win.height) where win.width and win.height are the width and height of the active window. Basic 2D ortho projection is used.
The question:
- How can I determine whether collision between any 2 given asteroids is possible
- What additional data do I need to keep track of for each asteroids
- If collision is possible, how do I check whether collision has occurred or not
Or alternatively links to docs/example that might as well cover the math behind it could be very useful. Thanks in advance for the help.. Yell to me if you need any more information about this specific setup.
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.
Author
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.
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.
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).
It's basically very simple billiards physics.
EDIT : fixed a bug.
[Edited by - oliii on March 21, 2010 5:06:19 PM]
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]
Quote:Original post by roidgamer
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.
Quote:Original post by oliii
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.
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.
Author
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
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
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...
, and [ source ] [ /source ]. I use
.... [Edited by - oliii on March 22, 2010 9:06:29 AM]
Author
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:
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:
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).
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)?
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)?
vector_angle could be doing a simple acos(), which has a range between (0, 180).
the angle of a direction vector should be
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
