van an nguyen

Collision detection

Collision detection

Introduction

In this chapter, we explore some techniques for detecting collisions between objects. This includes moving and static objects. We will first present three “classic” collision tests, and follow them with brief sketches of more complex algorithms.

Circle – Circle collision test

two circles with distances between the centers drawn

Collision between circles is easy. Imagine there are two circles:

    1. Circle c1 with center (x1,y1) and radius r1;
    2. Circle c2 with center (x2,y2) and radius r2.

Imagine there is a line running between those two center points. The distances from the center points to the edge of each circle is, by definition, equal to their respective radii. So:

    • if the edges of the circles touch, the distance between the centers is r1+r2;
    • any greater distance and the circles don’t touch or collide; whereas
    • any less and they do collide or overlay.

In other words: if the distance between the center points is less than the sum of the radii, then the circles collide.

Let’s implement this as a JavaScript function step-by-step:

  1. function circleCollideNonOptimised(x1, y1, r1, x2, y2, r2) {
  2.   var dx = x1 – x2;
  3.   var dy = y1 – y2;
  4.   var distance = Math.sqrt(dx * dx + dy * dy);
  6.   return (distance < r1 + r2);
  7. }

This could be optimized a little averting the need to compute a square root:

  1. (x2–x1)^2 + (y1–y2)^2 <= (r1+r2)^2

Which yields:

  1. function circleCollide(x1, y1, r1, x2, y2, r2) {
  2. var dx = x1 – x2;
  3. var dy = y1 – y2;
  4. return ((dx * dx + dy * dy) < (r1 + r2)*(r1+r2));
  5. }

This technique is attractive because a “bounding circle” can often be used with graphic objects of other shapes, providing they are not too elongated horizontally or vertically.

Let’s test this idea

Try this example at JSBin: move the monster with the arrow keys and use the mouse to move “the player”: a small circle. Try to make collisions between the monster and the circle you control.

monster and small circle: collision, they are drawn in red and a "collision" message appearsmonster and circle : no collision

This online example uses the game framework (without time-based animation in this one). We just added a “player” (for the moment, a circle that follows the mouse cursor), and a “monster”. We created two JavaScript objects for describing the monster and the player, and these objects both have a boundingCircleRadius property:

  1. // The monster!
  2. var monster = {
  3.   x:80,
  4.   y:80,
  5.   width: 100,
  6.   height : 100,
  7.   speed:1,
  8.   boundingCircleRadius: 70
  9. };
  11. var player = {
  12.   x:0,
  13.   y:0,
  14.   boundingCircleRadius: 20
  15. };

The collision test occurs in the main loop:

  1. var mainLoop = function(time){
  2.   //main function, called each frame
  3.   measureFPS(time);
  5.   // Clear the canvas
  6.   clearCanvas();
  8.   // Draw the monster
  9.   drawMyMonster();
  11.   // Check inputs and move the monster
  12.   updateMonsterPosition();
  14.   updatePlayer();
  16.   checkCollisions();
  18.   // Call the animation loop every 1/60th of second
  19.   requestAnimationFrame(mainLoop);
  20. };
  22. function updatePlayer() {
  23.   // The player is just a circle drawn at the mouse position
  24.   // Just to test circle/circle collision.
  26.   if(inputStates.mousePos) {            // Move the player and draw it as a circle
  27.     player.x = inputStates.mousePos.x;  // when the mouse moves
  28.     player.y = inputStates.mousePos.y;
  29.     ctx.beginPath();
  30.     ctx.arc(player.x, player.y, player.boundingCircleRadius, 0, 2*Math.PI);
  31.     ctx.stroke();
  32.   }
  33. }
  35. function checkCollisions() {
  36.   if(circleCollide(player.x, player.y, player.boundingCircleRadius,
  37.                    monster.x, monster.y, monster.boundingCircleRadius)) {
        // Draw everything in red
  38.     ctx.fillText(“Collision”, 150, 20);
  39.     ctx.strokeStyle = ctx.fillStyle = ‘red’;
  40.   } else {
        // Draw in black
  41.     ctx.fillText(“No collision”, 150, 20);
  42.     ctx.strokeStyle = ctx.fillStyle = ‘black’;
  43.   }
  44. }
  46. function circleCollide(x1, y1, r1, x2, y2, r2) {
  47.    var dx = x1 – x2;
  48.    var dy = y1 – y2;
  49.    return ((dx * dx + dy * dy) < (r1 + r2)*(r1+r2));
  50. }

