20
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$
    – user712092
    Jul 4, 2011 at 15:32

2 Answers 2

15
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – James P.
    Jun 2, 2011 at 10:29
  • \$\begingroup\$ 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. \$\endgroup\$
    – Cracker
    Jun 2, 2011 at 12:06
  • \$\begingroup\$ How to handle this - gamedev.stackexchange.com/questions/13076/… \$\endgroup\$
    – Cracker
    Jun 2, 2011 at 22:06
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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? \$\endgroup\$
    – Cracker
    Jun 1, 2011 at 16:29
  • \$\begingroup\$ 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! \$\endgroup\$
    – Cracker
    Jun 1, 2011 at 16:31
  • \$\begingroup\$ 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. \$\endgroup\$
    – Cracker
    Jun 1, 2011 at 16:34
  • \$\begingroup\$ 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. \$\endgroup\$
    – Lunin
    Jun 1, 2011 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .