Sign in to follow this  
roidgamer

Deflection calculation with collision detection?

Recommended Posts

roidgamer    100
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.

Share this post


Link to post
Share on other sites
roidgamer    100
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 this post


Link to post
Share on other sites
oliii    2196
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 this post


Link to post
Share on other sites
Emergent    982
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.

Share this post


Link to post
Share on other sites
roidgamer    100
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 this post


Link to post
Share on other sites
oliii    2196
Quote:

poss_roid_colls[n].roid1 = &roid_objs[i];
poss_roid_colls[n].roid1 = &roid_objs[j];



I think you meant

Quote:

poss_roid_colls[n].roid1 = &roid_objs[i];
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 this post


Link to post
Share on other sites
roidgamer    100
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 this post


Link to post
Share on other sites
oliii    2196
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.

Share this post


Link to post
Share on other sites
Emergent    982
Alternative: Instead of keeping an angle variable around, instead just do,

ship.orientation = rotationMatrix(omega*dt)*ship.orientation;

where 'omega' is the angular velocity (its sign determines the direction of rotation) and 'dt' is the length of a timestep.

Actually, rounding errors will mean that ship.orientation might slowly become not-a-unit-vector, so instead you'd probably actually want,

ship.orientation = normalize(rotationMatrix(omega*dt)*ship.orientation);

Share this post


Link to post
Share on other sites
oliii    2196
Personally I'd just keep an angular value, it also simplifies things a little bit if you want to go rigid body dynamics with angular momentums applies (angular velocity change after collisions, or by applying torques and forces to your body).

in 3D rigid body dynamics, that angular value is replaced by an orientation quaternion, and an angular velocity vector.

Share this post


Link to post
Share on other sites
oliii    2196

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <math.h>
#include <memory.h>
#include <windows.h>
#include <gl/glut.h>
#include <vector>

#pragma comment(lib, "opengl32.lib")
#pragma comment(lib, "glu32.lib")
#pragma comment(lib, "glut32.lib")

void dbgBreak()
{
__asm int 3;
}

void dbg(const char* format, ...)
{
va_list args;
va_start(args, format);
char buff[512];
vsprintf_s(buff, sizeof(buff), format, args);
va_end(args);

char str[1024];
sprintf_s(str, sizeof(str), "%s\n", buff);
printf(str);
OutputDebugString(str);
}

float randf(float range)
{
return (rand() / (float)(RAND_MAX)) * range;
}

float randf(float min, float max)
{
return min + (rand() / (float)(RAND_MAX)) * (max - min);
}

float twopi()
{
static float g_twopi = atan(1.0f) * 8.0f;
return g_twopi;
}


//===========================================================================
// VECTORS
//===========================================================================
class Vector
{
public:
float x,y;
public:
inline Vector(void)
{}

inline Vector(float ix,float iy)
: x(ix)
, y(iy)
{}

inline Vector &operator /=(const float scalar) { x /= scalar; y /= scalar; return *this; }

inline Vector &operator *=(const float scalar) { x *= scalar; y *= scalar; return *this; }

inline Vector &operator +=(const Vector &other) { x += other.x; y += other.y; return *this; }

inline Vector &operator -=(const Vector &other) { x -= other.x; y -= other.y; return *this; }

inline float operator ^ (const Vector &other) const { return (x * other.y) - (y * other.x); } // cross product

inline float operator * (const Vector &other) const { return (x * other.x) + (y * other.y); } // dot product

inline Vector operator * (float scalar) const { return Vector(x * scalar, y * scalar); }

inline Vector operator / (float scalar) const { return Vector(x / scalar, y / scalar); }

inline Vector operator + (const Vector &other) const { return Vector(x + other.x, y + other.y); }

inline Vector operator - (const Vector &other) const { return Vector(x - other.x, y - other.y); }

inline Vector operator -(void) const { return Vector(-x, -y); }

friend Vector operator * (float k, const Vector& other) { return Vector(other.x * k, other.y * k); }

inline float length(void) const { return (float) sqrt(x*x + y*y); }

inline float normalise(void) { float l = length(); if(l > 1.0E-5f) (*this) /= l; return l; }

inline Vector direction(void) const { Vector temp(*this); temp.normalise(); return temp; }

inline float dot_product(const Vector &other) const { return (*this) * other; } // cross product

inline float cross_product(const Vector &other) const { return (*this) ^ other; } // dot product

inline Vector& limit(float length_limit) { float l = length(); if(l > length_limit) (*this) *= (length_limit / l); return (*this); }

Vector& rotate(float angle)
{
float tx = x;
x = x * cos(angle) - y * sin(angle);
y = tx * sin(angle) + y * cos(angle);
return *this;
}
Vector& transform(const Vector& trans, float rot)
{
Vector D = *this;
D.rotate(rot);
*this = trans + D;
return *this;
}
void randomise(const Vector& min, const Vector& max)
{
x = randf(max.x - min.x) + min.x;
y = randf(max.y - min.y) + min.y;
}
};

