Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a square, tile-based collision map. To check if one of my (square) entities is colliding, I get the vertices of the 4 corners, and test those 4 points against my collision map. If none of those points are intersecting, I know I'm good to move to the new position.

I'd like to allow entities to rotate. I can still calculate the 4 corners of the square, but once you factor in rotation, those 4 corners alone don't seem to be enough information to determine if the entity is trying to move to a valid state.

For example:

In the picture below, black is unwalkable terrain, and red is the player's hitbox. The left scenario is allowed because the 4 corners of the red square are not in the black terrain.

The right scenario would also be (incorrectly) allowed, because the player, cleverly turned at a 45* angle, has its corners in valid spaces, even if it is (quite literally) cutting the corner.

enter image description here

How can I detect scenarios similar to the situation on the right?

share|improve this question
3  
Have you looked into the Separating Axis Theorem? Here's an example complete with code. –  NoobsArePeople2 Nov 30 '12 at 5:32
    
@NoobsArePeople2 Looks promising. I'd never heard of it before, actually. –  Raven Dreamer Nov 30 '12 at 12:47
add comment

1 Answer 1

up vote 6 down vote accepted

I finally got a decent collision detection implemented. I wound up using a 3d version of XenoCollide / Minkowski Portal Refinement, a la Gary Snethen in Game Programming Gems 7.

I've created a C# implementation of MPR below. It will return the direction of the minimum penetration vector. I know it's possible to return actual collision points, but I've not been able to implement that part, yet.

At any rate, here's the code for Minkowski Portal Refinement (MPR) / XenoCollide in 3d:

using System.Collections;
using System.Collections.Generic;

    //make the associated dot / cross products easier to read
    public static class Vector3Extensions
    {
        public static float Dot(this Vector3 op1, Vector3 op2)
        {
            return Vector3.Dot(op1, op2);
        }

        public static Vector3 Cross(this Vector3 op1, Vector3 op2)
        {
            return Vector3.Cross(op1, op2);
        }
    }

public static class MPRCollision {

    //points used by the algorithm
    static Vector3 v0;
    static Vector3 v1;
    static Vector3 v2;
    static Vector3 v3;
    static Vector3 v4;

    //if the difference in iteration is less than this,
    //we aren't going to (can't!) converge.
    static float kCollideEpsilon = 1e-3f;

    static Vector3 GetSupport(List<Vector3> shape, Vector3 direction)
    {


        Vector3 point = shape[0];

        for(int i = 1; i < shape.Count; i++)
        {
            //is the current point more "direction" than our result point?
            if ( (shape[i] - point).Dot(direction) > 0 )
            {
                //new result point
                point = shape[i];
            }
        }
        return point;

    }