[Advanced technique] Use several bounding circles for complex shapes, recompute bounding circles when the shape changes over time (animated objects)

This is an advanced technique: you can use a list of bounding circles or better still, a hierarchy of bounding circles in order to reduce the number of tests. The image below of an “arm” can be associated with a hierarchy of bounding circles. First test against the “big one” on the left that contains the whole arm, then if there is a collision, test for the two sub-circles, etc… this recursive algorithm will not be covered in this course, but it’s a classic optimization.

Image of an arm with a hierarchy of bounding circles: one for the whole arm, and two smaller for the forearm and the other part

In 3D, you can use spheres instead of circles:

a 3D object (a lamp) with bounding spheres

The famous game Gran Turismo 4 on the PlayStation 2 uses bounding spheres for detecting collisions between cars:

Grand turismo used collisions between bounding spheres: image of the game (a car on a road track)

Rectangle – rectangle (aligned along X and Y axis) detection test

Let’s look at a a simple illustration:

two pictures: one with non intersected rectangles: the projection of horizontal sides of rectangles to the X axis do not intersect (then rectangles do not intersect), the other with both projections intersect (rectangles intersect)

From this:

To detect a collision between two aligned rectangles, we project the horizontal and vertical axis of the rectangles over the X and Y axis. If both projections overlap, there is a collision!

Try this online demonstration of rectangle – rectangle detection

1 – Only horizontal axis projections overlap: no collision between rectangles

Only horizontal axis overlap: no collision

2 – Only vertical axis projections overlap: no collision between rectangles

Only vertical axis projections overlap: no collision

3 – Horizontal and vertical axis projections overlap: collision detected!

the projections of axis overlap: collision detected

Here is a JavaScript implementation of a rectangle – rectangle (aligned) collision test:

  1. // Collisions between aligned rectangles
  2. function rectsOverlap(x1, y1, w1, h1, x2, y2, w2, h2) {
  3.   
  4.   if ((x1 > (x2 + w2)) || ((x1 + w1) < x2))
  5.     return false; // No horizontal axis projection overlap
  7.   if ((y1 > (y2 + h2)) || ((y1 + h1) < y2))
  8.     return false; // No vertical axis projection overlap
  10.   return true;    // If previous tests failed, then both axis projections
  11.                   // overlap and the rectangles intersect
  12. }

Let’s test this method

Try this example at JSBin: move the monster with the arrow keys and use the mouse to move “the player”: this time a small rectangle. Try to make collisions between the monster and the circle you control. Notice that this time the collision detection is more accurate and can work with elongated shapes.

Player as a square is inside the monster bounding circle but not inside the bounding rectangle, as we use rect rect collision test: no collision detectedSame as previous picture but this time the player square is inside the monster bounding rectangle: collision detected

Here is what we modified (in bold) in the code:

  1. …
  2. // The monster!
  3. var monster = {
  4.   x: 80,
  5.   y: 80,
  6.   width: 100,
  7.   height: 100,
  8.   speed: 1,
  9.   boundingCircleRadius: 70
  10. };
  12. var player = {
  13.   x: 0,
  14.   y: 0,
  15.   boundingCircleRadius: 20
  16. };
  17. …
  19. function updatePlayer() {
  20.   // The player is just a square drawn at the mouse position
  21.   // Just to test rectangle/rectangle collisions.
  23.   if (inputStates.mousePos) {
  24.     player.x = inputStates.mousePos.x;
  25.     player.y = inputStates.mousePos.y;
  27.     // draws a rectangle centered on the mouse position
  28.     // we draw it as a square.
  29.     // We remove size/2 to the x and y position at drawing time in
  30.     // order to recenter the rectangle on the mouse pos (normally
  31.     // the 0, 0 of a rectangle is at its top left corner)
  32.     var size = player.boundingCircleRadius;
  33.     ctx.fillRect(player.x – size / 2, player.y – size / 2, size, size);
  34.   }
  35. }
  37. function checkCollisions() {
  38.   // Bounding rect position and size for the player. We need to translate
  39.   // it to half the player’s size
  40.   var playerSize = player.boundingCircleRadius;
  41.   var playerXBoundingRect = player.x – playerSize / 2;
  42.   var playerYBoundingRect = player.y – playerSize / 2;
  43.   // Same with the monster bounding rect
  44.   var monsterXBoundingRect = monster.x – monster.width / 2;
  45.   var monsterYBoundingRect = monster.y – monster.height / 2;
  47.    if (rectsOverlap(playerXBoundingRect, playerYBoundingRect,
  48.                    playerSize, playerSize,
  49.                    monsterXBoundingRect, monsterYBoundingRect,
  50.                    monster.width, monster.height)) {
  51.      ctx.fillText(“Collision”, 150, 20);
  52.      ctx.strokeStyle = ctx.fillStyle = ‘red’;
  53.    } else {
  54.      ctx.fillText(“No collision”, 150, 20);
  55.      ctx.strokeStyle = ctx.fillStyle = ‘black’;
  56.   }
  57. }
  59. // Collisions between aligned rectangles
  60. function rectsOverlap(x1, y1, w1, h1, x2, y2, w2, h2) {
  62.   if ((x1 > (x2 + w2)) || ((x1 + w1) < x2))
  63.      return false; // No horizontal axis projection overlap
  65.   if ((y1 > (y2 + h2)) || ((y1 + h1) < y2))
  66.      return false; // No vertical axis projection overlap
  68.   return true; // If previous tests failed, then both axis projections
  69.                // overlap and the rectangles intersect
  70. }

