Collision organization problems

Question

I just started playing around with c++ and some SFML. I'm going to create a 2D game with top view to test my ability and I came across a very big problem: collision detection and physics. So I see at least 4 scenarios:

1. An object collides with a solid object (that cannot move) so the first object must stop. (Example: a player hitting a wall)
2. An object collides with a movable object (that is not alive so does not move unless pushed) so the first object push that object. (Example: a player that moves a box)
3. Two object (that has proper move) moves and collide frontally so they push each other with the same force so they must stay still.
4. Two object (that has proper move) and one push the other which is going in the same direction: so the second object must move faster or must have more power. This implies also that if more object push themself one back to the other we have that the first gains a lot of push power. (Example: a crowd that push to to get inside a door and that door with x pushing power gets destroyed)

The collision problem is not a problem at all: you just check the player x and y and width and height against the object that is colliding with. The problem is instead: who is supposed to take care of the collision? Let's say that it's the movable object that is pushing that has to take care of it: (1 scenario), it's ok, the one that pushes just reset its x and y to where it was before colliding; (2 scenario) here things start to get a bit tricky: the pushing object must take care also of the object that gets pushed so it has to move that object too; (3 scenario) here we have two pushing object, which one should deal with the collision? (4 scenario) how do we store the pushing power of the object?

Is there general guidelines for that, considering also that the player is not the only mob and that there might be computer guided mobs?

Thanks.

Answer 1

Beside using an existing Physics Engine that can take care of this, there is one -- I guess, pretty popular -- technique for collision detection between moving and solid objects: Binary Space Partitioning.

I have only implement it yet for collision between the player (moving object) and solid map objects, where the idea works as the following. The map is sorted into a tree structure.

When loading the map, you separate the room of the map in the middle (middle does not necessarily be the room separated into two equal halfs, but you can use also the median of all objects in the map).

Now you check for every object, in which half of the room it is, and move it to the corresponding children node in the tree (one for each half). If it lies on both side, leave it in the current node.

Now you can split the children nodes, and so on. You can use a limit, of objects, that must minimum reside into one node. If there are less objects in a node, you won't split it up anymore.

If you have done this, you have a nice BSP-Tree for your map and your solid objects. If you want to check for collision with your player, you just take the position of your player and check it against collision with all the objects, that are in the root node of your tree. Then you look, in which half of the room your player is, and check his/her position against all the objects in that children node. And so on...

With that you reduced the complexity of the collision detection a lot compared to bruteforcing against all other map objects. Bruteforcing has O(n) complexity (not regarding your actual collision checks) and binary space partitioning use an average of O(log(n)), therefor needs the precalculation.

The same algorithm also works with moving objects, but you will need to move them in the tree, when they are moved on the map.

If you search literature about binary space partitioning, you will find a lot of improvements, how to make it even more efficient.

Of course you will find a lot of implementations of that already in physics engines, but for learning reasons, this is a nice thing to implement :)

Answer 2

Instead of having the objects responding to the collision, create a physics system to take care of that. The system should have a pointer to every 'physical' object and be able to know which objects are static or dynamic, which is heavier or lighter, their speed, etc. The system takes care of all collision resolving.

On another note, you could also try a physics library like Box2D. Unless your goal is to create a physics engine, it's a lot easier/faster to use a library.

Answer 3

If you want to make a game and are not that interested in getting into the nitty-gritty of physics yourself, I'd advise simply using a physics engine, such as Box2D.

If you do want to get into the nitty-gritty of physics yourself, well, that is a huge topic that can't really be explained in a couple-hundred-word answer here. I'd recommend picking up a book, such as Dave Eberly's Game Physics. This topic will require some serious study before you'll be able to do anything interesting with it, though. Most books on the game physics simulation are written about 3D physics, but most of the same techniques apply to 2D as well (the main difference is that rotation is much simpler in 2D than in 3D).