How to spread circles evenly around a point?

Question

In my game there's a part where a bunch of circles need to evenly spread around a point. Like in this demo below:

const rng = (min, max) => Math.random() * (max - min + 1) + min;

const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");

ctx.strokeStyle = "#000";
ctx.lineWidth = 4;
ctx.fillStyle = "#ff0000";

function drawCircle(c) {
  ctx.beginPath();
  ctx.arc(c.x, c.y, c.r, 0, 2 * Math.PI);
  ctx.stroke();
  ctx.fill();
}

class Circle {
  constructor(x, y, r) {
    this.x = x;
    this.y = y;
    this.r = r;
    this.vX = 0;
    this.vY = 0;
  }
}

const circles = [];

for (let i = 0; i < 300; i++) {
  circles.push(new Circle(rng(0, canvas.width), rng(0, canvas.height), rng(12, 14)));
}

function processCollision(c1, c2) {
  const deltaX = c2.x - c1.x;
  const deltaY = c2.y - c1.y;

  const sumRadius = c1.r + c2.r;
  const centerDistance = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
  
  if (centerDistance === 0 || centerDistance > sumRadius) { return; } // not colliding

  const circleDistance = centerDistance - sumRadius;

  const aX = deltaX / centerDistance;
  const aY = deltaY / centerDistance;

  const force = 5;

  c1.vX += aX * circleDistance * force;
  c1.vY += aY * circleDistance * force;
}

function update() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  for (const c of circles) {
    c.vX = (canvas.width / 2) - c.x; // move towards center x
    c.vY = (canvas.height / 2) - c.y; // move towards center y
  }
  
  for (const c1 of circles) {
    for (const c2 of circles) {
      c1 !== c2 && processCollision(c1, c2);
    }
  }
  
  for (const c of circles) {
    c.x += c.vX * (1 / 60);
    c.y += c.vY * (1 / 60);

    drawCircle(c);
  }
}

setInterval(update, 16.6666);

<canvas width="600" height="600" style="border:1px solid #d3d3d3;">

This works, but you'll notice most of the circles overlap each other, especially the ones in the center. I'm looking for a solution where the circles mostly don't overlap at all (a little is okay).

I tried adjusting the force parameter, and while that works slightly, it also causes a lot of shake, jitter, and jank. I would like everything to remain smooth and calm, and I am having a lot of trouble doing that. Is there any way to have the circles mostly evenly spread around the center point without massively colliding with one another?

Answer 1

Some quick optimizations you can make are to process collisions in a double-sided way, so you don't have to process them twice each, and save your square roots for only the cases where you need them:

function processCollision(c1, c2) {
  const deltaX = c2.x - c1.x;
  const deltaY = c2.y - c1.y;

  const interactionRange = 2;

  // Note if your circles all have the same size, you can
  // save sumRadius as a constant externally, and not re-compute it.
  const sumRadius = c1.r + c2.r + interactionRange;
  const squaredDistance = deltaX * deltaX + deltaY * deltaY;
  
  if (squaredDistance === 0 || squaredDistance > sumRadius * sumRadius) { return; } // not colliding

  const centerDistance = Math.sqrt(squaredDistance);
  

  const circleDistance = centerDistance - sumRadius;      

  const force = 5;

  const aX = circleDistance * force * deltaX / centerDistance;
  const aY = circleDistance * force * deltaY / centerDistance; 

  c1.vX += aX;
  c1.vY += aY;

  c2.vX -= aX;
  c2.vY -= aY;
}

Next, keep some velocity from frame to frame, and treat the inward pull as a competing acceleration:

function update() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  const inertia = 0.8;
  const attraction = 0.1;

  for (const c of circles) {
    c.vX *= inertia;
    c.vY *= inertia;

    c.vX += attraction * ((canvas.width / 2) - c.x);
    c.vY += attraction * ((canvas.height / 2) - c.y);
  }
  
  // Process each spring just once.
  for (let i = 0; i < circleCount; i++) {
    for (let j = i+1; j < circleCount; j++) {
      processCollision(circles[i], circles[j]);
    }
  }
  
  for (const c of circles) {
    c.x += c.vX * (1 / 60);
    c.y += c.vY * (1 / 60);

    drawCircle(c);
  }
}

Increase the interactionRange parameter to give more of a buffer between circles where the repulsion force can ramp up, and increase the force parameter to make the ramp steeper, so you get a stronger push.

If it jerks and jitters too much, reduce the inertia parameter to sap more energy out of the system.

If the pull into the center is too strong, reduce the attraction parameter. You could even make this attraction ignore distance, so you don't get tighter squeezes at the perimeter than near the center.