Tile based collision detection failing when player is going too fast

Question

I'm creating a side scroller and I'm have a problem with my collision detection.

The collision detection works perfect when the player is falling at a constant speed, but when I implement more realistic gravity the player falls too fast - resulting in that the collision will be checked with the tiles under the floor/platform causing the player to be able to jump through platforms.

The way my update and collision works is like following:

• Update entities velocity (no position change)
• Check for collisions (first x, then y)
  • if collision, then move the entity as close as possible, otherwise set the position with the velocity.

The collision method works like this:

• Get the four corners of the player.
• Get from that four corners the tiles.
• Collision check.

How can I solve this problem?

UPDATE

Added the code to make it more clear.

The main loop:

_frames_a_sec = 60;    
public void run() {
        while(true) {
            long timeElapsed = System.currentTimeMillis() - _lastUpdate;
            _lastUpdate = System.currentTimeMillis();

            if(timeElapsed > 80) {
                timeElapsed = 80;
            }

            update((int)timeElapsed);

            try {
                Thread.sleep((1000/_FRAMES_A_SEC));
            } catch(Exception ex) { }
        }
    }

Map update method:

public void update(int timeElapsed) {
        //update entities
        for(Entity entity : _mapEntities) {
            entity.update(timeElapsed);
        }

        //check for collisions
        checkMapCollision();
    }

Entity (abstract) update method:

public void update(int timeElapsed) {
        _velocity.x = 0.0F;

        if(!_isOnLand) {
        //add gravity
        _velocity.y += Map._GRAVITY_PER_SEC * timeElapsed;
    } else {
        _velocity.y = 0.0F;
    }
}

Mario (extends Entity) update method:

@Override
    public void update(int timeElapsed) {
        super.update(timeElapsed);

        if(_state == STATES.IDLE) {

        } else if(_isMoving) {
            _marioSmallWalk.update(timeElapsed);
        }

        if(_state == STATES.JUMPING) {
            setVelocityY(getVelocity().y + _jumpSpeed);

            _jumpSpeed += _JUMP_DECREASE * timeElapsed;

            //falling?
            if(getVelocity().y > 0) {
                setState(STATES.FALLING);
            }
        } 

        if(_isMoving) {
            double walkSpd = (_WALK_SPEED_SEC * timeElapsed);

            if(getFacing() == FACING.LEFT) {
                walkSpd = -walkSpd;
            }

            setVelocityX(getVelocity().x + walkSpd);
        }

        //falling?
        if(getVelocity().y > (Map._GRAVITY_PER_SEC * timeElapsed) + 1.0F) {
            setState(STATES.FALLING);
        }
    }

Map Collsion check method:

public void checkMapCollision() {
    for(Entity entity : _mapEntities) {
        placeEntityAtX(entity);
        placeEntityAtY(entity);
    }
}

X check method:

private void placeEntityAtX(Entity entity) {
        Vector2d dir = entity.getDirection();
        Rectangle bounds = entity.getBounds();
        boolean positionSet = false;

        bounds = new Rectangle((int)(bounds.x + dir.x), bounds.y, bounds.width, bounds.height);
        Block[] corners = getCornerBlocks(bounds);

        if(dir.x > 0) {
            if(corners[1].isSolid() || corners[3].isSolid()) {
                Rectangle blkBounds;

                if(corners[3].isSolid()) {
                    blkBounds = corners[3].getBounds();
                } else {
                    blkBounds = corners[1].getBounds();
                }

                entity.setPositionX(blkBounds.x - (bounds.width-entity.getCurrentSprite().getOffsetX())-1);
                positionSet = true;
            }
        } else if(dir.x < 0) {
            if(corners[0].isSolid() || corners[2].isSolid()) {
                Rectangle blkBounds;

                if(corners[2].isSolid()) {
                    blkBounds = corners[2].getBounds();
                } else {
                    blkBounds = corners[0].getBounds();
                }

                entity.setPositionX(blkBounds.x + blkBounds.width + (bounds.width/2) + 1);
                positionSet = true;
            }
        }

        if(!positionSet) {
            //set the original position
            entity.setPositionX((int)(entity.getX() + dir.x));
        }
    }

