# 2D Collisions

## Recommended Posts

EdwardDingle    129
after about a week of coding 2D collisions in my spare time, and seeing the futility of basing it off of rectangles, im trying to do it the "proper way" All math in my 2D space shooter is based on the following vector class I wrote:
public class Vector2D {
public double x;
public double y;
public double velocity;
public double angle;

public Vector2D(double velocity, double angle){
this.velocity=velocity;
this.angle=angle;
x=0;
y=0;
}

double cos1 =  Math.cos(angle);
double sin1 = Math.sin(angle);
double cos2 =  Math.cos(newVect.angle);
double sin2 = Math.sin(newVect.angle);
double x1 = cos1*velocity;
double y1 = sin1*velocity;
double x2 = cos2*newVect.velocity;
double y2 = sin2*newVect.velocity;
x=x1+x2;
y=y1+y2;

velocity = Math.sqrt(Math.pow(x,2)+Math.pow(y,2));
angle = Math.atan2(y,x);

return new Vector2D(velocity, angle);
}

public String toString(){
String t="X: "+x+"\nY: "+y+"\nvelocity: "+velocity+"\nangle: "+angle;
return t;
}

public Vector2D copyVector(){
return new Vector2D(velocity,angle);
}
}


I now use a circle to represent the players ship, but I have NO idea how to detect collisions of walls or any objects in general. I realize you can see if something collides by taking the closest point and comparing it with the radius, but the code i wrote was so inefficient it actually lagged my computer. But as far as getting the resulting new angle after the collision even takes place is out of my scope of comprehension. Looking for some guidance after researching exhaustively for hours, thanks!

##### Share on other sites
Atrix256    539
When you have a lot of objects to test against for collisions, obviously your game is going to slow down a ton because of all of those collisions.

The way you get around this is to store the objects in some kind of spatial structure.

One of the best, and simplest is a grid, which can be either 2d or 3d.

What you do is for each grid cell, store a list of what objects lie within it.

If an object lies in more than one grid cell, you can store it within both grid cells.

Then, when you want to test an object to see what other objects it collides with, all you do is find out what grid cell(s) the object lies within, and only test it against the other objects in those cell(s).

If done right (small enough grid cells but not too small), this cuts down the number of objects you have to test against significantly.

If you want more exotic structures to store objects in, there are some really interesting / cool ones, but the grid is a really good one.

Quadtrees and Octtrees are 2 other good ones sometimes

##### Share on other sites
oliii    2196
eek. That's a very OTT vector class. By definition, a vector class should be restricted to just (x, y). I'm not really sure what angle and velocity represent.

You have lots of very costly functions in there, such as cos() sin, sqrt(), even pow(). All these gets called every time you have a simple vector add. You rarely need to know the angle of a vector, or you should minimise the calls to those expensive trig functions.

Vector usually represent Cartesian coordinates, and nothing more. Angle-Length (you actually call it velocity which is a misnomer) are more related to polar coordinates. But a 2D vector class would be pretty much simplified to :

Quote:
 public class Vector2D { public double x; public double y; public Vector2D(double ix, double iy){ x=ix; y=iy; } public void addVector(Vector2D other){ x = x + other.x; y = y + other.y; } public void subVector(Vector2D other){ x = x - other.x; y = y - other.y; } public void mulVector(double scalar){ x *= scalar; y *= scalar; } public void divVector(double scalar){ x = x / scalar; y = y / scalar; } public double dotProduct(Vector2D other){ double dot = x*other.x + y * other.y; return dot; } public double crossProduct(Vector2D other){ double cross = x*other.y - y * other.x; return cross; } public double lengthSquared(){ double length2 = x*x + y*y; return length2; } public void length(){ double length2 = x*x + y*y; double length = sqrt(length2); return length; } public Vector2D direction(){ Vector2D copy = new Vector2D(x, y); copy.normalise(); return copy; } public double angle(){ double angle = atan2(y, x); return angle; } public double normalise(){ double l = length(); if(l > 1.0E-6f) { x /= l; y /= l; } return l; } public String toString(){ String t="X: "+x+"\nY: "+y; return t; } public Vector2D copyVector(){ return new Vector2D(x,y); }}

