0
\$\begingroup\$

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?

\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Hey thanks! I really like that for loop trick you used to make sure each collision pair is only tested once, but how would that work with a spatial hash? This code works by only processing a collision pair once, but with a spatial hash can't you not do that? Unless each circle had a huge circle id -> boolean hashmap mapping that was reset every frame, but that would be too cost prohibitive, no? Or maybe not, if it only reset the used pairs every frame.. Thinking about it now if there's a better way... \$\endgroup\$ Sep 21 at 13:32
  • \$\begingroup\$ I wonder if it would be better to instead just process every circle pair twice? Because with a spatial hash in order to prevent a double process you would need to maintain a mapping, no? Which would need to be cleared every frame. If each circle needs to clear each mapping, that is an O(n^2) operation, no? And also would cause a lot of garbage collection, because the circle count changes as the game progresses, so I can't just preallocate a giant array. I feel like maintaining that setup and the hashing costs are probably higher than just double-processing, no? (which is just simple math) \$\endgroup\$ Sep 21 at 13:41
  • 1
    \$\begingroup\$ Let's say your spatial hash structure is a grid of buckets. Each bucket contains a list of circles whose centers fall in that grid cell. You then iterate over each bucket, testing each circle in that bucket against each circle after it in the bucket, and against each circle in a neighbouring bucket below or to the right. You don't double-process any pair this way, and you don't need the giant map that you describe. \$\endgroup\$
    – DMGregory
    Sep 21 at 13:59
  • \$\begingroup\$ You just blew my mind but I'm still trying to think about whether or not that would work.. If it does then it would be huge and save me so many CPU cycles. But the way my program works (since I don't know which grids are in use), is by iterating through all the circles: like for (let c of circle) { for (let square of spatial.retrieve(c)) { .. } } Does your strategy still work in that case? \$\endgroup\$ Sep 21 at 14:11
  • \$\begingroup\$ You actually gave me goosebumps. I'm pretty sure you're right and that it actually works. Holy shit I love you this is going to improve the performance of my game by so much. Thank you soooooooooooooo much Thank you thank you thank you! \$\endgroup\$ Sep 21 at 14:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .