Hello, I have some questions to ask about collision handling. Collision detection articles everywhere, but handling articles are so rare.
What is the most used/useful order of operation for collision handling? Currently, I handle the collision as soon as it is found, while doing the standard O(n[sup]2[/sup]) collision detection routine:
#pseudocode
for obj1 in obj_lst:
for obj2 in obj_lst:
if obj1.collide(obj2):
collision_handle(obj1, obj2)
Handling collision as soon as detected has been pretty good, but the objects near the beginning of the list always get handled first, and this can affect the objects near the end of the list. How do 2d rpgs do it in practice? I vaguely remember reading something about adding the colliding pairs to a collision list, and use something called a "contact solver" to iterate through the list several times to handle them all. Why several times? Can someone elaborate on this?
Unless you're having an awful lot of entities/objects that need to check collision with each other, you will not really notice anything when iterating through your lists and compare them against each other, or at least.. You shouldn't.
When it comes to having a lot of objects in your screen, the easiest way to resolve it is to simply split your screen (or scene, depending on how you manage everything) into a grid and only check collision with what is within that specific space in the grid, if there is anything in it at all.
Not sure what a contact solver is or what it is specifically used for, so I can't really help you with that. Perhaps someone else can shed some light on it
Picture a pool/billards type game. One of your balls has hit another, and there's a group of balls there. If you simply iterate through the objects and check the collisions once, you will probably end up with one or more balls being inside another because, one of the later balls you check has collision, and you have to move it out of the ball that hit it; except, doing this, you've collided with a ball that's already been checked. This adds much more complexity to possible collisoins
While I'm not 100% sure if that's what a contact solver does (my guess is it's more to do with where one polygon/circle has collided with another exactly), there are many complexities to true collision detection. IMO, you probably don't have to go into that much detail for simple games. If you are concerned with this, a simpler solution could be:
Once an object has collision, and you've adjusted it's position, you could check all other objects near it to see if you've caused another indirect collision.
My advice; it's great to understand how collisions are detected and how they are handled, but other people have spent a lot of time writing code that already handles this for you in 2d physics libraries. Once you learn how to use a 2d physics library (chipmunk-physics is my favorite, but Box2d is a popular one too), writing games becomes much easier. You can check my Old Blog (linked in my signature) for steps I took to make a game using a chipmunk-physics.
Thanks guys, but I am not really worrying about the performance right now. I am more confused about collision detection and handling's place in the update function. Does one update everything first, then iterate again to check for all collisions, then iterate yet again correct all collisions? or does one (me) update one object, check collision for that object, and handle collision for that object all in one iteration?
My advice; it's great to understand how collisions are detected and how they are handled, but other people have spent a lot of time writing code that already handles this for you in 2d physics libraries. Once you learn how to use a 2d physics library (chipmunk-physics is my favorite, but Box2d is a popular one too), writing games becomes much easier. You can check my Old Blog (linked in my signature) for steps I took to make a game using a chipmunk-physics.
Yes, I am trying to implement it first time around, as much as I can. Chipmunks sounds like the one I would use; a quick search shows it uses c99, which is what I am using too.
Thanks guys, but I am not really worrying about the performance right now. I am more confused about collision detection and handling's place in the update function. Does one update everything first, then iterate again to check for all collisions, then iterate yet again correct all collisions? or does one (me) update one object, check collision for that object, and handle collision for that object all in one iteration?
Well, there's multiple ways you can do it, and I'm not sure one is better than another. You can handle the collisions as you iterate through the objects while checking for collisions. That is what I would suggest you do to begin with. Or, you can mark the objects (as pairs) that have collided during an iteration, and handle them after. It really depends on your game.
The physics library gives you full control; you can get notified the instance your object collides with another (ie, before the physics engine performs the reactions of the object colliding called pre-solver), you can get notified after the physics engine has perform the physical updates (ie, handled the collision and response of the objects colliding), and you can also get notified when your objects STOP colliding with another. If you want to do something like that, you can make a generic interface that notifies your object of collisions, like this:
public TPlayer : public TPhysicalObject, public ICollisionHandler
{
// define your player
// put these in public section
virtual void HandleCollision(TPhysicalObject objectHit);
virtual void HandleSeparate(TPhysicalObject objectHit);
};
I would suggest to KISS until you feel more comfortable with handling collisions.
The physics library gives you full control; you can get notified the instance your object collides with another (ie, before the physics engine performs the reactions of the object colliding called pre-solver), you can get notified after the physics engine has perform the physical updates (ie, handled the collision and response of the objects colliding), and you can also get notified when your objects STOP colliding with another. If you want to do something like that, you can make a generic interface that notifies your object of collisions, like this:
That's pretty flexible. Does "notify" imply some sort of message passing or event system going on there? Never thought about using that in physics.
I would suggest to KISS until you feel more comfortable with handling collisions.
I try... but there are so many interesting things out there, sometimes I just can't help it.
On the solver: the box2d doc talks about a constraint solver, and it seems to be what I was looking for. It's a function that iterates through the colliding pairs multiple times to fix collisions, so your billiard example pretty much describes that exactly. I also saw it mentioned in speculative contacts, so it seems to be a common practice.
When handling collisons, calculate colliding objects and their time of impact sort by time of impact, process the first impact by advancing the simulation to that point and solving the collision.
You then iterate until there are no collisions or you run out of time in the timestep (or you hit a max number of iterations in which case bad things might happen).
For example, in a game of pool, if your time step is 2 and two balls collide at time 1.2, then the balls positions are upated to where they would be at that intermediate time, the two balls that collide would update their velocities. That collision results in one of the balls hitting a third ball at time 1.75, using the new velocities the balls would be updated to time 1.75, assuming no more collisions occur the balls would be updated the remaining 0.25 and you'd be done.
By only updating the simulation to the time of impact and updating velocities then iterating you get around the problem of fixing penetrations which then push objects into other objects.
OP asked about "collision handling". Everyone seems to be replying with the assumption that he meant "generic physics solving".
To me, the most puzzling thing about collision handling is how to gracefully organize the collision-handling game logic in such a way that you don't have to repeat yourself all over the place.
Take SMB3 -era Mario, for instance. There are a ton of different enemies, different tiles, different powerups in the game. Enemies may have alternate states like "stunned" which change what it means to collide with them. Mario himself has a zillion different states, like small, big, invulnerable, stealthed, etc. Finally, the direction of the collision is often significant in determining the result. A big-Mario-on-breakable-tile collision will only break the tile if Mario hits from under the tile. A normal-Mario-on-normal-Goomba collision kills the Goomba if Mario hits from above, and kills Mario otherwise.
How would you guys deal with this?
The impossibly naive way would be to have a class for each enemy type, a class for Mario's every possible form, and a collision handler function for each class combination. That would result in M*E handler functions - hundreds of functions - just for Mario-enemy collisions. Most lines of code in those functions would repeat hundreds of times in the project. Also, every time you wanted to add any new object that is only slightly different than an existing one, you'd need a new function for every single object that may collide with the new one.
I once wrote a crude Mario clone prototype in C++ for a school project. My collision logic used Player, Tile, Enemy etc. base classes, one for every major category of stuff that is kept in its own container and may collide with another category of stuff. From them I derived concrete classes such as Goomba : public Enemy. Then I did multiple dispatch. One of every two colliding categories would have a pure virtual collide function (for instance, Tile::collide(Enemy &e)) which my collision checker would use to trigger the collision. The other colliding category would have a counterpart function, in this case Enemy::collideBack(Tile &t), which the implementation of collide would call after possibly executing some logic internal to the tile. Both functions could be overloaded for specific Tile/Enemy subclass types as needed. In practice, Tile subclasses such as BreakableTile would implement collide simply by calling e.collideBack(&this), and the bulk of the handling of the collision happened in collideBack. This enabled writing default behavior for Goomba collisions with any kind of Tile, and only having to manually define exceptions if Goomba actually acts differently with different Tiles. I wasn't totally satisfied with this setup; the asymmetry is kind of ugly and the functionality sharing only operates inasmuch the game objects which want to share are on the exact same branch in the rigid behavior hierarchy.
I handled game object destruction by marking them dead. They continued interacting with the other objects for the remainder of the logic iteration. I think that's likely to be harmless in almost all interactions, but in a few cases it could be a disaster and has to be checked for. For instance, players might be able to dupe items by picking up the item on the exact same tick as another player.
When handling collisons, calculate colliding objects and their time of impact sort by time of impact, process the first impact by advancing the simulation to that point and solving the collision.
You then iterate until there are no collisions or you run out of time in the timestep (or you hit a max number of iterations in which case bad things might happen).
For example, in a game of pool, if your time step is 2 and two balls collide at time 1.2, then the balls positions are upated to where they would be at that intermediate time, the two balls that collide would update their velocities. That collision results in one of the balls hitting a third ball at time 1.75, using the new velocities the balls would be updated to time 1.75, assuming no more collisions occur the balls would be updated the remaining 0.25 and you'd be done.
By only updating the simulation to the time of impact and updating velocities then iterating you get around the problem of fixing penetrations which then push objects into other objects.
Thanks for the explanation. I have never used time step before, is it a cool trick or best practices? Is it fine to update non physics and physics by a differing number of times per frame like that? I've never paid much attention to time before. Currently I just have a loop that calls game update once per frame, and game update would do logic stuff, and move the objects by a little bit. Then game draw is called, and a timer function will wait for some time to make the game run at 60fps.
OP asked about "collision handling". Everyone seems to be replying with the assumption that he meant "generic physics solving".
My fault, I noticed my questions are not that clear, swaying from collision handling to oder of operations, to definition of constraint solver, stc...
To me, the most puzzling thing about collision handling is how to gracefully organize the collision-handling game logic in such a way that you don't have to repeat yourself all over the place.
Take SMB3 -era Mario, for instance. There are a ton of different enemies, different tiles, different powerups in the game. Enemies may have alternate states like "stunned" which change what it means to collide with them. Mario himself has a zillion different states, like small, big, invulnerable, stealthed, etc. Finally, the direction of the collision is often significant in determining the result. A big-Mario-on-breakable-tile collision will only break the tile if Mario hits from under the tile. A normal-Mario-on-normal-Goomba collision kills the Goomba if Mario hits from above, and kills Mario otherwise.
How would you guys deal with this?
The impossibly naive way would be to have a class for each enemy type, a class for Mario's every possible form, and a collision handler function for each class combination. That would result in M*E handler functions - hundreds of functions - just for Mario-enemy collisions. Most lines of code in those functions would repeat hundreds of times in the project. Also, every time you wanted to add any new object that is only slightly different than an existing one, you'd need a new function for every single object that may collide with the new one.
Nice of you to share your experiences. The way I handle it is to have a single generic game object class, and fill it with details instead of making a sperate class for every little thing. Inheritance is cool, but I won't use it just for the sake of using it. Another OOP solution is the composite pattern, I think thats where you have an object that is combination of multiple objects. But now I am going offtopic ;o
