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'm working on collision resolution for my game.

I just need a good way to get an object out of another object if it gets stuck. In this case a car.

Here is a typical scenario. enter image description here

The red car is in the green object. How do I correctly get it out so the car can slide along the edge of the object as it should.

I tried:

if(buildings.size() > 0)
    {
        Entity e = buildings.get(0);
        Vector2D vel = new Vector2D();
        vel.x = vehicle.getVelocity().x;
        vel.y = vehicle.getVelocity().y;
        vel.normalize();
        while(vehicle.getRect().overlaps(e.getRect()))
        {
            vehicle.setCenter(vehicle.getCenterX() - vel.x * 0.1f, vehicle.getCenterY() - vel.y * 0.1f);
        }
        colided = true;
    }

But that does not work too well.

Is there some sort of vector I could calculate to use as the vector to move the car away from the object? Thanks

Here is my OBB2D class:

public class OBB2D
{

    // Corners of the box, where 0 is the lower left.
   private  Vector2D corner[] = new Vector2D[4];

   private Vector2D center = new Vector2D();
   private Vector2D extents = new Vector2D();

   private RectF boundingRect = new RectF();
   private float angle;

    //Two edges of the box extended away from corner[0]. 
   private  Vector2D axis[] = new Vector2D[2];

   private double origin[] = new double[2];

   public OBB2D(Vector2D center, float w, float h, float angle)
    {
       set(center,w,h,angle);
    }

   public OBB2D(float left, float top, float width, float height)
    {
       set(new Vector2D(left + (width / 2), top + (height / 2)),width,height,0.0f);
   }

   public void set(Vector2D center,float w, float h,float angle)
   {
         Vector2D X = new Vector2D( (float)Math.cos(angle), (float)Math.sin(angle));
           Vector2D Y = new Vector2D((float)-Math.sin(angle), (float)Math.cos(angle));

           X = X.multiply( w / 2);
           Y = Y.multiply( h / 2);

           corner[0] = center.subtract(X).subtract(Y);
           corner[1] = center.add(X).subtract(Y);
           corner[2] = center.add(X).add(Y);
           corner[3] = center.subtract(X).add(Y);

           computeAxes();
           extents.x = w / 2;
           extents.y = h / 2;
           computeDimensions(center,angle);
   }

   private void computeDimensions(Vector2D center,float angle)
   {
       this.center.x = center.x;
       this.center.y = center.y;   
       this.angle = angle;

       boundingRect.left = Math.min(Math.min(corner[0].x, corner[3].x), Math.min(corner[1].x, corner[2].x));
       boundingRect.top = Math.min(Math.min(corner[0].y, corner[1].y),Math.min(corner[2].y, corner[3].y));
       boundingRect.right = Math.max(Math.max(corner[1].x, corner[2].x), Math.max(corner[0].x, corner[3].x));
       boundingRect.bottom = Math.max(Math.max(corner[2].y, corner[3].y),Math.max(corner[0].y, corner[1].y)); 
   }

   public void set(RectF rect)
   {
       set(new Vector2D(rect.centerX(),rect.centerY()),rect.width(),rect.height(),0.0f);
   }

    // Returns true if other overlaps one dimension of this.
    private boolean overlaps1Way(OBB2D other)
    {
        for (int a = 0; a < axis.length; ++a) {

            double t = other.corner[0].dot(axis[a]);

            // Find the extent of box 2 on axis a
            double tMin = t;
            double tMax = t;

            for (int c = 1; c < corner.length; ++c) {
                t = other.corner[c].dot(axis[a]);

                if (t < tMin) {
                    tMin = t;
                } else if (t > tMax) {
                    tMax = t;
                }
            }

            // We have to subtract off the origin

            // See if [tMin, tMax] intersects [0, 1]
            if ((tMin > 1 + origin[a]) || (tMax < origin[a])) {
                // There was no intersection along this dimension;
                // the boxes cannot possibly overlap.
                return false;
            }
        }

        // There was no dimension along which there is no intersection.
        // Therefore the boxes overlap.
        return true;
    }


    //Updates the axes after the corners move.  Assumes the
    //corners actually form a rectangle.
    private void computeAxes()
    {
        axis[0] = corner[1].subtract(corner[0]); 
        axis[1] = corner[3].subtract(corner[0]); 

        // Make the length of each axis 1/edge length so we know any
        // dot product must be less than 1 to fall within the edge.

        for (int a = 0; a < axis.length; ++a) {
            axis[a] = axis[a].divide((axis[a].length() * axis[a].length()));
            origin[a] = corner[0].dot(axis[a]);
        }
    }

