3
\$\begingroup\$

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);

enter image description here

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. 

\$\endgroup\$
  • 1
    \$\begingroup\$ That's pretty nifty! If you have two lists, plausiblePairs() and implausiblePairs(), you only do detailed checks on the plausible pairs. The check might move it to the implausible list. Each entry in "implausiblePairs" could have a frame number for when it needs to be put it back in the plausible list (because you calculated how many frames til they might). Keep the implausiblePairs sorted (or in a priority queue), so you can pull of implausibles that have expired easily. Nice! \$\endgroup\$ – david van brink Dec 27 '14 at 0:23
  • 2
    \$\begingroup\$ The more general technique for optimizing collision detection is spatial indexing — build a data structure (the classic example is a quadtree/octree) which makes it easy to find only objects in the neighborhood of another object. \$\endgroup\$ – Kevin Reid Dec 27 '14 at 3:08
  • \$\begingroup\$ @KevinReid I was under the impression that quadtree works for same-sized circles only(?). Is there a variant of spatial indexing that works for different-sized circles? \$\endgroup\$ – markE Dec 27 '14 at 3:21
  • 1
    \$\begingroup\$ I'm not familiar with the details, but the general pattern is that the index has some size (fixed, for a voxel array or hash, or varying in a quadtree) of "cells" (the level at which it just contains a set of objects), and you put the object into every cell which it intersects. Note that you have to also remove it before the object is resized or moved! \$\endgroup\$ – Kevin Reid Dec 27 '14 at 3:26
  • \$\begingroup\$ I added a comment about the expensive Math.sqrt :) \$\endgroup\$ – wolfdawn Dec 27 '14 at 8:06
3
\$\begingroup\$

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.

Circles in grid

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
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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