How to Generate Hundreds of Non‑Overlapping Circles Quickly with Canvas

Problem Statement

A game requires eliminating targets within a limited time on a 2D plane. To simplify hit detection, each target is approximated by a circle. The article focuses on the case where all circles have the same size and are static, and provides code for both equal‑size/static and variable‑size/static scenarios.

Basic Linear Approach

Randomly generate a point, draw a circle around it, and repeat. If the new circle overlaps an existing one, discard it; otherwise keep it.

Random Point Function

function randomPoint({w, h}) {
  const x = parseInt(Math.random() * w);
  const y = parseInt(Math.random() * h);
  return {x, y};
}

The algorithm must avoid two invalid cases: points too close to the canvas border (ignored because a random point in the full width guarantees at least half the circle stays inside) and points that overlap existing circles, which requires collision detection.

Collision Detection

Two circles overlap when the distance between their centers is less than the sum of their radii.

function testOverlay(pointA, pointB) {
  const xGap = Math.abs(pointA.x - pointB.x);
  const yGap = Math.abs(pointA.y - pointB.y);
  const distance = Math.sqrt(xGap * xGap + yGap * yGap);
  const rGap = pointA.r + pointB.r;
  return distance >= rGap;
}

Valid Point Test

To decide whether a newly generated point is usable, iterate over all existing circles and apply the collision test.

function testAvailable(pointArr, newPoint) {
  let arr = Array.from(pointArr);
  let aval = true;
  while (arr.length > 0) {
    const lastPoint = arr.pop();
    if (testOverlay(lastPoint, newPoint)) {
      aval = false;
      break;
    }
  }
  return aval;
}

Limiting Attempts

When the canvas becomes almost full, the naive loop can run indefinitely. Adding a counter that stops after a certain number of failed attempts prevents endless execution.

Alternative BFS‑Based Method

Instead of generating points globally, start from a valid point and search for N new valid points around it (breadth‑first search). Repeat the process recursively until no more space is available. This combines BFS with random placement.

Relative Random Point (Fixed Radius)

function randomRelativePoint(prev, radius) {
  const dia = radius * 2;
  const xGap = Math.random() * (dia * 2);
  const x = parseInt(xGap + prev.x - dia);
  const sign = Math.random() - 0.5 > 0 ? 1 : -1;
  const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)));
  const y = prev.y + yGap * sign;
  return {x, y, r: radius};
}

Relative Random Point (Random Radius – Pre‑Check)

function randomRelativePoint(prev, size) {
  const {maxR, minR} = size;
  const nextR = parseInt(Math.random() * (maxR - minR) + minR);
  const dia = prev.r + nextR;
  const xGap = prev.x - dia < 0
    ? Math.random() * (prev.x + dia)
    : prev.x + dia > size.w
      ? Math.random() * (size.w - prev.x + dia)
      : Math.random() * (dia * 2);
  const x = prev.x - dia < 0
    ? parseInt(xGap)
    : parseInt(xGap + prev.x - dia);
  const sign = Math.random() - 0.5 > 0 ? 1 : -1;
  const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)));
  const y = prev.y - yGap < 0
    ? prev.y + yGap
    : prev.y + yGap > size.h
      ? prev.y - yGap
      : yGap * sign + prev.y;
  return {x, y, r: nextR};
}

Relative Random Point (Random Radius – Post‑Check)

function randomRelativePoint(prev, radius) {
  const dia = radius * 2;
  const xGap = Math.random() * (dia * 2);
  const x = parseInt(xGap + prev.x - dia);
  const sign = Math.random() - 0.5 > 0 ? 1 : -1;
  const yGap = parseInt(Math.sqrt(dia * dia - (prev.x - x) * (prev.x - x)));
  const y = yGap * sign + prev.y;
  return {x, y, r: radius};
}

Performance Comparison

On a 320 × 550 canvas the two approaches differ by less than 10 % in coverage (roughly 4–5 extra circles). On a larger 2000 × 2000 canvas the simple random algorithm is markedly faster, while still staying within a 10 % coverage gap; the BFS‑combined method can take up to a second for random‑radius placement.

Application in a Game

The principles are illustrated with the puzzle game Human Resource Machine , where only a handful of assembly‑like instructions are available and the player must optimise both code length and execution speed, encouraging deep thinking about data storage, processing, and algorithmic efficiency.

Complete Example

The final demo uses the second (post‑check) algorithm with fixed radius for simplicity, but the source includes both fixed‑radius and random‑radius implementations, as well as the pre‑check variant.