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:
- Check the grid squares for correctness (circles are actually in their respective squares).
- Update with changes if necessary (i.e. remove a circle from where it no longer is, add it to where it actually is).
- Check for collisions only with circles that occupy the same grid squares.
- 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).
- 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
}