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 having a little difficulty figuring out the following scenarios.

In scenario A, the moving entity has fallen to (and slightly into the floor). The current position represents the projected position that will occur if I apply the acceleration & velocity as usual without worrying about collision. The Next position, represents the corrected projection position after collision check. The resulting end position is the falling entity now rests ON the floor--that is, in a consistent state of collision by sharing it's bottom X axis with the floor's top X axis.

My current update loop looks like the following:

// figure out forces & accelerations and project an objects next position
// check collision occurrence from current position -> projected position
   // if a collision occurs, adjust projection position

Which seems to be working for the scenario of my object falling to the floor. However, the situation becomes sticky when trying to figure out scenario's B & C.

In scenario B, I'm attempt to move along the floor on the X axis (player is pressing right direction button) additionally, gravity is pulling the object into the floor. The problem is, when the object attempts to move the collision detection code is going to recognize that the object is already colliding with the floor to begin with, and auto correct any movement back to where it was before.

In scenario C, I'm attempting to jump off the floor. Again, because the object is already in a constant collision with the floor, when the collision routine checks to make sure moving from current position to projected position doesn't result in a collision, it will fail because at the beginning of the motion, the object is already colliding.

How do you allow movement along the edge of an object? How do you allow movement away from an object you are already colliding with.

Extra Info My collision routine is based on AABB sweeping test from an old gamasutra article, http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php?page=3

My bounding box implementation is based on top left/bottom right instead of midpoint/extents, so my min/max functions are adjusted. Otherwise, here is my bounding box class with collision routines:

public class BoundingBox {
    public XYZ topLeft;
    public XYZ bottomRight;


    public BoundingBox(float x, float y, float z, float w, float h, float d)
    {
        topLeft = new XYZ();
        bottomRight = new XYZ();        
        topLeft.x = x;
        topLeft.y = y;
        topLeft.z = z;
        bottomRight.x = x+w;
        bottomRight.y = y+h;
        bottomRight.z = z+d;
    }

    public BoundingBox(XYZ position, XYZ dimensions, boolean centered)
    {
        topLeft = new XYZ();
        bottomRight = new XYZ();
        topLeft.x = position.x;
        topLeft.y = position.y;
        topLeft.z = position.z;
        bottomRight.x = position.x + (centered ? dimensions.x/2 : dimensions.x);
        bottomRight.y = position.y + (centered ? dimensions.y/2 : dimensions.y);
        bottomRight.z = position.z + (centered ? dimensions.z/2 : dimensions.z);
    }

    /**
     * Check if a point lies inside a bounding box
     * @param box
     * @param point
     * @return
     */
    public static boolean isPointInside(BoundingBox box, XYZ point)
    {
        if(box.topLeft.x <= point.x && point.x <= box.bottomRight.x
        && box.topLeft.y <= point.y && point.y <= box.bottomRight.y
        && box.topLeft.z <= point.z && point.z <= box.bottomRight.z)
            return true;
        return false;
    }

    /**
     * Check for overlap between two bounding boxes using separating axis theorem
     * if two boxes are separated on any axis, they cannot be overlapping
     * @param a
     * @param b
     * @return
     */
    public static boolean isOverlapping(BoundingBox a, BoundingBox b)
    {
        XYZ dxyz = new XYZ(b.topLeft.x - a.topLeft.x, b.topLeft.y - a.topLeft.y, b.topLeft.z - a.topLeft.z);

        // if b - a is positive, a is first on the axis and we should use its extent
        // if b -a is negative, b is first on the axis and we should use its extent
        // check for x axis separation
        if ((dxyz.x >= 0 && a.bottomRight.x-a.topLeft.x < dxyz.x)
        // negative scale, reverse extent sum, flip equality
          ||(dxyz.x < 0 && b.topLeft.x-b.bottomRight.x > dxyz.x))
            return false;
        // check for y axis separation
        if ((dxyz.y >= 0 && a.bottomRight.y-a.topLeft.y < dxyz.y)
        // negative scale, reverse extent sum, flip equality
          ||(dxyz.y < 0 && b.topLeft.y-b.bottomRight.y > dxyz.y))
            return false;
        // check for z axis separation
        if ((dxyz.z >= 0 && a.bottomRight.z-a.topLeft.z < dxyz.z)
        // negative scale, reverse extent sum, flip equality
          ||(dxyz.z < 0 && b.topLeft.z-b.bottomRight.z > dxyz.z))
            return false;       
        // not separated on any axis, overlapping
        return true;
    }