and the y:

private void placeEntityAtY(Entity entity) {
        Vector2d dir = entity.getDirection();
        Rectangle bounds = entity.getBounds();
        boolean positionSet = false;

        bounds = new Rectangle(bounds.x, (int)(bounds.y + dir.y), bounds.width, bounds.height);
        Block[] corners = getCornerBlocks(bounds);

        //moving down
        if(dir.y > 0) {
            if(corners[2].isSolid() || corners[3].isSolid()) {
                Rectangle blkBounds = null;

                if(corners[2].isSolid()) {
                    blkBounds = corners[2].getBounds();
                } else {
                    blkBounds = corners[3].getBounds();
                }

                entity.setPositionY(blkBounds.y);
                entity.landed();
                positionSet = true;
            } 
        } else if (dir.y < 0) {
            if(corners[0].isSolid() || corners[1].isSolid()) {
                Rectangle blkBounds = null;

                if(corners[0].isSolid()) {
                    blkBounds = corners[0].getBounds();
                } else {
                    blkBounds = corners[1].getBounds();
                }

                entity.setPositionY(blkBounds.y + blkBounds.height + bounds.height);
                entity.roof();
                positionSet = true;
            }
        } else {
            if(!corners[2].isSolid() && !corners[3].isSolid()) {
                entity.falling();
            }
        }

        if(!positionSet) {
            //set the original position
            entity.setPositionY((int)(entity.getY() + dir.y));
        }
    }

Answer 1

I know of two ways that will solve this problem.

First method: Fixed Time Step Physics

You can use fixed timestep physics with a high enough frequency that you will detect all the collisions.

What this means is that you will decide on a physics update delta, e.g. 1/60th of a second. Then for each frame of your game you'll calculate how much time has passed since the last frame, divide this by the physics update delta. This is how many physics updates you have to do that frame. In other words, instead of doing a single physics update and then collision check, you will be doing many smaller updates.

• Pros: This is probably the easiest solution to implement
• Cons: May not be practical, depending on how small your collision items are, and how fast they move.

See this question which compares fixed and variable timestep (and there's some useful links in the question itself).

Second method: Swept Collision Detection

You can to calculate the vector between the current position of the player and the projected position of the player, and do your collisions between this line and the platforms.

• Pros: Would work even with very very fast moving and small bodies.
• Cons: Movement in reality due to gravity won't be a straight line, sweeping/integrating the path of multiple accelerating bodies is potentially a difficult maths problem.

Answer 2

Up the physics update rate until it works, it doesn't have to coincide with the framerate. I'd always do my timing like:

physicsStep=25
physicsdivider=3
nextUpdate=currentTime()*physicsdivider
while(1){
    while(nextUpdate<currentTime()*physicsdivider){
        doPhysics()
        nextUpdate+=physicsStep
    }
    doRender()
}

Edit: Updated the code to do 120 rather than 100 Hz as that will be a little smoother on screens running 60 Hz.

What happens is that the inner loop repeats until the physics have caught up with the current time, only then is frame rendered. With v-Sync enabled on a 60 Hz monitor the result should be this:

render   00 ms
physics
physics
render   17 ms
physics
physics
render   33 ms
...

With exactly 120 physics updates per second, and 60 render updates per second

If the video card is too slow to do 60 Hz some of the render updates will be dropped, but the physics will still be exactly the same with 120 updates per second.

This only works well as long as the physics can stay comfortably within the allotted time of 8 1/3 ms per updated. You should try timing a physics update to get an idea of how close to being a problem this is.

By the way, I can't find the render and flip commands in your code. In any case, simply calling a sleep 16 ms once for every update is a very poor method of timing, that way you are invariably going to drop frames.