#define ARGB_A(u) (((u)>>24) & 0x000000FF)
#define ARGB_R(u) (((u)>>16) & 0x000000FF)
#define ARGB_G(u) (((u)>> 8) & 0x000000FF)
#define ARGB_B(u) (((u)>> 0) & 0x000000FF)
void renderColour(u_int col)
{
glColor4ub(ARGB_R(col), ARGB_G(col), ARGB_B(col), ARGB_A(col));
}

void renderCross(float x, float y, float r, int colour)
{
renderColour(colour);
glBegin(GL_LINES);
glVertex2f(x - r, y - r);
glVertex2f(x + r, y + r);
glVertex2f(x - r, y + r);
glVertex2f(x + r, y - r);
glEnd();
glEndList();
}

void renderCircle(float x, float y, float r, int colour)
{
static GLint displaylist=-1;
if(displaylist < 0)
{
displaylist = glGenLists(1);
glNewList(displaylist, GL_COMPILE);
glBegin(GL_LINE_LOOP);
float da = twopi() / 32;
float a = 0.0f;
for(int i = 0; i <= 32; i ++, a += da)
glVertex2f(cos(a), sin(a));
glEnd();
glEndList();
}

glPushMatrix();
glTranslatef(x, y, 0.0f);
glScalef(r, r, r);
renderColour(colour);
glCallList(displaylist);
glPopMatrix();
}

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;
}

int width = 1024;
int height = 764;
Asteroid asteroids[100];
int asteroid_count=100;
Vector mousepos(0, 0);
Vector mousevel(0, 0);
bool attract=false;
bool repel=false;
bool scrolling = true; // screen is relative to the mouse cursor.

void update_mouse()
{
if(scrolling)
{
POINT point;
GetCursorPos(&point);
mousevel.x = (point.x - width/2);
mousevel.y = (point.y - height/2);
SetCursorPos(width/2, height/2);

mousepos.x += mousevel.x;
mousepos.y += mousevel.y;
}
}

void init()
{
for(int i = 0; i < asteroid_count; i ++)
{
asteroids[i].position.randomise(Vector(0, 0), Vector(width, height));
asteroids[i].velocity.randomise(Vector(-width, -height), Vector(width, height));
asteroids[i].velocity.limit(50.0f);
asteroids[i].radius = randf(10.0f, 30.0f);
asteroids[i].mass = (asteroids[i].radius * asteroids[i].radius);
}
}

void update(float dt)
{
int passes = 4;

// update velocity.
for(int i = 0; i < asteroid_count; i ++)
{
// move towards mouse position.
Vector delta = (mousepos - asteroids[i].position);
delta *= (attract)? 1.0f : (repel)? -1.0f : 0.0f;
delta.limit(200.0f);
asteroids[i].velocity += delta * 0.1f;

asteroids[i].velocity *= 0.995f;
asteroids[i].velocity.limit(200.0f);
}

for(int i = 0; i < asteroid_count; i ++)
{
move_asteroid(asteroids[i], dt);
}

for(int i = 0; i < asteroid_count; i ++)
{
for(int j = i+1; j < asteroid_count; j ++)
{
collide_asteroids(asteroids[i], asteroids[j]);
}
}

Vector origin = (scrolling)? mousepos : Vector(0, 0);

for(int i = 0; i < asteroid_count; i ++)
{
float maxx = origin.x + width / 2 + asteroids[i].radius;
float maxy = origin.y + height / 2 + asteroids[i].radius;
float minx = origin.x - width / 2 - asteroids[i].radius;
float miny = origin.y - height / 2 - asteroids[i].radius;

if(asteroids[i].position.x < minx) asteroids[i].position.x += (maxx - minx);
if(asteroids[i].position.y < miny) asteroids[i].position.y += (maxy - miny);
if(asteroids[i].position.x > maxx) asteroids[i].position.x -= (maxx - minx);
if(asteroids[i].position.y > maxy) asteroids[i].position.y -= (maxy - miny);
}
}

void render()
{
Vector origin = (scrolling)? mousepos : Vector(0, 0);

glMatrixMode(GL_MODELVIEW);
glPushMatrix();
glTranslatef(-origin.x, -origin.y, 0.0f);

renderCross(mousepos.x, mousepos.y, 16.0f, 0xffffffff);

for(int i = 0; i < asteroid_count; i ++)
{
renderCircle(asteroids[i].position.x, asteroids[i].position.y, asteroids[i].radius, 0xffffffff);
}

glPopMatrix();
}