    public static boolean isContactEdge(int xyzAxis, BoundingBox a, BoundingBox b)
    {
        switch(xyzAxis) {
            case XYZ.XCOORD:
                if(a.topLeft.x == b.bottomRight.x || a.bottomRight.x == b.topLeft.x)
                    return true;
                return false;
            case XYZ.YCOORD:
                if(a.topLeft.y == b.bottomRight.y || a.bottomRight.y == b.topLeft.y)
                    return true;
                return false;
            case XYZ.ZCOORD:
                if(a.topLeft.z == b.bottomRight.z || a.bottomRight.z == b.topLeft.z)
                    return true;
                return false;
        }
        return false;
    }

    /**
     * Sweep test min extent value
     * @param box
     * @param xyzCoord
     * @return
     */
    public static float min(BoundingBox box, int xyzCoord)
    {
        switch(xyzCoord) {
            case XYZ.XCOORD:
                return box.topLeft.x;
            case XYZ.YCOORD:
                return box.topLeft.y;
            case XYZ.ZCOORD:
                return box.topLeft.z;
            default: return 0f;
        }
    }

    /**
     * Sweep test max extent value
     * @param box
     * @param xyzCoord
     * @return
     */
    public static float max(BoundingBox box, int xyzCoord)
    {
        switch(xyzCoord) {
            case XYZ.XCOORD:
                return box.bottomRight.x;
            case XYZ.YCOORD:
                return box.bottomRight.y;
            case XYZ.ZCOORD:
                return box.bottomRight.z;
            default: return 0f;
        }
    }   

    /**
     * Test if bounding box A will overlap bounding box B at any point
     * when box A moves from position 0 to position 1 and box B moves from position 0 to position 1
     * Note, sweep test assumes bounding boxes A and B's dimensions do not change
     * 
     * @param a0 box a starting position
     * @param a1 box a ending position
     * @param b0 box b starting position
     * @param b1 box b ending position
     * @param aCollisionOut xyz of box a's position when/if a collision occurs
     * @param bCollisionOut xyz of box b's position when/if a collision occurs
     * @return
     */
    public static boolean sweepTest(BoundingBox a0, BoundingBox a1, BoundingBox b0, BoundingBox b1, XYZ aCollisionOut, XYZ bCollisionOut)
    {
        // solve in reference to A
        XYZ va = new XYZ(a1.topLeft.x-a0.topLeft.x, a1.topLeft.y-a0.topLeft.y, a1.topLeft.z-a0.topLeft.z);
        XYZ vb = new XYZ(b1.topLeft.x-b0.topLeft.x, b1.topLeft.y-b0.topLeft.y, b1.topLeft.z-b0.topLeft.z);
        XYZ v = new XYZ(vb.x-va.x, vb.y-va.y, vb.z-va.z);

        // check for initial overlap
        if(BoundingBox.isOverlapping(a0, b0))
        {
            // java pass by ref/value gotcha, have to modify value can't reassign it
            aCollisionOut.x = a0.topLeft.x;
            aCollisionOut.y = a0.topLeft.y;
            aCollisionOut.z = a0.topLeft.z;
            bCollisionOut.x = b0.topLeft.x;
            bCollisionOut.y = b0.topLeft.y;
            bCollisionOut.z = b0.topLeft.z;
            return true;
        }

        // overlap min/maxs
        XYZ u0 = new XYZ();
        XYZ u1 = new XYZ(1,1,1);
        float t0, t1;

        // iterate axis and find overlaps times (x=0, y=1, z=2)
        for(int i = 0; i < 3; i++)
        {
            float aMax = max(a0, i);
            float aMin = min(a0, i);
            float bMax = max(b0, i);
            float bMin = min(b0, i);
            float vi = XYZ.getCoord(v, i);

            if(aMax < bMax && vi < 0)
                XYZ.setCoord(u0, i, (aMax-bMin)/vi);
            else if(bMax < aMin && vi > 0)
                XYZ.setCoord(u0, i, (aMin-bMax)/vi);

            if(bMax > aMin && vi < 0)
                XYZ.setCoord(u1, i, (aMin-bMax)/vi);
            else if(aMax > bMin && vi > 0)
                XYZ.setCoord(u1, i, (aMax-bMin)/vi);

        }

        // get times of collision
        t0 = Math.max(u0.x, Math.max(u0.y, u0.z));
        t1 = Math.min(u1.x, Math.min(u1.y, u1.z));
        // collision only occurs if t0 < t1
        if(t0 <= t1 && t0 != 0) // not t0 because we already tested it!
        {
            // t0 is the normalized time of the collision
            // then the position of the bounding boxes would
            // be their original position + velocity*time
            aCollisionOut.x = a0.topLeft.x + va.x*t0;
            aCollisionOut.y = a0.topLeft.y + va.y*t0;
            aCollisionOut.z = a0.topLeft.z + va.z*t0;
            bCollisionOut.x = b0.topLeft.x + vb.x*t0;
            bCollisionOut.y = b0.topLeft.y + vb.y*t0;
            bCollisionOut.z = b0.topLeft.z + vb.z*t0;
            return true;
        }
        else
            return false;
    }
}
share|improve this question

