Might this alternate circle-circle collision test help performance?

Question

Preface: I’m no gaming pro…I code business apps, but I’m experimenting with game coding this Christmas. :-)

I want to detect collisions between 200+ circles of different sizes which are moving at different speeds.

I know I can determine if any 2 circles are actually colliding like this:

// are circle0 & circle1 colliding?
var dx= circle1.x-circle0.x;
var dy= circle1.y-circle0.y;
var rr= circle0.radius+circle1.radius;
var isColliding = (dx*dx + dy*dy) < rr*rr;

In reading about collision testing here on GameDev I understand that performance can be improved by reducing the count of circle-pairs that need to be tested during an animation cycle.

So I’m thinking I can skip the above collision test for any circle-pair that is too far apart to possibly be colliding.

To calculate how many times I can safely skip the collision test I can calculate the separation distance between a circle-pair and divide that distance by the combined speeds of the circles.

// no collision is possible for `var safe` animation cycles
var safe = Math.sqrt(dx*dx+dy*dy)/(circle0.speed+circle1.speed);

Question#1: In general, is it worthwhile to do the “expensive” Math.sqrt once to gain skipping multiple “cheap” arithmetic isColliding tests?

Question#2: What collision testing pattern would you gaming pro’s use to detect collisions between different sized circles moving at different speeds?

BTW, I ask the first question out of inexperience, so I understand the answer may well be: You just have to compare both methods yourself and see which works best for you. 

Answer 1

Math.sqrt() is indeed very expensive but you can always use fast sqrt instead. I generally would avoid this altogether.

Spatial indexing works for circles of all sizes. Start with a simple grid which has been proven to be the most efficient anyhow in many tests. Use a 2d array of circle lists to conceptually divide the space to 2d-grid of squares.

The grid should be spacious enough so that each circle can be in four squares at the same time at most.

Each frame, you can:

1. Check the grid squares for correctness (circles are actually in their respective squares).
2. Update with changes if necessary (i.e. remove a circle from where it no longer is, add it to where it actually is).
3. Check for collisions only with circles that occupy the same grid squares.
4. Check first if collision is possible across both x & y, i.e. check that distance in x & y is less than r1 + r2 on both axes (addition is simpler than multiplication).
5. Do the actual check.

Remember to avoid checking the same pair twice. There are several ways to do that, you don't have to, this will still speed up things considerably.

Here is the pseudo code for the technique I use:

class Grid {
    const int SQUARE_SIZE = 100;
    array<array<int>> grid; //An array that represents a 2d grid with circles ids
                            //The squares are ordered by rows and then by columns
    /* lets say the grid is 8 x 8 and has 64 squares inside */
    const int SQUARE_COUNT_X = 8;
    const int SQUARE_COUNT_Y = 8;
}

The grid class is used to store data about circle positions.

class Circle {
    static int counter;

    int cx; //center x position
    int cy; //center y position
    int cr  //radius

    int id; // A static counter assigns a unique serial id to each circle
    int squareIndex // the index of the square the center is in,
                    // a circle can only overlap with four squares
}

The circle class stores the basic needed data for the circle as well as it's collision square index to keep things simple. This could have been stored in some collision class as hash from circleId to collision square.

// Somewhere in the collision code //
grabSquareIndex(_x, _y)
{
  squareX = _x / SQUARE_SIZE;
  squareY = _y / SQUARE_SIZE;
  index = squareX + squareY * SQUARE_COUNT_X;
}

Keeping the grid up to date.

foreach (circle in circleList)
{
  tmpSquareIndex = grabSquareIndex(circle.cx, circl.cy);
  if (circle.squareIndex != tmpSquareIndex)
  {
    // remove circle id from old square
    grid[circle.squareIndex].remove(circle.id); // Won't work (implement in real code)
    // add it to new square
    grid[circle.tmpSquareIndex].add(circle.id); // Normally we use push() to do this
    circle.squareIndex = tmpSquareIndex;
  }
}

Checking for collisions between circles

foreach (circle in circleList)
{
  foreach (circleId in grid[circle.squareIndex])
  {
    if (circleId > circle.id) //cehck for collision
  }
  // check if circle may be overlapping a tile to the top left
  topLeft = grabSquareIndex(circle.cx - circle.cr, circle.cy - circle.cr);
  if (topLeft != circle.squareIndex)
  {
    foreach (circleId in grid[topLeft])
    {
      if (circleId > circle.id) //cehck for collision
    }
  }
  // Do the same for topRight and Bottom
  topRight = grabSquareIndex(circle.cx + circle.cr, circle.cy - circle.cr);
  if (topRight != topLeft && topRight != circle.squareIndex ...)
   //... do the same
  // Same idea for bottom
}