const char* windowname = "2D sphere collision";
void glutDisplay()
{
//--------------------------------------------------------------------------
// render stuff
//--------------------------------------------------------------------------
glClearColor(0.2f, 0.2f, 0.2f, 0.0f);
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(-width/2.0f, width/2.0f, height/2.0f, -height/2.0f);

glMatrixMode(GL_MODELVIEW);
glLoadIdentity();

HWND focus = GetFocus();
HWND myWindow = FindWindow("GLUT", windowname);
if(focus == myWindow)
{
update_mouse();
update(1.0f / 30.0f);
}
render();
glutSwapBuffers();
}

void glutTimer(int t)
{
glutDisplay();
glutTimerFunc(t, glutTimer, (int) (1000.0f / 30.0f));
}

void glutKeyboard(unsigned char key, int x, int y)
{
if (key == 27)
exit(0);

if (key == ' ')
init();
}

void glutMotion(int x, int y)
{
if(!scrolling)
{
Vector newmousepos(x - width / 2, y - height / 2);
mousevel = newmousepos - mousepos;
mousepos = newmousepos;
}
}

void glutPassiveMotion(int x, int y)
{
if(!scrolling)
{
Vector newmousepos(x - width / 2, y - height / 2);
mousevel = newmousepos - mousepos;
mousepos = newmousepos;
}
}

void glutMouse(int buttons, int state, int x, int y)
{
if(!scrolling)
{
Vector newmousepos(x - width / 2, y - height / 2);
mousevel = newmousepos - mousepos;
mousepos = newmousepos;
}

if (buttons == GLUT_LEFT_BUTTON)
{
attract = (state == GLUT_DOWN);
}

if (buttons == GLUT_RIGHT_BUTTON)
{
repel = (state == GLUT_DOWN);
}
}

void glutReshape(int w, int h)
{
width = w;
height = h;
glViewport(0, 0, w, h);
}

void main(int argc, char** argv)
{
//--------------------------------------------------------------------------
// OpenGL / GLUT init
//--------------------------------------------------------------------------
glutInit( &argc, argv );
glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGBA | GLUT_DEPTH);
glutInitWindowSize (width, height);
glutInitWindowPosition (0, 0);
glutCreateWindow (windowname);

glutKeyboardFunc (glutKeyboard);
glutMouseFunc (glutMouse);
glutMotionFunc (glutMotion);
glutPassiveMotionFunc (glutPassiveMotion);
glutDisplayFunc (glutDisplay);
glutReshapeFunc (glutReshape);
glutTimerFunc (0, glutTimer, (int) (1000.0f / 60.0f));
glutSetCursor (0);

init();
glutMainLoop();
}

Share this post


Link to post
Share on other sites
roidgamer    100
Awesome!

Whenever I get back here I see a new verzóy useful post. :) Getting to like this community.. hehe

My asteroid game is progressing as well quite nicely. I got the 'ship' (triangle) moving around, asteroids and can shoot. :) yay
I'll post a screenshot of it later on today.
Once again thanks for the tips for the rotation problem. It turned out that I was taking the ship's xy position instead of the orientation to calculate the new angle. Silly me :) It works now...

For now I don't dare the run valgrind on this code hehe...

[Edited by - roidgamer on March 23, 2010 6:08:23 AM]

Share this post


Link to post
Share on other sites
roidgamer    100
Hello again!

As I promised here are some screenshots of my first 'game' :) Totally pointless but you can waste a lot of time with it. :)

http://i41.tinypic.com/qsnm7l.png

http://i44.tinypic.com/11j0scy.png

I still don't know how to post links. I can't seem to find the bbcode for that.
Anyway a list of features:

- you can shoot (projectile)
- can can target asteroids and shoot missiles
- can you fly around (your inertia will move you in that direction)
- you have a deflector shield that make roids bounce off of you
- roids bounce off of shield based on ship's mass and their mass
- shield recharges in 10 seconds and drains in 7.5
- colliding with roid makes shield 5% less immediately
- you have 3 lives
- you get points for asteroids. The larger they are the more you get

Backstory:
A lone pilot took it upon himself to collect resources for the last colony of human kind in the dark and endless space. Resources became so scarce through the centuries of massive industrial production that wars broke out between colonies. Only 1 survived, barely. The economy and the human population suffers the lack of resources, plages, illnesses.
It is your duty to secure the survival of this race!

Ok, now seriously:
I frigging enjoy making silly games that are good for nothing but maan, it's fun to make them. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this