Opinions on platform game actor/background collision resolving

Question

Imagine the following scenario: I have a level whose physical structure is built up from a collection of bounding rectangles, combined with prerendered bitmap backgrounds. My actors, including the player character, all have their own bounding rectangle. If an actor manages to get stuck inside a level block, partially or otherwise, it'll need to be shifted out again, so that it is flush against the block.

The untested technique I thought up during bio break is as follows:

If an actor's box is found to intersect a level box, determine where the centerpoints of each rect are. If the actor's center is higher than the level box's, move the actor so that the bottom of the actor's rect is flush with the top of the level's rect, and vice versa if it's lower. Then do a similar thing horizontally.

Opinions on that? Suggestions on better methods?

Actually, the bounding rects are XNA BoundingBoxes with their Z spanning from -1 to 1, but it's still 2D gameplay.

Answer 1

A lot depends on the details. A complete solution could take into account velocities or other issues. But treating this simply...

You don't want to always resolve vertically first. Imagine an actor nudges horizontally into a block. If you resolve vertically first then the actor will pop up above that block, when a small horizontal movement would have sufficed.

Find what the vertical and horizontal movements would need to be to "get out of collision", and then apply the one with the smallest absolute value.

Then repeat a few times, in case the movement puts the actor into another block. But don't repeat forever, because the actor could be wedged somewhere that never resolves.

Maybe if your last movement still leaves you in collision, you could just average the last two movements and leave it there.

Answer 2

What the "real" physics engines do is find the minimum penetration vector. That is - the smallest vector that represents how far inside each other the two objects penetrate.

For an AABB (axis-aligned bounding box) this is really easy to calculate.

(Consider making your own 2D AABB structure, it will be smaller and therefore better for performance.)

Once you have your minimum penetration vector, you can perform collision response. And the easiest response is to simply separate the two objects by that vector (or separate the one object if the other is static).

Here is a good reference, by the makers of N on how to do this for convex polygons and circles. You should be able to simplify this down for AABBs.

Answer 3

Have you read the N Tutorials? They're a wonderful introduction, complete with little demos, of Separating Axis Theorem based collision detection and simple projection response. (They're actually used in the N game to great effect.) The tutorials cover more than you need, but they're very general (extensible to many other shapes), and start to touch on issues with fast-moving objects and other response techniques.

Even if you do decide to go with something simpler than a SAT implementation, this may give you a lot of good ideas.

(When you're done with that and if you want your mind blown, try looking into some of the presentations from the Game Developers Conference physics tutorial day, including realtimecollisiondetection.net publications, the essentialmath.com tutorial slides, both of those books, and/or other stuff linked from those sites. I'd highly recommend the GDC session itself, too. While we still don't need or particularly want fancy GJK on swept hulls on the handheld game platforms we work with, some of the simpler concepts such as "configuration spaces" and Minkowski sums and differences have greatly influenced how I think about physics and collision detection and how we implement it.)

Answer 4

Another possible approach is, rather than waiting for a collision and then shifting out, check for possible collisions before you move objects and, if there is going to be a collision, move the player only up to the edge of the block.

I.e., contrast how Adventure does collisions with walls: http://www.youtube.com/watch?v=I6-zN_eaRd8 to how most NES games do collisions with walls.