1 Answer 1

up vote 1 down vote accepted

As always, there are multiple possibilities depending on your objectives (simplicity, speed, accuracy). One easy solution here is to treat each axis independently.

  • figure out forces & accelerations and project an objects next position
  • check collision occurrence from current position -> projected position
    • if no collision occurs on x axis then set x to projected position
    • if no collision occurs on y axis then set y to projected position

It is not necessary to use a sweep test for this, a simple intersection test will suffice. The downside of using such a direct approach is that it can still give incorrect results if the destination point results in another collision. The trick to improving the accuracy is to either cap the velocity of the character, or use a small time span, possibly performing collision detection multiple times per frame.

The slightly harder solution which gives better results is to use the sweep test to return the time of collision (or depth vector), then move the character to this point. This is more general purpose and will be more accurate than the other method, it will add additional complexity to the force and acceleration components which need to be scaled according to the time of impact time. The stability of the integrator also becomes more relevant, and multiple simultaneous collision becomes more problematic.

Edit:

@Jeremy: You must not reset the position after the collision. Start with the current position and the predicted position. Consider each axis by itself - reducing the problem from n dimensions down to 1. For example: If the object collides at the predicted position on the x axis, you don't do anything, leave the x position unchanged, but if it does not collide on the x axis, the you set the new x position to the predicted x position. Repeat this for the other axes. The (rather crude) result will be that your character can move along an axis as long as there is no collision. Implemented as-is this may result in conditions where your character does not touch the walls or floors but appears to collide a short distance away. Solutions to avoid this are:

  1. Use a low velocity so that the change between the current position and predicted position is never more than some acceptable value (say a pixel). Admittedly this is probably the worst and most limiting solution.

  2. Use a small time step so that the velocity at any moment is never greater than a threshold (say a pixel). Slightly better than the previous solution, but not very practical as higher velocities will require a smaller time step.

  3. Recursively sub-divide the time step to find the closest point to the wall/floor which does not result in a collision. This is a good trade off in terms of performance and complexity. Not the best performance but not overly complex to implement.

  4. Update the sweep function to return the time of impact (instead of a true/false value) and use this to scale the projected position based on the time.

For perfect accuracy (for example, if bounce or friction is needed) it may be necessary to sub-divide the simulation step. For example, if you jump towards a wall and the impact occurs half-way through the time step you will need to recalculate the forces at the point of impact, and run the simulation step again with the remaining segment of time. Not that this can result in infinite recursion (for example if two objects are stacked) so some means are necessary to prevent this (i.e. limiting the number of recursions or amount of time spent in the calculation).

share|improve this answer
    
Thanks for replying lukevanin. However, these don't seem to address some of my concerns. How do you address when there is a constant collision (ie, sliding along the floor or down a wall)? If I reset my position if the end result is a collision, how will the object move at all? –  Jeremy Giberson Nov 22 '11 at 8:12
1  
@JeremyGiberson I added some more detail to try clarify what I was trying to explain. I will add some code later which will hopefully help explain it better. –  Luke Van In Nov 22 '11 at 12:03

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.