When to detect and respond to collisions?

Question

I've usually implemented collision detection like this in the past:

1. Move entity
2. Check if it collides with anything
3. Resolve the collision by moving it back

That's also the approach employed by most tutorials on the topic I've seen, so it seems popular. But isn't the following cleaner?

1. Calculate entity's velocity based on its acceleration
2. Check if it would collide with anything
3. Resolve the collision by adjusting its velocity
4. Move entity based on its velocity

The former approach has always been buggy for me, with objects getting stuck in walls or sometimes moving right through them.

One issue I see with the latter approach is with the time step. All of my entities have an void update(int ticks) method which updates their position. Now, I'd have to calculate the position twice: Once to anticipate a collision and once to actually move the object. Also, can I accurately resolve the collision by just updating the velocity?

Answer 1

There are many ways to handle collisions in your game.

One possible solution is to revert to the position before the collision happened, like the first method you mentioned. I would advise against this solution. It gives a weird feeling when you are playing and prevents you from "sliding across a wall". I used to handle collisions like that. I wish I hadn't.

Instead, I would recommend doing it in a more "realistic" way. Depending on your game environment, you could use a physics engine if your game uses a lot of physics. I think this may be the most complete way to go. There are many engines out there depending on your programming language and framework. Find one that fits your needs and is well documented.

However, you can program it yourself if your game is simple enough and you want to do it yourself out of curiosity. If you are making a game where your environment is made up of squares (a grid, such as a platformer game or a top-down tower defense, etc.), then you can do it yourself. When a collision happens, push the entity across the shallow axis (in order to make the collision response less apparent). This way, you'll be able to move while walking into a wall, and you'll simply slide against it. It should feel natural. You can take a look at this article for a tutorial about it. You can find a lot of other resources online to do this as well.

The general algorithm for this method is the following:

1. Find how far the entity is pushed inside an object of the environment on each axis (by comparing their rectangles).
2. Find which is the shallow axis (abs(x) < abs(y) or the other way around).
3. Push against this axis to undo the collision
4. Adjust velocities if needed (this depends on your game, you could apply a bounce effect in a physics-based game, stop a jump in a platformer when you jump under a wall)

I wish you the best of luck to find a solution that fits your needs.

Happy coding!

Answer 2

The topic is too broad to benefit from a single answer on this site.. but some better things to do can be covered nonetheless:

• investigate continuous collision detection/simulation strategies
• use ray casts and/or shape casts to detect collisions AND the TOI (time-of-impact)
• once the time of impact is computed, it gives you the time the object will travel until it will collide with the first object in the scene. You can use this estimate to advance your simulation until you have a hit. From that hit you must compute a response and modify your velocity accordingly (apply impulses, reaction forces, friction or whatever your dynamics engine can add). After this impact, you are reduced to using whatever simulation time is left from the engine time-step. Use that remaining time to advance your simulation with the updated dynamics.

This strategy is simple and intuitive, but the details are math/physics heavy. Perhaps some simple introduction can be found here: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

UPDATE: Richard Tonge of Nvidia PhysX has explained their solver implementation for collision handling (in parallel!) for multiple objects. It does answer and explains a lot of issues: http://www.essentialmath.com/GDC2012/Richard_Tonge_solvingRigidBodyContacts.pdf