What collision handling code to use

[Tasnu Arakun]

hi,

i'd like to discuss which collision detection i should adopt for a 2d arcade-style game i'm writing at the moment. collisions come in two distinct types: those whose effect is always the same (objects getting destroyed) and those whose effect vary depending on the objects location, speed and direction. the latter in this case is deciding upon a new direction vector for a bouncing ball (one affected by gravity).

the game area consists of 16 * 16 tiles - some are empty, others hold "bricks" of different kinds. now "balls" are to fall from above, collide and eventually come to a rest upon these bricks. the balls all have different behaviours which, among other things, affect their movement. thus i need to check what side of the brick the ball has hit (and the direction of the ball).

both balls and bricks have a rectangle bounding box (although that can easily change). what my first collision code did was essentially to check the location of the ball compared to the brick. e.g. if the ball struck the brick from above and the direction is negative (downwards), i have a collision and have simply to multiply the y-value by -0.9 (or whatever). each ball is allowed to collide only once during each engine tick. also a collision turns of some of the special behaviour (like always moving in the direction of the player) during that engine tick.

int collides( NSRect rect1, NSRect rect2 ) {
if ( !NSIntersectsRect( rect1, rect2 ) ) return NONE;

if ( NSMinY( rect1 ) < NSMinY( rect2 ) && NSMaxY( rect1 ) < NSMaxY( rect2 ) ) return NORTH;
if ( NSMinX( rect1 ) < NSMinX( rect2 ) && NSMaxX( rect1 ) < NSMaxX( rect2 ) ) return WEST;
if ( NSMinY( rect1 ) > NSMinY( rect2 ) && NSMaxY( rect1 ) > NSMaxY( rect2 ) ) return SOUTH;
if ( NSMinX( rect1 ) > NSMinX( rect2 ) && NSMaxX( rect1 ) > NSMaxX( rect2 ) ) return EAST;
return WITHIN;
}

to keep things simple i only took into account four sides. a ball hitting a corner was taken care of by giving on side (e.g. NORTH) higher priority. this, however, has the side effect of balls sometime passing through the bricks if hitting them from the side. the solution i could come up with was adding 4 more sides, i.e. the corners. hitting a corner would be interpreted as hitting a hitting a slanting side with an angle of 45°. after discussing the topic with a friend he recomended the same thing and volunteered to write the code.

int collides( NSRect rect1, NSRect rect2 ) {
if ( !NSIntersectsRect( rect1, rect2 ) ) return NONE;

int side = WITHIN;
if ( NSMinY( rect1 ) < NSMinY( rect2 ) && NSMaxY( rect1 ) < NSMaxY( rect2 ) ) {
side = NORTH;
}
if ( NSMinY( rect1 ) > NSMinY( rect2 ) && NSMaxY( rect1 ) > NSMaxY( rect2 ) ) {
side = SOUTH;
}
if ( NSMinX( rect1 ) > NSMinX( rect2 ) && NSMaxX( rect1 ) > NSMaxX( rect2 ) ) {
if ( side == NORTH ) side = NORTHEAST;
if ( side == SOUTH ) side = SOUTHEAST;
if ( side == WITHIN ) side = EAST;
}
if ( NSMinX( rect1 ) < NSMinX( rect2 ) && NSMaxX( rect1 ) < NSMaxX( rect2 ) ) {
if ( side == NORTH ) side = NORTHWEST;
if ( side == SOUTH ) side = SOUTHWEST;
if ( side == WITHIN ) side = WEST;
}
return side;
}

this didn't make things much better - possibly worse. balls would get stuck at corners, pass right through or get caugh in strange circular motions.

the last idea that we never got around to test was dividing the ball into 4 separate squares and test collision for each of them. then actions could be taken depending on which of these squares had collided. e.g. if the bottom two reported a hit we would know we had hit something straight on from above, but if only one reported a hit we would have hit a corner. the different squares wouldn't even have to hit the same object - and thus i could allow for more accuracy. i have no idea however if this might introduce any new problems.

i'll include the "collisionFrom:side withTypeOfGameObject:t" method below. please tell if you need any more information - code, screenshots or a somewhat playable demo... ;)

