Collision reaction in a 2D side-scroller game similar to "Mario"

Question

This has been greatly bothering me in the past few weeks. In this time I've been researching online, even reading books in the Computers section at Borders to try to find an answer, but I haven't had much luck.

I programmed a 2D level editor for side-scroller video games. Now I want to turn it into a game where I have a player who can run and jump to explore the level, similar to "Mario".

The thing that is really giving me trouble is the collision response (not detection: I already know how to tell if two blocks are colliding). Here are some scenarios that I am going to illustrate so that you can see my problems (the shaded blocks are the ground, the arrow is the velocity vector of the player, the dashed lines are the projected path of the player).

See this collision response scenarios image:

http://dl.dropbox.com/u/12556943/collision_detection.jpg

Assume that the velocity vectors in scenarios (1) and (2) are equal (same direction and magnitude). Yet, in scenario (1), the player is hitting the side of the block, and in scenario (2), the player is landing on top of the block. This allows me to conclude that determining the collision response is dependent not only on the velocity vector of the player, but also the player's relative position to the colliding block. This leads to my first question: knowing the velocity vector and the relative position of the player, how can I determine from which direction (either left side, right side, top, or bottom) the player is colliding with the block?

Another problem that I'm having is how to determine the collision response if the player collides with multiple blocks in the same frame. For instance, assume that in scenario (3), the player collides with both of those blocks at the same time. I'm assuming that I'm going to have to loop through each block that the player is colliding with and adjust the reaction accordingly from each block. To sum it up, this is my second question: how do I handle collision response if the player collides with multiple blocks?

Notice that I never revealed the language that I'm programming in; this is because I'd prefer for you to not know (nothing personal, though :] ). I'm more interested in pseudo-code than to see language-specific code.

Thanks!

Answer 1

I think the way XNA's example platform game handles collisions could work well for you. I posted this answer to a very similar question elsewhere on Stack Overflow but will relay it here as well.

1. After applying movement, check for and resolve collisions.
2. Determine the tiles the player overlaps based on the player's bounding box.
3. Iterate through all of those tiles doing the following: (it's usually not very many unless your player is huge compared to your world tiles)
   1. If the tile being checked isn't passable:
      1. Determine how far on the X and Y axes the player is overlapping the non-passable tile
      2. Resolve collision by moving the player out of that tile only on the shallow axis (whichever axis is least penetrated)
         • For example, if Y is the shallow axis and the collision is below, shift the player up to no longer overlap that tile.
         • Something like this: if(abs(overlap.y) < abs(overlap.x)) { position.y += overlap.y; } else { position.x += overlap.x; }
      3. Update the bounding box's position based on the player's new position
      4. Move on to the next tile...
   2. If the tile being checked is passable, do nothing
4. If it's possible that resolving a collision could move the player into another collision, you may want to run through the above algorithm a second time. Or redesign your level.

The XNA version of this logic is in player.cs in the HandleCollisions() function if you are interested in grabbing their code to see what they specifically do there.

Answer 2

So what makes this a little more tricky is the constant force of gravity adjusting your players position. If your player jumps on top of a block they shouldn't bounce off they should land on top of the block and stay there. However, if the player hits a block on the left or right they shouldn't just stay there gravity must pull them down. I think that's roughly your question at a high level.

I think you'll want to separate the two forces of gravity and player velocity from collision detection/response algorithm. Using the velocity of the player if they collide with a block regardless of direction simply move the player's position to the edge of the collision, and subtract equal and opposite vector from the player's velocity since not doing this would cause them to collide yet again with the object. You will want to calculate the intersection point and place the player's position there on the block.

On a side note you could vary that really big force by what type of block the player collided with allowing for interesting responses like the player can break through the block if they are running fast enough (ie the player's velocity > than the force of the block)

Then continue to apply the constant force gravity to the player's position and continue doing your normal calculation to determine if the player has reached a floor.

I think by separating these two concepts you have a really simple straight forward collision response algorithm, and you have a fairly simple gravity-floor algorithm. That way you can vary gravity without having to redo your collision response algorithm. Say for example a water level, space level, etc and collision detection response is all the same.

Answer 3

I thought about this for a long time recently.

I am using the separating axis theorem, and so if I detected a collision I proceeded to project the object onto the normalized velocity vector and move the object by that distance in the direction of the negative velocity vector. Assuming the object came from a safe place this solution will position the object in a safe place post collision.

May not be the answer you're looking to get, but hopefully it'll point you in the right direction?