Collision Response

[xander333]

Hey forum,

So I'm working on a mario-style platformer and I'm working on the physics now. Collision DETECTION works well, but now I need to HANDLE the collision properly :)
For example, what do we do if an object collides with another one? Revert the moving object to it's previous state? Not so easily, because when I'm falling at high speed that would make my character stop 10 pixels above the ground. Is there a common solution to this problem that I'm overlooking?

[hamsterman]

That depends on how your detection works, but if it's based on boxes or circles, it should be quite easy to find coordinates for your objects such that they don't overlap and don't have where to fall.

[Disch]

For object/wall collision, a common technique is the "ejection" approach. Where you allow object to move until they are "inside" a wall (colliding with a wall). At which point you stop their movement and "eject" them from the wall by moving them in the reverse direction just enough to where they are no longer in the wall.

The problem with this approach is it allows "tunneling". That is, if the wall is thin, and the object is moving fast, it will be possible for the object to move through the wall without any collision ever being detected.

[xander333]

Well that's my biggest concern, Disch. How should I handle that?
Also, I'm using bounding boxes collision detection.

[Disch]

I haven't found a good way with bounding box collision. Bounding boxes are simple, but they're actually kind of harder to work with for some things (like this). I abandoned them long ago for this and other reasons.

The only way I can think of to prevent tunnelling would be to move the object in "steps" that are no larger than its size.

For example, say you have an object that is 10 pixels wide, and is moving 40 pixels to the right in one step. To prevent tunnelling, you would move him in 10 pixel steps... so move 10, check collision, move 10 move, check again, move 10 more, etc.

Of course that's somewhat impractical, especially if you have tons of small and fast objects (bullets).


A way to optimize this would be to do a broad collision check first. Coming back to the 10 pixel object example... rather than only checking where the object moved to, you would check a larger rect that covers all the space between where the object was and where it moved to. So if he's 10 pixels wide and moving 40 pixels, you would make a new rect that is 50 pixels wide and check that for any wall collisions. If there is one, then you could go back to the "move 10 - check - move 10 - check" approach.

But this approach is poor if the movement is diagonal, because the rect you construct will be overly huge. For example a 10x10 object moving 50 right and 50 down would have a 60x60 broad-check rect that you'd have to cover -- but only a fraction of that space was actually passed through by the object.

What's worse -- moving diagonally opens up some new tunnelling possibilities. Even if the object is moving slow.

Take for instance, this situation:

http://i41.tinypic.com/344d0mg.png

black = walls
object = red

The object can squeeze through a space it shouldn't be able to.

So how do you solve this? In my early attempts, I moved the object along one axis, then another (ie: move it right first, check for collision, then move it down, and check for collision again). But this sucks if the object is moving fast, because then you'll hit walls you shouldn't. (in the same example as that picture, if the object was small enough to make it through that hole, it wouldn't be able to because moving right first would make it hit that wall -- false positive)


Really, I've just found this approach for collision detection inadequate if you want "perfect" collision. If you want to stick with bounding boxes, you'll have to suck it up and accept that it's imperfect and there will be ways to break it. The best you can do is minimize the problems.



I've since moved on to line based collision and never looked back. It's more complicated to understand and set up, but once in place it works great.

[hamsterman]

If walls are tile based, this is not that hard.. (as hard as drawing a line, mostly).

[Duthomhas]

Tunnelling occurs when doing simplistic collision detection.
It only takes very simple math to determine if a line intersects with another (or with a box).

This is often necessary information anyway because, unless your game is very strict about how your sprites move, you will have to take a partial step to "land" on the ground or "bounce" off the wall etc.

Also, how is it that your falling object would collide ten pixels above the ground? Shouldn't it collide with the ground and stop there? Things like Mario games typically have only two responses to collisions anyway: "land" on top of / "bounce" off of, and power reduce / die.

[Disch]

If walls are tile based, this is not that hard.. (as hard as drawing a line, mostly).

Until you get into slopes and diagonal movement.

I've really struggled with all this in the past. Getting fast-motion to work without gross flaws, using bounding boxes alone is actually surprisingly difficult.

[xander333]

I was able to fix it...with a concept I had never heard of, yet is extremely easy to implement and one that I'll be using a lot in the future!
A Fixed Timestep!
http://gamesfromwithin.com/casey-and-the-clearly-deterministic-contraptions

[Disch]

Yeah a fixed timestep is something I do in all my projects as well. But I don't see how it solves this particular problem. You still have the tunnelling issue if objects are moving too fast.