Jump to content
  • Advertisement
Sign in to follow this  
EdwardDingle

2D Collisions

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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;
	}
	
	public Vector2D addVector(Vector2D newVect){		
		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 this post


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


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


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


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


Link to post
Share on other sites
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);
currentVector.addVector(accVector);
}
else if(this.isThrustingBackwards() && !thrusting){
accVector = new Vector2D(acc*-1, angle);
currentVector.addVector(accVector);
}
else{
accVector = new Vector2D(0, angle);
currentVector.addVector(accVector);
}

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

Share this post


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


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


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


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!