[Tasnu Arakun]

...and here comes the method from my Ball-class:

- ( void ) collisionFrom:( int )side withTypeOfGameObject:( int )t {
if ( t == BRICK ) {
switch ( side ) {
case EAST:
if ( velocity.x < 0.0 ) [ self reboundX ];
break;
case NORTH:
if ( velocity.y > 0.0 ) [ self reboundY ];
break;
case WEST:
if ( velocity.x > 0.0 ) [ self reboundX ];
break;
case SOUTH:
if ( velocity.y < 0.0 ) [ self reboundY ];
break;
case NORTHEAST:
if ( velocity.x - velocity.y > 0.0 ) {
[ self swap ]; // swaps the values of x and y
}
break;
case NORTHWEST:
if ( velocity.x + velocity.y > 0.0 ) {
[ self swap ];
[ self reboundX ];
[ self reboundY ];
}
break;
case SOUTHEAST:
if ( velocity.x + velocity.y < 0.0 ) {
[ self swap ];
[ self reboundX ];
[ self reboundY ];
}
break;
case SOUTHWEST:
if ( velocity.y - velocity.x > 0.0 ) {
[ self swap ];
}
break;
case WITHIN:
[ self reboundX ];
[ self reboundY ];
break;
}
collision = YES;
}

if ( t == SHOT || t == SHIP ) [ self destroy ];
}

[phydeaux]

Unfortunately this isn't a direct answer to your question, but I find that when you're trying to do these 2d box collisions, the easiest solution is to do the collision in one axis (say the x direction) and then the other. So for example, move your x velocity, and check for a collision (that is, if the bounding boxes collide), if you have one, move to the edge of the object you're colliding with and out the penetrating x distance. Now, do the same thing in the y axis. The one problem here is that you cannot bounce off a corner in both velocity directions with this method, since you will move in one direction, miss the corner, then moving in the other direction you will bounce off of it.

Looking at your code, I think it might help you to take your velocity into account- for example if you are going in the positive x direction, you could only bounce off the east side of an object (unless you are doing something much more complicated, but even then I think this may work provided you move a small enough amount each frame.)

[Tasnu Arakun]

Looking at your code, I think it might help you to take your velocity into account- for example if you are going in the positive x direction, you could only bounce off the east side of an object (unless you are doing something much more complicated, but even then I think this may work provided you move a small enough amount each frame.)

i'm updating locations every 10 ms so it should be quite accurate.
since i want to keep my collision detection function as simple as possible and don't want it prodding inside my game objects, they themselves are responsible for ignoring a collision if it happens to be moving away from the source of impact (see my second post).
i'll take a look at the idea of splitting the collision into x and y.

by the way, would collisions between a circle and a rectangle be harder to handle?

[phydeaux]

Circle vs rectangle is kind of a pain in the butt; i'd have to look up the formula to make sure I was doing it right.

You could pass velocity to your collision detection routine, and then it'd still be fairly modular; that might be easier for you.

[FCCovett]

I am working on a bricks game that is almost done. This is what I am doing:

1. I treat the ball as a sphere and check if the sphere touched the sides of the tiles/bricks.
2. I check for all obstacles in all 8 surrounding tiles (north, south, east, west, NE, NW, SW, SE). N, S, E, W have priority. If the ball didn't bounce off of any of these, then I check for the "diagonal" neighbors.
3. I get the cosine of angle between two vectors to decide if the ball is moving towards or away from the side of a tile: the distance between the ball and the center of that tile, and the ball's velocity vector. For instance, if the cosine is negative, I don't check the ball against the sides of that tile, because the ball is moving away from it.
4. When the ball intersects a line segment that defines one of the sides of the tile/brick, then I invert the appropriate velocity component, Vx or Vy, depending on the segment being vertical or horizontal.
5. To avoid problems with low frame rates, you may want to cap and force your step-time, so the ball doesn't move too much and passes right through a brick because the collision detection method is running at 4 Hz, for instance. The game will seem to run in "slow-motion" when the frame rate drops too much.

Hope that helped a bit.