Collision detection for lemming/TIM-like game

Two friends and me made a game for a 72hour competition back in december. The game is kind of a mixture of Lemmings and The Incredible Machine: You need to help the main character reach the level exit by placing bricks and jump markers in the level; all of this in 2d. (You can find the current version of the game at my website.) However, the collision detection is very buggy. Let me illustrate the problem: Currently, the whole world is made up of bounding rectangles (axis-aligned). Collision is checked by checking whether two of these rectangles overlap. However, we also need to know what side of the brick/enemy the player collided with to determine the reaction (turn around, die etc.). E.g., there are bricks who are harmless if touched from above but lethal from any other direction. To check from what direction the collision occured, the overlapping rectangle is examined. If its width is greater than its height, the collision occured from above or below. If its height is greater than its width, the collision occured from the left or right. Obviously, this last part introduces bugs, e.g. when the falling velocity (or *any* velocity, for that matter) is high. So I'm looking for a better way to accomplish this. Some things I already came up with: - Make everything pixel-based and move the player only one pixel at a time. Con: I'd need to rewrite most of the game, since right now it's all floating-point ^^ - Do intersection tests from the player's corners moving with the player's velocity. E.g.:

player - moves to the bottom-right
 ---- 
|    |\ 
|    | \ 
 ----   \ 
 \    \  \ 
  \    \  \ 
   \    \  \ 
    \ ----  \ 
     |    |  \ 
     |    |   \ 
      ----     \ 
      brick

Since the ray that hits the brick first hits it from above, the hit is from above. But what if the object is small enough that none of the rays hits it? Has anyone got any other suggestions? I'm sure many people have done jump'n'runs before :)