And pretty much all your collision detection needs can be based on that.

##### Share on other sites
EdwardDingle    129
I guess i'll try to convert my code to using proper vectors then. How do I get the resulting x/y for a vector from just an angle and magnitude? Or rather, how should I alter my ship class, because currently it just adds x radians to it's "direction" depending on left or right which has worked great.

##### Share on other sites
Atrix256    539
oliii was saying don't store angle and magnitude, just store the X and Y components of the vector.

If you need to get the angle that a vector is, you can use atan2(Y,X) but hopefully you shouldn't have to do that too often (:

Edit: oh and to answer your question, how do you get a vector from an angle and a speed, you do it like this:

VectorX = cos(Angle) * Speed;
VectorY = sin(Angle) * Speed;

##### Share on other sites
EdwardDingle    129
Yeah, I understand that, but i'm trying to figure out how to use this class from having an angle and acceleration of a ship. This is how it used to be done, with just the acceleration of the ship, and the angle it was facing. I'm trying to figure out how to get x/y out of just an angle, or how I can rotate the ship in general.

if(thrusting && !isThrustingBackwards()){
accVector = new Vector2D(acc, angle);
}
else if(this.isThrustingBackwards() && !thrusting){
accVector = new Vector2D(acc*-1, angle);
}
else{
accVector = new Vector2D(0, angle);
}

Edit: Nevermind I see you answered my question. :)

##### Share on other sites
oliii    2196
angle / magnitude are just polar coordinates.

So basically

x = cos(angle) * magnitude
y = sin(angle) * magnitude

and the reverse

angle = atan2(y, x);
magnitude = sqrt(x*x + y*y);

You should really brush up on trigs and linear algebra, angles and magnitude are useful for some things, but in most cases, simple vector maths are much more handy for collision detection and physics.

##### Share on other sites
EdwardDingle    129
Alright, I successfully converted my code to use the vector class you provided using a few tweaks. Now how should I approach basic Rectangle Circle collisions using vector math?

##### Share on other sites
Atrix256    539
Don't forget - if you make nice, optimized collision detection with circles and rectangles but your game still is slow (or gets to a point where it's slow), think about using a grid for storing your objects in.

You'll be able to quickly cull out a lot of objects that you KNOW don't collide because they aren't in any of the same cells as the object you are testing, so you can throw them away before they are ever in your list for consideration.

But, at the same time, if after you find that your game runs plenty fast with this optimized vector class and collision detection routines, then stop there.

Fast enough is fast enough (:

for collision detection stuff...

Testing rectangle vs rectangle (assuming neither is rotated)

if(Rect1.MinX > Rect2.MaxX || Rect2.MinX > Rect1.MaxX || Rect1.MinY > Rect2.MaxY || Rect2.MinY > Rect1.MaxY){  //rectangles do not overlap}

For circle vs circle:

get the distance from the midpoint of one circle to the other. If that distance is < the radius of circle A + the radius of circle B, you know that the circles overlap.

For circle vs rectangle:

First find the closest point on the rectangle to the circle's center (info on that below).

Next, calculate the distance between that point and the center of the circle. If it's smaller than the circles radius, there's a collision.

Finding the closest point on a rectangle to a point (ie the center of the circle):

if(CircleMid.X < Rect.MinX)  ClosestPoint.X = Rect.MinX;else if(CircleMid.X > Rect.MaxX)  ClosestPoint.X = Rect.MaxX;else  ClosestPoint.X = CircleMid.X;if(CircleMid.Y < Rect.MinY)  ClosestPoint.Y = Rect.MinY;else if(CircleMid.Y > Rect.MaxY)  ClosestPoint.Y = Rect.MaxY;else  ClosestPoint.Y = CircleMid.Y;

bon apetit!

##### Share on other sites
EdwardDingle    129
Thanks! You guys have been a great help. Ill let you know how it goes.

##### Share on other sites
EdwardDingle    129
Thanks again, the code worked great, better than I expected actually, I had to write out the results because I did not actually understand why it worked along long walls, but I see why I was wrong now.

Now I need to figure out how to get the resulting angle and position after hitting the wall, which seems to be where I was having the most difficulty understanding before, and why I decided to come here for help.

The steps I need to do (and I have no clue if im right) is:
-Calculate how much penetration there has been into the rectangle.
-Move the circle against the wall
-Calculate New Vector(???)

##### Share on other sites
oliii    2196
the code for sphere - rectangle collision is relatively straight forward. The principle is easy (if you consider when a circle intersects a circle).

1) find point on rectangle perimeter the closest to the circle centre.
2) is that point outside the circle, no collision.
3) else push the sphere away so that that point is at exactly at the distance equal to the radius of the sphere, from the sphere centre.

