2
\$\begingroup\$

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

enter image description here

The same for y

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

\$\endgroup\$
  • \$\begingroup\$ Most physics libraries have collision detection, whats your coding language? \$\endgroup\$ – Zich Dec 2 '16 at 23:46
  • \$\begingroup\$ 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! \$\endgroup\$ – Zich Dec 2 '16 at 23:52
1
\$\begingroup\$

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.

You can find some images and additional code (in C++) about this on http://lazyfoo.net/tutorials/SDL/27_collision_detection/index.php.

Lasoloz

\$\endgroup\$
1
\$\begingroup\$

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- :) .

P.S. I wrote some additional comments in the code, please take your time to go over them.

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.