    public static bool CheckCollide(List<Vector3> shape1, List<Vector3> shape2,
                                    Vector3 center1, Vector3 center2, ref Vector3 penVector)
    {
        //holding variables
        Vector3 n = Vector3.zero;
        Vector3 swap = Vector3.zero;

        // v0 = center of Minkowski sum
        v0 = center2 - center1;

        // Avoid case where centers overlap -- any direction is fine in this case
        if (v0 == Vector3.zero) v0 = new Vector3(0, 0.00001f, 0);

        // v1 = support in direction of origin
        n = -v0;

        //get the differnce of the minkowski sum
        Vector3 v11 = GetSupport(shape1, -n);
        Vector3 v12 = GetSupport(shape2, n);

        v1 = v12 - v11;

        //if the support point is not in the direction of the origin
        if (v1.Dot(n) <= 0)
        {
            //return the direction of the origin, because we're not colliding
            if (penVector != null) penVector = n;
            return false;
        }

        // v2 - support perpendicular to v1,v0
        n = v1.Cross(v0);
        if (n == Vector3.zero)
        {
            //v1 and v0 are parallel, which means 
            //the origin is within the first portal?
            n = v1 - v0;

            if (penVector != null) penVector = n.normalized;
            return true;
        }

        //no early outs yet, so get the new support point
        Vector3 v21 = GetSupport(shape1, -n);
        Vector3 v22 = GetSupport(shape2, n);
        v2 = v22 - v21;

        if (v2.Dot(n) <= 0)
        {
            //can't reach the origin in this direction, ergo, no collision
            if (penVector != null) penVector = n;
            return false;
        }

        // Determine whether origin is on + or - side of plane (v1,v0,v2)
        //tests linesegments v0v1 and v0v2
        n = (v1 - v0).Cross(v2 - v0);
        float dist = n.Dot(v0);

        // If the origin is on the - side of the plane, reverse the direction of the plane
        if (dist > 0)
        {
            //swap the winding order of v1 and v2
            swap = v1;
            v1 = v2;
            v2 = swap;

            //swap the winding order of v11 and v12
            swap = v12;
            v12 = v11;
            v11 = swap;

            //swap the winding order of v11 and v12
            swap = v22;
            v22 = v21;
            v21 = swap;

            //and swap the plane normal
            n = -n;
        }


        ///
        // Phase One: Identify a portal

        while (true)
        {
            // Obtain the support point in a direction perpendicular to the existing plane
            // Note: This point is guaranteed to lie off the plane
            Vector3 v31 = GetSupport(shape1, -n);
            Vector3 v32 = GetSupport(shape2, n); 
            v3 = v32 - v31;

            if (v3.Dot(n) <= 0)
            {
                //can't enclose the origin within our tetrahedron
                if (penVector != null) penVector = n;
                return false;
            }

            // If origin is outside (v1,v0,v3), then eliminate v2 and loop
            if (v1.Cross(v3).Dot(v0) <= 0)
            {
                //failed to enclose the origin, adjust points;
                v2 = v3;
                v21 = v31;
                v22 = v32;
                n = (v1 - v0).Cross(v3 - v0);
                continue;
            }

            // If origin is outside (v3,v0,v2), then eliminate v1 and loop
            if (v3.Cross(v2).Dot(v0) < 0)
            {
                //failed to enclose the origin, adjust points;
                v1 = v3;
                v11 = v31;
                v12 = v32;
                n = (v3 - v0).Cross(v2 - v0);
                continue;
            }


            bool hit = false;

            ///
            // Phase Two: Refine the portal

            int phase2 = 0;

            // We are now inside of a wedge...
            while (phase2 < 20)
            {
                phase2++;

                // Compute normal of the wedge face
                n = (v2 - v1).Cross(v3 - v1);

                n.Normalize();

                // Compute distance from origin to wedge face
                float d = n.Dot(v1);

                // If the origin is inside the wedge, we have a hit
                if (d >= 0 && !hit )
                {
                    if (penVector != null) penVector = n;
                    hit = true;
                }


                // Find the support point in the direction of the wedge face
                Vector3 v41 = GetSupport(shape1, -n);
                Vector3 v42 = GetSupport(shape2, n);
                v4 = v42 - v41;


                float delta = (v4 - v3).Dot(n);
                float separation = -(v4.Dot(n));

                if (delta <= kCollideEpsilon || separation >= 0)
                {
                    //Debug.Log("Non-convergance detected");    
                    if (penVector != null) penVector = n;
                    return hit;
                }

                // Compute the tetrahedron dividing face (v4,v0,v1)
                float d1 = v4.Cross(v1).Dot(v0);

                // Compute the tetrahedron dividing face (v4,v0,v2)
                float d2 = v4.Cross(v2).Dot(v0);

                // Compute the tetrahedron dividing face (v4,v0,v3)
                float d3 = v4.Cross(v3).Dot(v0);

                if (d1 < 0)
                {
                    if (d2 < 0)
                    {
                        // Inside d1 & inside d2 ==> eliminate v1
                        v1 = v4;
                        v11 = v41;
                        v12 = v42;
                    }
                    else
                    {
                        // Inside d1 & outside d2 ==> eliminate v3
                        v3 = v4;
                        v31 = v41;
                        v32 = v42;
                    }
                }
                else
                {
                    if (d3 < 0)
                    {
                        // Outside d1 & inside d3 ==> eliminate v2
                        v2 = v4;
                        v21 = v41;
                        v22 = v42;
                    }
                    else
                    {
                        // Outside d1 & outside d3 ==> eliminate v1
                        v1 = v4;
                        v11 = v41;
                        v12 = v42;
                    }
                }
            }   

            return false;
        }
    }
}
share|improve this answer
    
-1 "I kind of fixed it, here's all my code" is a really unsatisfying answer. What did you change? What was the intuition behind your changes? –  Anko Dec 23 '12 at 13:45
    
@Anko What are you referring to? –  Raven Dreamer Dec 23 '12 at 14:16
    
You had collision code. Then you changed something and to fix a problem with it, right? What did you change? –  Anko Dec 23 '12 at 15:23
    
@Anko You mean my edit? I was missing an "=" in a "<=". This meant the code did not detect contact collisions in some cases. –  Raven Dreamer Dec 23 '12 at 15:39
1  
I get it now. In that case, your code is properly helpful. I'd like to upvote instead, but apparently SE "locks in" downvotes unless the answer is edited. :/ I've put in a small clarifying edit for peer review and will fix my vote when that gets through. Thanks for explaining! –  Anko Dec 23 '12 at 16:21
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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