Quote:
 Vector closestPointFromRectangle(Vector point, Vector min, Vector max){ Vector closest = point; if(point.x < min.x) closest.x = min.x; if(point.x > max.x) closest.x = max.x; if(point.y < min.y) closest.y = min.y; if(point.y > max.y) closest.y = max.y; return point;}bool CollideCircleOnRectangle(Vector& centre, float radius, Vector min, Vector max){ // closest point on rectangle to sphere centre Vector closest = closestPointFromRectangle(centre, min, max); // vector between sphere centre and closest point on rectangle Vector delta = (centre - closest); // distance, squared, between sphere centre and closest point on rectangle float distance_squared = delta.lengthSquared(); // if distance squared greater than radius squared, no intersection. if (distance_squared > radius * radius) return false; // distance between the sphere centre and closest point on rectangle float distance = sqrt(distance_squared); // vector needed to push sphere away from rectangle, so that distance // between sphere and closest point on rectangle is exactly equal to radius. Vector push_vector = delta * (radius - distance) / distance; // push sphere away from rectangle. centre += push_vector; return true; }

EDIT : if the sphere centre is inside the rectangle, you'll need some more code!

##### Share on other sites
EdwardDingle    129
How do I update the current vector that my ship is moving in? Do I add the push vector to that? When I do that it works, but I feel like there is a loss of momentum when I "bounce"

[Edited by - EdwardDingle on March 30, 2010 11:02:57 PM]

##### Share on other sites
oliii    2196
Quote:
 Do I add the push vector to that? When I do that it works, but I feel like there is a loss of momentum when I "bounce"

Nope, that's not accurate enough.

You reflect the velocity / displacement / move vector (whatever it is called) by 'reflecting' it against the collision normal, Which happens to be the delta vector (normalised). This reflection is basically calculating a collision impulse that will 'inverse' the velocity along the collision normal, thus making a bounce effect.

Quote:
 bool CollideCircleOnRectangle(Vector& centre, Vector& velocity, float radius, Vector min, Vector max){ // closest point on rectangle to sphere centre Vector closest = closestPointFromRectangle(centre, min, max); // vector between sphere centre and closest point on rectangle Vector delta = (centre - closest); // distance, squared, between sphere centre and closest point on rectangle float distance_squared = delta.lengthSquared(); // if distance squared greater than radius squared, no intersection. if (distance_squared > radius * radius) return false; // distance between the sphere centre and closest point on rectangle float distance = sqrt(distance_squared); // vector needed to push sphere away from rectangle, so that distance // between sphere and closest point on rectangle is exactly equal to radius. Vector push_vector = delta * (radius - distance) / distance; // push sphere away from rectangle. centre += push_vector; // collision normal Vector collision_normal = delta / distance; // coefficient of restitution (how much bounce you want). const float coef_restitution = 0.7f; // how much impact we get float impact_speed = velocity.dotProduct(collision_normal); // objects move away from each other. no collison impulse // or else the objects will 'stick' into each other. if(impact_speed > 0.0f) return true; // collision impulse Vector collision_impulse = collision_normal * (impact_speed * -(1.0f + coef_restitution)); // apply collision impulse velocity += collision_impulse; return true;}

##### Share on other sites
EdwardDingle    129
Thanks again, you're quite brilliant! :) Clearly I need to brush up on Euclidean vectors.