    public void moveTo(Vector2D center) 
    {
        Vector2D centroid = (corner[0].add(corner[1]).add(corner[2]).add(corner[3])).divide(4.0f);

        Vector2D translation = center.subtract(centroid);

        for (int c = 0; c < 4; ++c)
        {
            corner[c] = corner[c].add(translation);
        }

        computeAxes();
        computeDimensions(center,angle);
    }

    // Returns true if the intersection of the boxes is non-empty.
    public boolean overlaps(OBB2D other)
    {
        if(right() < other.left())
        {
            return false;
        }

        if(bottom() < other.top())
        {
            return false;
        }

        if(left() > other.right())
        {
            return false;
        }

        if(top() > other.bottom())
        {
            return false;
        }


        if(other.getAngle() == 0.0f && getAngle() == 0.0f)
        {
            return true;
        }

        return overlaps1Way(other) && other.overlaps1Way(this);
    }

    public Vector2D getCenter()
    {
        return center;
    }

    public float getWidth()
    {
        return extents.x * 2;
    }

    public float getHeight() 
    {
        return extents.y * 2;
    }

    public void setAngle(float angle)
    {
        set(center,getWidth(),getHeight(),angle);
    }

    public float getAngle()
    {
        return angle;
    }

    public void setSize(float w,float h)
    {
        set(center,w,h,angle);
    }

    public float left()
    {
        return boundingRect.left;
    }

    public float right()
    {
        return boundingRect.right;
    }

    public float bottom()
    {
        return boundingRect.bottom;
    }

    public float top()
    {
        return boundingRect.top;
    }

    public RectF getBoundingRect()
    {
        return boundingRect;
    }

    public boolean overlaps(float left, float top, float right, float bottom)
    {
        if(right() < left)
        {
            return false;
        }

        if(bottom() < top)
        {
            return false;
        }

        if(left() > right)
        {
            return false;
        }

        if(top() > bottom)
        {
            return false;
        }

        return true;
    }

};
share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

The quick and dirty answer to your question:

Is there some sort of vector I could calculate to use as the vector to move the car away from the object?

is: the normal of the face of the OBB that your car is colliding with, scaled by the distance that your car is penetrating the building.

There is a longer answer though, and how exactly you resolve this collision depends on how detailed and physically accurate you want the resolution to be. I'll describe your options here, and what's required to make them work, but I'll also encourage you to read some articles written by Chris Hecker if you are really interested in the details of rigid body dynamics. Now, back to your problem...

Like, I said, the quick way to do this is to push the car out along the normal of the face it is colliding with. The calculation of this normal depends on how you store the geometric information of you boxes. The one I prefer to use is a half-vector scheme as follows:

class OBB {
    Vector3 half_x;
    Vector3 half_y;
    Vector3 position;
    float rotation;
};

Please note that I intend the above definition to be language-agnostic. The reason I prefer this scheme is it makes implementing the Separating Axis Theorem easier to calculate, as the half-vectors also act as your projection axes. In turn, the advantage of using SAT is that you can calculate the distance that your car has penetrated your building. This is given by:

penetration = (project(car vectors onto axis).length + project(building vectors onto axis).length)
              - project((car.position-building) onto axis).length*2

I kind of wish there is an easier way for me to write that equation, but it should be clear if you read the tutorial on SAT at the link I provided. (Maybe I can throw together an image that demonstrates better and upload it here...).

From there, you just have to scale the normal by the amount of penetration and move your car's position with the resulting vector, and your car is precisely touching the side of your building. Yay!

Furthermore, this could be considered an accurate representation of where the car would be had it "slid" along the wall. Technically, the normal of the wall the car is hitting enacts a force on the car equal and opposite to the velocity of the car projected onto that normal (thus cancelling out the portion of the car's velocity that would cause it to penetrate the wall), and the car would just travel parallel to the wall. So yay! The car is where we expect it to be! Except...

If you wanted to take your collisions a step further, and add friction to the car scraping along the wall of your building, then the quick resolution I just described doesn't really work well, because the car wouldn't have been able to travel that far along the wall with friction present. I'm not going to go too far into this case; it's probably more that you need.

However, for the sake of knowing, it involves back-tracking your simulation using some fancy math to determine exactly where the car is the exact moment it collides with the wall, adjusting its velocity from that point, applying the force of friction and the resisting force of the wall, and stepping the simulation from there.

This ended up being really long... so thanks for reading! I hope this helps :)

share|improve this answer
    
Thanks a bunch for this. My OBB2D does use separate axis theorem. However I'm just not sure about a couple things: What is car vectors ? Is that the car's position? When you say project (car position - building) onto axis, which axis do I project onto? Thank you so much! –  Milo Nov 10 '12 at 13:59
    
I added my OBB2D class if that helps. –  Milo Nov 10 '12 at 14:32
add comment

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.