Many real games use aligned rectangle collision tests

Testing “circle-circle” or “rectangle-rectangle collisions is cheap in terms of computation. “Rectangle-rectangle” collisions are used in many 2D games, such as Dodonpachi (one of the most famous and enjoyable shoot’em’ups ever made – you can play it using the MAME arcade game emulator):

screenshot of dodonpachi

You could also try the free Genetos shoot’em up game (Windows only) that retraces the history of the genre over its different levels (download here). Press the G key to see the bounding rectangles used for collision test. Here is a screenshot:

genetos screenshot

These games run at 60 fps and can have hundreds of bullets moving at the same time. Collisions have to be tested: did the player’s bullets hit an enemy, AND did an enemy bullet (for one of the many enemies) hit the player? These examples demonstrate the efficiency of such collision test techniques.

Other collision tests

In this section we will only give sketches and examples of more sophisticated collision tests. For further explanation, please follow the links provided.

Aligned rectangle-circle

There are only two cases when a circle intersects with a rectangle:

    1. Either the circle’s center lies inside the rectangle, or
    2. One of the edges of the rectangle intersects the circle.

We propose this function (implemented after reading this Thread at StackOverflow):

  1. // Collisions between rectangle and circle
  2. function circRectsOverlap(x0, y0, w0, h0, cx, cy, r) {
  3.    var testX=cx;
  4.    var testY=cy;
  6.    if (testX < x0) testX=x0;
  7.    if (testX > (x0+w0)) testX=(x0+w0);
  8.    if (testY < y0) testY=y0;
  9.    if (testY > (y0+h0)) testY=(y0+h0);
  11.    return (((cx–testX)*(cx–testX)+(cy–testY)*(cy–testY))< r*r);
  12. }

Try this function in this example on JSBin.

Circle and rectangle not in collisioncircle collides a rectangle

[ADVANCED] Collision between balls (pool like)

ball ball collision example

The principle behind collision resolution for pool balls is as follows. You have a situation where two balls are colliding, and you know their velocities (step 1 in the diagram below). You separate out each ball’s velocity (the solid blue and green arrows in step 1, below) into two perpendicular components: the “normal” component heading towards the other ball (the dotted blue and green arrows in step 2) and the “tangential” component that is perpendicular to the other ball (the dashed blue and green arrows in step 2). We use “normal” for the first component as its direction is along the line that links the centers of the balls, and this line is perpendicular to the collision plane (the plane that is tangent to the two balls at collision point).

The solution for computing the resulting velocities is to swap the components between the two balls (as we move from step 2 to step 3), then finally recombine the velocities for each ball to achieve the result (step 4):

diagram with two balls, velocities, tengeantial and normal planes

The above picture has been borrowed from this interesting article about how to implement in C# pool like collision detection.

Of course, we will only compute these steps if the balls collide, and for that test we will have used the basic circle collision test outlined earlier.

To illustrate the algorithm, here is an example at JSBin that displays the different vectors in real time, with only two balls. The maths for the collision test have also been expanded in the source code to make computations clearer. Note that this is not for beginners: advanced maths and physics are involved!

To go further… video game physics!

For the ones who are not afraid by some maths and physics and would like to learn how to do collision detection in a more realistic way (using physics modeling), we recommend this tutorial, that is the first of a three-part series  about  video game physics.

Leave a comment