Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am developing a small 2D game engine. The characters have a paint method which currently does the following:

  1. Calculate the new position of the character as per its speed, etc.
  2. Update the collision grid cell **
  3. Draw the character at the new position

** I have created a collision grid to reduce the number of intersection checks

Now the basic algorithm which I have thought for detecting collision is:

For Each Character
    Check intersection with characters in surrounding 8 cells

I can simply place this code in the paint method. But here is the problem I anticipate.

Suppose two characters A and B lie in adjacent cells in the collision grid. Now as per the above algorithm in the iteration of character A it will detect that it has collided with B. In the iteration for character B it will detect that it has collided with A.

But I have an idea that when A detects that it has collided with B, it should inform B that it has collided with A. This would save lot of comparisons when there are more than 2 actors colliding. But I am not sure how to handle this. I think instead of every character checking for its collision, I should check for the collision inside the game loop.

Would this approach be correct? How have you handled this kind of problem? I thought of the collision grid thing myself. Are there any alternatives to collision grid logic?

share|improve this question
    
I am sorry to nitpick, but in a specialized 2D physics library. Game physics is usually very approximative, so any solution which does not make game non-playable is fine, but if You want to solve it correctly just use specialized physics like Box2D ... :-D –  user712092 Jul 4 '11 at 15:32
add comment

2 Answers

up vote 11 down vote accepted

The usual approach for collision detection is to not have either A or B detect collisions on their own.

Instead, you first move all objects, then have a separate collision system look for collisions between all pairs of objects, telling every object about the things that it has collided with, and then finally render all objects.

So in essence, instead of doing "move, check for collisions, draw" inside your Paint() function, you split up "move" and "draw" into separate functions which you call separately (first "move" for every object, then "draw" for every object). And between those, check for collisions.

Advanced note: If any of your objects move themselves in reaction to detected collisions, then you may need to repeat the "look for collisions between all pairs of objects" step, in case an object's collision-response causes another collision.

share|improve this answer
    
This is the proper way of doing things. Let the objects handle their responsibilities and the collision system should decide what happens when they meet an obstacle. You can also have a collision rectangle/cylinder (2d/3d) around your characters as a sort of early trigger. –  James Poulson Jun 2 '11 at 10:29
    
Great! Regarding the advanced note, shouldn't the collisions be rechecked only for objects which move themselves in reaction to the collision and the objects they collide with in the new position? There will be a chain of checks but it will avoid checking collision for all the objects. –  Cracker Jun 2 '11 at 12:06
    
How to handle this - gamedev.stackexchange.com/questions/13076/… –  Cracker Jun 2 '11 at 22:06
add comment

I run a loop for all my characters in the game loop like you say.

The way I do it is with a state on each of my characters, so if A and B collide while A is checking collision A and B are set to hit. at the beginning of B's loop it checks to see if it is already hit, if so id doesn't run the loop.

I put the affect code in the loop so any action that should be taken on B has happened in A's loop so there should be no reason for B to check as this would mess up the outcome of the collision, this may be different for you though.

share|improve this answer
    
But in this case when A detects intersection with B, B.hit will be set to true and so B won't check for ANY intersection. But if another character C intersects with B, B won't detect it? –  Cracker Jun 1 '11 at 16:29
    
Sorry, got it. Since A does not intersect with C, C.hit will still be false. B won't check for collisions. But C will check and will pass the information to B that there is a collision between B and C. Cool! –  Cracker Jun 1 '11 at 16:31
    
But I guess if all A, B and C intersect with each other there would be a problem. A will set B.hit and C.hit to true. B and C will know that they have collided with A. But since their hit property is true they won't check for collision. The collision between B and C will go unnoticed. –  Cracker Jun 1 '11 at 16:34
    
You can sneak in a similar method by putting every viable collision object in a collection of some sort, then only checking collision with things that come after the object in the collection. IE: A checks vs B, C, D; B checks vs C, D; C checks vs D. Each one behind doesn't need to be checked as it was already checked from the one behind's turn. Not quite as fast as skipping the element's collision entirely, but useful nonetheless. –  Lunin Jun 1 '11 at 17:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.