I wrote a game called Cell a while ago and I decided to try adding some smoother timestep. Before I did this, the velocity variables were integral and in the update method I moved the entity 1 pixel at a time, checking if a collision occurred each step. Now the velocities are floating points, and in the update function the velocity is added to the appropriate co-ordinate variables (veloX to X, veloY to Y), and if a collision has been detected the entity is moved to the closest location that isn't inside a bound-box. There's a problem though; if you hit a wall you sometimes go through it for a split second and get moved back, and if you go fast enough you can even go straight through the bound-box and out of the level

How do you do collision detection with fractional velocities like this?

bump

There are a couple of things that I can think of that might help.

1. Check for collisions more often. This would be more accurate, but would also slow down your game.
2. Limit how fast you can go so that there isn't such a big gap between the locations.
3. Check for collisions before you actually move the object. Something like this pseudocode:

apply velocity ::custom
check for collision ::custom
if <(collided?) = [true]> then
  undo velocity ::custom
  ... // do other collision stuff
else
  move the object ::custom
  ...
end

Move the object in steps of [object size] rather than 1 px at a time (saves time, should only happen once but include the loop to prevent going through walls). If a collision occurs, then move backwards either one pixel at a time or with a binary search.

Also, make sure to do your x and y calculations separately. Move x, check x, move y, check y. Don't just move and check.

Raycasttrace!

Project a polygon from the object forward and check if that polygon intersects with anything else.

The hard part is then backing it out enough so that it doesn't intersect…

You don't need to use fractional velocities. You can use the nearest integer above or below the fractional value, and select above or below according to the error term. In other words adapt Bresenham's line drawing algorithm to your speed calculation.

Alternatively use a fixed motion step that's faster than you need, and do a similar calculation to generate a ‘frameskip’ so that you don't always move, thus slowing down your apparent speed. Distribute your frameskips evenly and the motion appears to be smooth.

When I dealt with collisions in my 3D engine, the approach I used was to specify cuboids that contained all my objects. Then, to detect collision, I'd check if the cuboid for the player intersected with any of the cuboids for the other objects.

To stop collisions being “missed” from going to fast, I then added the velocity of the player onto the bounds of the cuboid in the current direction (thus meaning that the player collision cuboid contained both the player and all the area it would move through in the next step).

To apply this to 2D, simply use rectangles instead of cuboids and ignore the 3rd dimension.

For further precision, as people have stated, you can move in single-pixel jumps and check for collisions each jump, but I found that this was unnecessary for most situations.