# Tile based collision detection failing when player is going too fast

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 {
} 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) {
_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));
}
}

• Your algorithm looks sound. A code snippet would be useful. – JRT May 21 '11 at 11:57
• JRT: Actually his algorithm is flawed, if the goal is to prevent the player from passing through objects. – Olhovsky May 21 '11 at 12:11
• My understanding is that the character is moving so fast it has gone completely through the platform in the time between two frames and so the collision isn't being detected. – CiscoIPPhone May 21 '11 at 12:14
• @CiscoIPPhone: Exactly. When the the player is going slower the collision detection works fine. – Sven van Zoelen May 21 '11 at 12:35
• @Olhovsky: If his intention is to calculate the next position, then check for a collision based on the calculated position, then why is this flawed? (His implementation may well be flawed) – JRT May 21 '11 at 12:54

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.
• I implemented the first method and increased the frame rate to 60. Now I still got the problem that the player goes trough the ground (sometimes). My tiles are 16x16. Maybe a max velocity y? The second method sounds good, but I'm wondering how to get the lines of the blocks close to the line from the start to new postion line to find the intersection. – Sven van Zoelen May 21 '11 at 15:07
• You should definitely have a max falling speed. This would help tremendously and I don't think it would be a huge deal to the player. – Michael Coleman May 21 '11 at 18:15
• There is a terminal velocity for things falling in real life so you'd actually be making it more realistic =) – CiscoIPPhone May 21 '11 at 18:21
• I implemented the max velocity y and tweeked the gravity and player jump physics. And it works like a charm. Thanks for the link and information! – Sven van Zoelen May 21 '11 at 18:25

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.

• The time elapsed method will keep up with the delay by updating the physics with the lost time. Your method in the other hand will not catch up with the delay when the update cycles will be higher then 10 milliseconds (not smooth). – Sven van Zoelen May 22 '11 at 9:13
• That is only a problem if you set the update rate too high for the computer to keep up. You'd do variable step 20 years ago because stuff like this was on on the limit of what a computer could handle. That is not so any more. – aaaaaaaaaaaa May 22 '11 at 10:32
• But then you still have a gap in time that is not caught by your physics when the elapsed time exceeds let's say 100, because the user's machine was busy with other more important processes. – Sven van Zoelen May 22 '11 at 19:41
• Have you actually read and understood the code? Unless the physics takes more than 10 ms per step it will always do a complete catchup. – aaaaaaaaaaaa May 22 '11 at 20:53
• I wrote it down on the whiteboard and you are right. It will check all the collisions correctly, but when the delay is to big the renderer will lag. But what will hapen when your nextUpdate stays under the 10 milliseconds? – Sven van Zoelen May 23 '11 at 7:28