# 2D moving sprites collision

I'm trying to create a game where i have two abjects A and B

1 :I know the shape of the two objects(Rectangles) .

2 :The speed and position of each object.

And i'm trying to figure out if the two object will eventually collide .

I calcuted the point where the object's paths intersect using this formula

The same for y

But i still don't know if the two object will actually collide or will miss each other .

• Most physics libraries have collision detection, whats your coding language? – Iman Dec 2 '16 at 23:46
• If you are going to write a collision detector, I propose to use a 2 step check the first checks the origins and size to provide a rough estimation some times it is not needed to use an accurate formula this will be very fast and the secound step(if the first says you have a possible collide) goes more into detail and check the exact situation, using a exact method for all cases will slow your game. Go find a physic lib I still recommend! Does the objects rotate during their move? Cause that will make it harder! – Iman Dec 2 '16 at 23:52

You just need to compare sidelines. These are the algebraic representations of vertical or horizontal lines. Note, this will return only the current value, not what will be, but from here is only one step to do that.

Let's define a Rectangle with the following properties:

Rectangle.x1: rectangle's left side line (this is a vertical line)

Rectangle.x2: rectangle's right side line (same)

Rectangle.y1: rectangle's top side line (this is a horizontal line)

Rectangle.y2: rectangle's bottom side line (same)

These values are properties of your rectangle and they can be any type of numerical data (int, float,...). The algorithm will use two Rectangles, and compare their sides (in pseudocode):

Function rectCollision(rect1, rect2)
{
if (rect1.x1 > rect2.x2) //the first rectangle is after the second rectangle, they are not colliding
or (rect1.x2 < rect2.x1) //the first rectangle is before the second
or (rect1.y1 > rect2.y2) //the first is under the second
or (rect1.y2 < rect2.y1) //the first is above the second
//then
{
return false
}
else
{
//there is explicitly no other way for collision
return true
}
}


How is this working? We are projecting the collision boxes on the x and y axis. They are not meeting, if they are not colliding on x OR on y axis. If they are colliding on x and y axis too, then bang, we got a collision.

Lasoloz

Check out this source. I wrote the code below based off of it to make it more friendly for a C# application. This works with convex polygons as well which might be a little overkill for you, considering you only need rectangles, but it works none the less.

I found more tutorials and explanations of why the separate axis theorem (which this uses) works, and so I think you'll appreciate this link. Also, this link might come in handy in the future too, if you're looking for specific points enclosed in polygons- :) .

public class MainForm {

// Structure that stores the results of the PolygonCollision function
public struct PolygonCollisionResult {
public bool WillIntersect; // Are the polygons going to intersect forward in time?
public bool Intersect; // Are the polygons currently intersecting
public Vector MinimumTranslationVector; // The translation to apply to polygon A to push the polygons apart
}

// Check if polygon A is going to collide with polygon B for the given velocity
public static PolygonCollisionResult PolygonCollision(Polygon polygonA, Polygon polygonB, Vector velocity) {
var result = new PolygonCollisionResult
{
Intersect = true,
WillIntersect = true
};

int edgeCountA = polygonA.Edges.Count;
int edgeCountB = polygonB.Edges.Count;
float minIntervalDistance = float.PositiveInfinity;
Vector translationAxis = new Vector(); //default value
Vector edge;

// Loop through all the edges of both polygons
for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
if (edgeIndex < edgeCountA) {
edge = polygonA.Edges[edgeIndex];
} else {
edge = polygonB.Edges[edgeIndex - edgeCountA];
}

// ===== 1. Find if the polygons are currently intersecting =====

// Find the axis perpendicular to the current edge
Vector axis = new Vector(-edge.Y, edge.X);
axis.Normalize();

// Find the projection of the polygon on the current axis
float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;
ProjectPolygon(axis, polygonA, ref minA, ref maxA);
ProjectPolygon(axis, polygonB, ref minB, ref maxB);

// Check if the polygon projections are currentlty intersecting
if (IntervalDistance(minA, maxA, minB, maxB) > 0)
result.Intersect = false;

// ===== 2. Now find if the polygons *will* intersect =====

// Project the velocity on the current axis
float velocityProjection = axis.DotProduct(velocity);

// Get the projection of polygon A during the movement
if (velocityProjection < 0) {
minA += velocityProjection;
} else {
maxA += velocityProjection;
}

// Do the same test as above for the new projection
float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
if (intervalDistance > 0)
result.WillIntersect = false;

// If the polygons are not intersecting and won't intersect, exit the loop
if (!result.Intersect && !result.WillIntersect)
break;

// Check if the current interval distance is the minimum one. If so store
// the interval distance and the current distance.
// This will be used to calculate the minimum translation vector
intervalDistance = Math.Abs(intervalDistance);
if (intervalDistance < minIntervalDistance) {
minIntervalDistance = intervalDistance;
translationAxis = axis;

Vector d = polygonA.Center - polygonB.Center;
if (d.DotProduct(translationAxis) < 0)
translationAxis = -translationAxis;
}
}

// The minimum translation vector can be used to push the polygons appart.
// First moves the polygons by their velocity
// then move polygonA by MinimumTranslationVector.
if (result.WillIntersect)
result.MinimumTranslationVector = translationAxis * minIntervalDistance;

return result;
}

// Calculate the distance between [minA, maxA] and [minB, maxB]
// The distance will be negative if the intervals overlap
public static float IntervalDistance(float minA, float maxA, float minB, float maxB) {
if (minA < minB) {
return minB - maxA;
} else {
return minA - maxB;
}
}

// Calculate the projection of a polygon on an axis and returns it as a [min, max] interval
public static void ProjectPolygon(Vector axis, Polygon polygon, ref float min, ref float max) {
// To project a point on an axis use the dot product
float d = axis.DotProduct(polygon.Points[0]);
min = d;
max = d;
for (int i = 0; i < polygon.Points.Count; i++) {
d = polygon.Points[i].DotProduct(axis);
if (d < min) {
min = d;
} else {
if (d > max) {
max = d;
}
}
}
}
}


How to use: What you want to do is create a struct type PolygonCollisionResult. Call the PolygonCollision method with the required parameters and store the result in that struct.

The concepts in the code do not belong to me in any way, shape, or form.

Hope this helps, and good luck on your game!