Circles and Boxes

What You’ll Learn

Circles and axis-aligned boxes. Between them they cover almost every collision a 2D game actually ships, and there are only three pairings to learn: circle–circle, box–box, circle–box.

The reason that is three lessons and not three formulas is that all three are one distance and one comparison, and the third reduces to the first by a single clamp. Once you see that, collision stops being a list of cases to memorise.

This Section answers only “did they touch”. Working out how deep the overlap is and which way to push is Section 5.4, and keeping the two questions apart is most of what makes collision code readable.

Circle Against Circle

(b_x - a_x)^2 + (b_y - a_y)^2 < (r_a + r_b)^2

Compare the distance between the centres against the sum of the radii. Squared on both sides, so there is no square root anywhere — Section 1.3’s shortcut, and this is where it earns its keep, because a broad-phase check runs this thousands of times a frame.

Strictly less than, so circles that touch at exactly one point are not overlapping. That is a decision rather than a fact, and it is the one to make: standing on the ground is touching, and a test that calls that a collision leaves a character permanently colliding with the floor it is resting on.

Box Against Box

Two axis-aligned boxes overlap only if they overlap on both axes. It is easier to get right stated negatively: they miss if there is any axis on which one lies entirely to one side of the other.

\text{overlap} \iff (a_{\min x} < b_{\max x} \wedge b_{\min x} < a_{\max x}) \wedge (\text{same for } y)

That sentence — one separating axis is enough to prove a miss — is the whole of Section 5.3, which does the same thing for shapes whose axes are not the world’s. Seeing the box test as “check every axis” rather than as four inequalities makes that Section a small step instead of a new subject.

Three pairings of circles and boxes, one test at a time

Pick a pairing, drag the shape into the other one, then tick the box and head for a corner.

The code that draws it src/lib/gamedev/demos/2d/shapes.scene.ts

/** Three pairings of circles and boxes, one test at a time, with the shape you drag doing the asking. */
import {
  makeCanvas2D,
  addDragTargets,
  dot as fillDot,
  label,
  line,
} from "../canvas2d.ts";
// From `controls.ts`, not `ui.ts`: the latter imports Three.js and this track must not.
import {
  addButtonRow,
  addCheckbox,
  addReadout,
  addSlider,
} from "../controls.ts";
import {
  BOUNDS,
  KINDS,
  MOVING_RADIUS,
  START,
  STATIC_BOX,
  STATIC_CIRCLE,
  UNIT,
  VIEW,
  movingBoxAt,
  reportAt,
  screenOf,
  worldOf,
  type Kind,
} from "./shapes-shared.ts";
import type { MountFn } from "../runner.ts";

const APART = "#58a6ff";
const TOUCHING = "#f0883e";
const STATIC = "#7d8590";
const NEAREST = "#7ee787";
const WRONG = "#ff7b72";
const AXIS = "#3b4552";
const DIM = "#636c76";

const mount: MountFn = (el) => {
  const { ctx, canvas, clear } = makeCanvas2D(el, VIEW.height);

  let kind: Kind = KINDS[0];

  const show = addReadout(el);
  const note = addReadout(el);
  const px = addSlider(el, "x", -BOUNDS.x, BOUNDS.x, START.x, draw, "", 0.05);
  const py = addSlider(el, "y", -BOUNDS.y, BOUNDS.y, START.y, draw, "", 0.05);
  const showWrong = addCheckbox(
    el,
    "also run the wrong version of this test",
    false,
    draw,
  );
  const setActive = addButtonRow(
    el,
    KINDS.map((k, index) => ({
      label: k,
      apply: () => {
        kind = k;
        setActive(index);
        draw();
      },
    })),
  );
  setActive(0);

  // Dragging is the natural way in; the two sliders are the keyboard path to the same position.
  const stopDragging = addDragTargets(
    canvas,
    () => [screenOf({ x: px(), y: py() })],
    (_index, sx, sy) => {
      const world = worldOf(sx, sy);
      px.set(Math.min(Math.max(world.x, -BOUNDS.x), BOUNDS.x));
      py.set(Math.min(Math.max(world.y, -BOUNDS.y), BOUNDS.y));
      draw();
    },
  );

  function strokeCircle(
    centre: { x: number; y: number },
    radius: number,
    colour: string,
    width = 2,
    dashed = false,
  ) {
    const c = screenOf(centre);
    ctx.save();
    ctx.strokeStyle = colour;
    ctx.lineWidth = width;
    if (dashed) ctx.setLineDash([5, 4]);
    ctx.beginPath();
    ctx.arc(c.x, c.y, radius * UNIT, 0, Math.PI * 2);
    ctx.stroke();
    ctx.restore();
  }

  function strokeBox(
    box: { min: { x: number; y: number }; max: { x: number; y: number } },
    colour: string,
    width = 2,
    dashed = false,
  ) {
    const a = screenOf(box.min);
    const b = screenOf(box.max);
    ctx.save();
    ctx.strokeStyle = colour;
    ctx.lineWidth = width;
    if (dashed) ctx.setLineDash([5, 4]);
    ctx.strokeRect(
      Math.min(a.x, b.x),
      Math.min(a.y, b.y),
      Math.abs(b.x - a.x),
      Math.abs(b.y - a.y),
    );
    ctx.restore();
  }

  function draw() {
    clear();
    const p = { x: px(), y: py() };
    const r = reportAt(kind, p);
    const colour = r.hit ? TOUCHING : APART;

    // The axes, so a reader can see the box test really is about the two of them separately.
    line(
      ctx,
      { x: 0, y: VIEW.height / 2 },
      { x: VIEW.width, y: VIEW.height / 2 },
      AXIS,
      { width: 1 },
    );
    line(
      ctx,
      { x: VIEW.width / 2, y: 0 },
      { x: VIEW.width / 2, y: VIEW.height },
      AXIS,
      { width: 1 },
    );

    // The shape that stays put.
    if (kind === "two circles") {
      strokeCircle(STATIC_CIRCLE.centre, STATIC_CIRCLE.radius, STATIC);
    } else {
      strokeBox(STATIC_BOX, STATIC);
    }

    // What the test measured, drawn before the moving shape so the shape sits on top of it.
    if (kind === "two circles") {
      line(ctx, screenOf(STATIC_CIRCLE.centre), screenOf(p), colour, {
        width: 1.5,
      });
      // The reach: the two radii laid end to end along that same line.
      strokeCircle(
        STATIC_CIRCLE.centre,
        STATIC_CIRCLE.radius + MOVING_RADIUS,
        DIM,
        1,
        true,
      );
      label(
        ctx,
        "the sum of the radii",
        screenOf({ x: STATIC_CIRCLE.centre.x, y: STATIC_CIRCLE.centre.y }).x +
          6,
        screenOf({
          x: 0,
          y: STATIC_CIRCLE.centre.y - STATIC_CIRCLE.radius - MOVING_RADIUS,
        }).y - 8,
        DIM,
      );
    } else if (kind === "circle and box") {
      // The clamp, which is the whole test: centre to nearest point on the box.
      if (r.nearest) {
        const q = screenOf(r.nearest);
        line(ctx, screenOf(p), q, NEAREST, { width: 1.5 });
        fillDot(ctx, q.x, q.y, 4.5, NEAREST);
        label(ctx, "the clamped point", q.x + 8, q.y - 8, NEAREST);
      }
    } else {
      // Two ranges per axis, drawn along the edges of the canvas.
      const moving = movingBoxAt(p);
      const rows: Array<[number, number, number, string]> = [
        [STATIC_BOX.min.x, STATIC_BOX.max.x, VIEW.height - 26, STATIC],
        [moving.min.x, moving.max.x, VIEW.height - 18, colour],
      ];
      for (const [lo, hi, y, c] of rows) {
        line(
          ctx,
          { x: screenOf({ x: lo, y: 0 }).x, y },
          { x: screenOf({ x: hi, y: 0 }).x, y },
          c,
          { width: 3 },
        );
      }
      const cols: Array<[number, number, number, string]> = [
        [STATIC_BOX.min.y, STATIC_BOX.max.y, 14, STATIC],
        [moving.min.y, moving.max.y, 22, colour],
      ];
      for (const [lo, hi, x, c] of cols) {
        line(
          ctx,
          { x, y: screenOf({ x: 0, y: lo }).y },
          { x, y: screenOf({ x: 0, y: hi }).y },
          c,
          { width: 3 },
        );
      }
      /* Both labels sit **beside the bars they name**. The y one was at the top-left corner of the
         canvas while its bars run down the middle of the left edge, so the two vertical strips read as
         unexplained decoration - which is what a reader reported. Anchored to the static box's own y
         range, which never moves, so the label cannot drift away from what it is pointing at. */
      label(ctx, "x ranges", 12, VIEW.height - 30, DIM);
      label(
        ctx,
        "y ranges",
        32,
        (screenOf({ x: 0, y: STATIC_BOX.min.y }).y +
          screenOf({ x: 0, y: STATIC_BOX.max.y }).y) /
          2 +
          4,
        DIM,
      );
    }

    // The shape being dragged.
    if (kind === "two boxes") strokeBox(movingBoxAt(p), colour, 2.4);
    else strokeCircle(p, MOVING_RADIUS, colour, 2.4);
    const centre = screenOf(p);
    fillDot(ctx, centre.x, centre.y, 3.5, colour);

    /* The wrong version's verdict, drawn only when asked and only when it differs. A wrong answer that
       happens to agree here is not worth a mark on the picture. */
    if (showWrong() && r.naiveDisagrees) {
      strokeCircle(p, MOVING_RADIUS + 0.16, WRONG, 1.5, true);
      label(
        ctx,
        "the wrong test disagrees here",
        centre.x + 12,
        centre.y + 20,
        WRONG,
      );
    }

    label(ctx, "drag the shape, or use the sliders", 12, VIEW.height - 8, DIM);

    show(
      `${kind} \u00b7 ${r.detail} \u00b7 ` +
        `${r.hit ? `overlapping by ${Math.abs(r.separation).toFixed(2)}` : `apart by ${r.separation.toFixed(2)}`}`,
    );
    note(
      showWrong()
        ? r.naiveDisagrees
          ? kind === "two circles"
            ? "here the wrong test squares the radii separately and misses an overlap that is really there"
            : "here the wrong test grew the box by the radius, so its corners are square and it reports a hit too early"
          : kind === "two boxes"
            ? "there is no popular wrong version of the box test \u2014 it is two range checks and hard to get subtly wrong"
            : "the two agree at this position, which is why the bug survives testing \u2014 move toward a corner"
        : r.hit
          ? "one distance and one comparison, and no square root anywhere"
          : "a miss is proved by a single gap, which is the idea Section 5.3 generalises",
    );
  }

  draw();

  return stopDragging;
};

export default mount;

Note what “axis-aligned” is buying. The box’s edges are always parallel to the axes, so no test here ever considers an angle. A box that can rotate costs a great deal more, and that is why so many games give a rotating sprite an upright collision box and accept the mismatch.

Circle Against Box, Which Is Circle Against Circle

Here is the good part. Clamp the circle’s centre into the box, one axis at a time:

q = \left(\text{clamp}(p_x, \min_x, \max_x),\ \text{clamp}(p_y, \min_y, \max_y)\right)

That gives the point of the box nearest the circle’s centre. Then it is a distance against a radius — test one, unchanged.

Two clamps. That is the entire thing, and it is worth pausing on why it works: the axes are independent, so the nearest allowed $x$ cannot depend on $y$ . It handles all three cases — nearest to a face, nearest to a corner, and the centre already inside the box — with no branch distinguishing them. The build checks it against a brute-force scan of the box’s whole perimeter.

The clamp, and the two popular ways to get these tests wrong

The code src/lib/gamedev/demos/2d/hittest.ts

/** The clamp that turns circle-versus-box into circle-versus-circle, and the two ways to get it wrong. */
import {
  circlesOverlap,
  circlesOverlapWrongSquare,
  closestPointInAabb,
  cornerErrorArea,
  toBox,
} from "../../../gamedev2d/collide2d.ts";
import { MOVING_RADIUS, STATIC_BOX, STATIC_CIRCLE } from "./shapes-shared.ts";
import type { Demo } from "../runner.ts";

const at = (x: number, y: number) => ({ x, y });
const show = (p: { x: number; y: number }) => `(${p.x}, ${p.y})`;

const demo: Demo = (log) => {
  // One clamp per axis, and it covers a face, a corner and the inside with no branch between them.
  log(
    "closestPointInAabb(box, (4, 0))",
    show(closestPointInAabb(STATIC_BOX, at(4, 0))),
    "clamped on x only, so the nearest point is on a face",
  );
  log(
    "closestPointInAabb(box, (4, 3))",
    show(closestPointInAabb(STATIC_BOX, at(4, 3))),
    "clamped on both, so it is a corner - the same two lines of code",
  );
  log(
    "closestPointInAabb(box, (-1.5, 0))",
    show(closestPointInAabb(STATIC_BOX, at(-1.5, 0))),
    "already inside, so it is the point itself",
  );

  // The mistake that makes collision feel late: squaring the radii instead of their sum.
  const reach = STATIC_CIRCLE.radius + MOVING_RADIUS;
  const wrongReach = Math.sqrt(STATIC_CIRCLE.radius ** 2 + MOVING_RADIUS ** 2);
  log(
    `(${STATIC_CIRCLE.radius} + ${MOVING_RADIUS})\u00B2 against ${STATIC_CIRCLE.radius}\u00B2 + ${MOVING_RADIUS}\u00B2`,
    `${reach ** 2} against ${STATIC_CIRCLE.radius ** 2 + MOVING_RADIUS ** 2}`,
    `the missing 2\u00B7r\u2090\u00B7r\u1D47 is ${2 * STATIC_CIRCLE.radius * MOVING_RADIUS}, which is most of it`,
  );
  /* Placed between the two reaches, so the right test says yes and the wrong one says no. A round 2.25
     rather than the midpoint of the two, because the wrong reach is a square root and the midpoint
     printed as 0.8512812094883317 in a panel that gets committed. The build asserts 2.25 really does
     fall between them, which is the part that has to be true. */
  const between = at(STATIC_CIRCLE.centre.x + 2.25, 0);
  log(
    `both tests on a circle at ${show(between)}`,
    `correct ${circlesOverlap(STATIC_CIRCLE, { centre: between, radius: MOVING_RADIUS })}, wrong ${circlesOverlapWrongSquare(STATIC_CIRCLE, { centre: between, radius: MOVING_RADIUS })}`,
    `the wrong one only reports contact at ${((wrongReach / reach) * 100).toFixed(2)}% of the right distance`,
  );

  // And the corner bug, priced in closed form rather than described.
  log(
    "cornerErrorArea(1.25), the area the naive box test gets wrong",
    cornerErrorArea(1.25).toFixed(4),
    "(4 \u2212 \u03C0)r\u00B2, and it does not depend on the box at all",
  );

  // Two representations of one box, because passing one where the other belongs still looks like a box.
  const asBox = toBox(STATIC_BOX);
  log(
    "toBox(box), from two corners to a centre and half-extents",
    `centre ${show(asBox.centre)}, half ${show(asBox.half)}`,
    `the box is ${STATIC_BOX.max.x - STATIC_BOX.min.x} by ${STATIC_BOX.max.y - STATIC_BOX.min.y}, so the extents are halved - mix the two forms up and you get a box of the wrong size that still looks like a box`,
  );
};

export default demo;

closestPointInAabb(box, (4, 0)) → (0.25, 0) // clamped on x only, so the nearest point is on a face

closestPointInAabb(box, (4, 3)) → (0.25, 1.25) // clamped on both, so it is a corner - the same two lines of code

closestPointInAabb(box, (-1.5, 0)) → (-1.5, 0) // already inside, so it is the point itself

(1.5 + 1.25)² against 1.5² + 1.25² → 7.5625 against 3.8125 // the missing 2·rₐ·rᵇ is 3.75, which is most of it

both tests on a circle at (0.75, 0) → correct true, wrong false // the wrong one only reports contact at 71.00% of the right distance

cornerErrorArea(1.25), the area the naive box test gets wrong → 1.3413 // (4 − π)r², and it does not depend on the box at all

toBox(box), from two corners to a centre and half-extents → centre (-1.5, 0), half (1.75, 1.25) // the box is 3.5 by 2.5, so the extents are halved - mix the two forms up and you get a box of the wrong size that still looks like a box

The Corner Bug

Now the mistake nearly everybody makes first, because it is simpler and it is nearly right: grow the box by the radius and test whether the centre is inside it.

Where a circle's centre can be and still touch a box

Grow the radius and watch the gap between the two outlines open up at the corners.

The code that draws it src/lib/gamedev/demos/2d/corners.scene.ts

/** The region a circle's centre can be in and still touch a box: rounded corners, not square ones. */
import { makeCanvas2D, dot as fillDot, label, line } from "../canvas2d.ts";
// From `controls.ts`, not `ui.ts`: the latter imports Three.js and this track must not.
import { addCheckbox, addReadout, addSlider } from "../controls.ts";
import {
  CORNER_BOX,
  RADIUS_RANGE,
  UNIT,
  VIEW,
  cornerErrorArea,
  errorFraction,
  naiveRegion,
  screenOf,
} from "./shapes-shared.ts";
import type { MountFn } from "../runner.ts";

const BOX = "#7d8590";
const TRUE_REGION = "#7ee787";
const NAIVE = "#ff7b72";
const PROBE = "#ffd866";
const DIM = "#636c76";

const mount: MountFn = (el) => {
  const { ctx, clear } = makeCanvas2D(el, VIEW.height);

  const show = addReadout(el);
  const note = addReadout(el);
  const radius = addSlider(
    el,
    "the circle's radius",
    RADIUS_RANGE.min,
    RADIUS_RANGE.max,
    1.1,
    draw,
    "",
    0.05,
  );
  const probe = addCheckbox(
    el,
    "put a circle at the worst point the naive test accepts",
    true,
    draw,
  );

  function draw() {
    clear();
    const r = radius();
    const box = CORNER_BOX;
    const grown = naiveRegion(r);
    const a = screenOf(box.min);
    const b = screenOf(box.max);
    const left = Math.min(a.x, b.x);
    const right = Math.max(a.x, b.x);
    const top = Math.min(a.y, b.y);
    const bottom = Math.max(a.y, b.y);
    const pad = r * UNIT;

    /* The four corner squares the naive test wrongly accepts, shaded before either outline so both
       outlines stay legible on top of them. Each is a square minus a quarter-disc. */
    ctx.save();
    ctx.fillStyle = "rgba(255, 123, 114, 0.18)";
    for (const [cx, cy, sx, sy] of [
      [right, top, 1, -1],
      [right, bottom, 1, 1],
      [left, bottom, -1, 1],
      [left, top, -1, -1],
    ] as const) {
      ctx.beginPath();
      ctx.moveTo(cx, cy);
      ctx.lineTo(cx + sx * pad, cy);
      ctx.lineTo(cx + sx * pad, cy + sy * pad);
      ctx.lineTo(cx, cy + sy * pad);
      ctx.closePath();
      // Cut the quarter-disc back out, leaving exactly the region the two tests disagree on.
      ctx.arc(cx, cy, pad, 0, Math.PI * 2, true);
      ctx.fill("evenodd");
    }
    ctx.restore();

    // The box itself.
    ctx.save();
    ctx.strokeStyle = BOX;
    ctx.lineWidth = 2;
    ctx.strokeRect(left, top, right - left, bottom - top);
    ctx.restore();

    // What the naive test accepts: the box grown by the radius, corners and all.
    const ga = screenOf(grown.min);
    const gb = screenOf(grown.max);
    ctx.save();
    ctx.strokeStyle = NAIVE;
    ctx.lineWidth = 1.6;
    ctx.setLineDash([6, 4]);
    ctx.strokeRect(
      Math.min(ga.x, gb.x),
      Math.min(ga.y, gb.y),
      Math.abs(gb.x - ga.x),
      Math.abs(gb.y - ga.y),
    );
    ctx.restore();

    // What is actually true: the same box with rounded corners of exactly the radius.
    ctx.save();
    ctx.strokeStyle = TRUE_REGION;
    ctx.lineWidth = 2.2;
    ctx.beginPath();
    ctx.moveTo(left, top - pad);
    ctx.lineTo(right, top - pad);
    ctx.arc(right, top, pad, -Math.PI / 2, 0);
    ctx.lineTo(right + pad, bottom);
    ctx.arc(right, bottom, pad, 0, Math.PI / 2);
    ctx.lineTo(left, bottom + pad);
    ctx.arc(left, bottom, pad, Math.PI / 2, Math.PI);
    ctx.lineTo(left - pad, top);
    ctx.arc(left, top, pad, Math.PI, (3 * Math.PI) / 2);
    ctx.closePath();
    ctx.stroke();
    ctx.restore();

    /* A circle sitting at the naive region's corner: the furthest the wrong test accepts. Its distance
       from the box corner is r*sqrt(2), so it clears the corner by r*(sqrt(2) - 1) and touches nothing. */
    if (probe()) {
      const worst = { x: grown.max.x, y: grown.max.y };
      const w = screenOf(worst);
      ctx.save();
      ctx.strokeStyle = PROBE;
      ctx.lineWidth = 2;
      ctx.beginPath();
      ctx.arc(w.x, w.y, pad, 0, Math.PI * 2);
      ctx.stroke();
      ctx.restore();
      fillDot(ctx, w.x, w.y, 3.5, PROBE);
      // The gap it leaves, drawn from the box's corner toward the circle's centre.
      const corner = screenOf(box.max);
      line(ctx, corner, w, PROBE, { dashed: true, width: 1.2 });
      label(ctx, "accepted, and touching nothing", w.x + 10, w.y - 8, PROBE);
    }

    label(ctx, "the box", left + 8, bottom - 8, BOX);
    label(ctx, "actually touching: rounded", 12, 16, TRUE_REGION);
    label(ctx, "the naive test: square", 12, 30, NAIVE);
    label(ctx, "the difference is the bug", 12, VIEW.height - 8, DIM);

    show(
      `radius ${r.toFixed(2)} \u00b7 the wrong region is bigger by ` +
        `${cornerErrorArea(r).toFixed(3)} square units, which is (4 \u2212 \u03C0)r\u00B2 \u00b7 ` +
        `${(errorFraction(r) * 100).toFixed(2)}% of everything it accepts`,
    );
    note(
      `at a corner it over-reaches by r(\u221A2 \u2212 1) = ${(r * (Math.SQRT2 - 1)).toFixed(3)} units \u2014 ` +
        "41.42% of the radius, whatever the radius is, and whatever the box is",
    );
  }

  draw();

  return () => {};
};

export default mount;

Growing a rectangle by $r$ gives you square corners. The region where a circle’s centre can sit and actually touch the box has rounded ones, of radius exactly $r$ . So the naive test reports a hit while the circle is still short of the corner, touching nothing: a shot that stops in mid-air near a crate, which usually gets blamed on the renderer.

The size of the mistake is not a matter of opinion. The false region is four corner squares minus four quarter-discs:

4r^2 - \pi r^2 = (4 - \pi)\,r^2 \approx 0.8584\,r^2

Independent of the box entirely. The build measures that area by counting grid cells where the two tests disagree and compares the count against the formula — two completely different computations, agreeing to under half a percent.

And at a corner specifically, the over-reach has a clean value. The grown box’s corner sits $r\sqrt{2}$ from the real corner while the true region reaches only $r$ , so the naive test accepts circles up to

r\left(\sqrt{2} - 1\right) \approx 0.4142\,r

past the point of contact — 41.42% of the radius, whatever the radius, whatever the box.

Along a face the naive test is exactly right, which is precisely why it survives. If you test it by walking a circle straight at a wall, it passes.

Where The Square Roots Went

None of the three tests needs one. Circle–circle squares the reach, box–box only compares coordinates, and circle–box squares the radius. That matters less than it used to for a handful of shapes and matters a great deal at the scale collision runs at — and it costs nothing in clarity once the habit is to square the threshold rather than root the distance.

The trap is that a squared distance is not a distance. Compare it against a squared threshold or the numbers are nonsense, and it is nonsense that looks plausible: a radius of 5 quietly becomes a radius of 25 rather than an error.

source Three tests, two representations of a box, and the wrong versions kept for pricing src/lib/gamedev2d/collide2d.ts 275 lines

/**
 * Circles and boxes: the two shapes almost every 2D game actually ships, and the three tests between them.
 *
 * All three come down to **one distance and one comparison**, and the third one comes down to the
 * second by a single clamp. That is worth saying up front, because a collision chapter can look like a
 * list of unrelated formulas to memorise when it is really one idea applied three times.
 *
 * The tests here are boolean: did they touch. Working out how to *respond* - how deep the overlap is
 * and which way to push - is Section 5.4, and mixing the two together is what makes collision code
 * hard to follow. One question at a time.
 */
import { distanceSquared, length } from "./length2d.ts";
import { displacement, type Point } from "./vectors2d.ts";

export type Circle = {
  centre: Point;
  radius: number;
};

/**
 * An axis-aligned box, stored as its two opposite corners.
 *
 * "Axis-aligned" is the whole reason this shape is cheap: its edges are always parallel to the axes, so
 * a test never has to consider an angle. A box that can rotate is Section 5.3's problem and costs a
 * great deal more.
 */
export type Aabb = {
  min: Point;
  max: Point;
};

/**
 * The same box, stored as a centre and half-widths. Both forms are common and they are not interchangeable.
 *
 * Engines disagree: Godot's `Rect2` is position and size, Unity's `Bounds` is centre and extents, and
 * plenty of code uses min/max. Passing one where the other is expected produces a box of the wrong size
 * in the wrong place, and it still looks like a box, so nothing crashes. Convert deliberately.
 */
export type Box = {
  centre: Point;
  /** Half the width and half the height. **Half**, which is the part people get wrong. */
  half: Point;
};

/** Centre-and-half-extents to min-and-max. */
export function toAabb(box: Box): Aabb {
  return {
    min: { x: box.centre.x - box.half.x, y: box.centre.y - box.half.y },
    max: { x: box.centre.x + box.half.x, y: box.centre.y + box.half.y },
  };
}

/** And back. Note the halving, which is the direction the mistake usually happens in. */
export function toBox(box: Aabb): Box {
  return {
    centre: {
      x: (box.min.x + box.max.x) / 2,
      y: (box.min.y + box.max.y) / 2,
    },
    half: {
      x: (box.max.x - box.min.x) / 2,
      y: (box.max.y - box.min.y) / 2,
    },
  };
}

/** A box from a centre and its **full** width and height, which is what a sprite's size usually is. */
export function boxAround(centre: Point, width: number, height: number): Aabb {
  return toAabb({ centre, half: { x: width / 2, y: height / 2 } });
}

/**
 * Is this box the right way round? A box built from two dragged corners often is not.
 *
 * Every test below assumes `min` really is the smaller corner. Hand one an inverted box and it reports
 * no collision, always, for any other shape - a solid wall that everything walks through, with no error
 * anywhere. Which is why `normalized` exists and why a drag should go through it.
 */
export function isValidAabb(box: Aabb): boolean {
  return box.min.x <= box.max.x && box.min.y <= box.max.y;
}

/** The same box with its corners put in the right order. */
export function normalized(box: Aabb): Aabb {
  return {
    min: {
      x: Math.min(box.min.x, box.max.x),
      y: Math.min(box.min.y, box.max.y),
    },
    max: {
      x: Math.max(box.min.x, box.max.x),
      y: Math.max(box.min.y, box.max.y),
    },
  };
}

export function boxWidth(box: Aabb): number {
  return box.max.x - box.min.x;
}

export function boxHeight(box: Aabb): number {
  return box.max.y - box.min.y;
}

// ---- Test one: two circles ------------------------------------------------------------------

/**
 * Do two circles overlap? Compare the distance between their centres against the sum of their radii.
 *
 * $$(b_x - a_x)^2 + (b_y - a_y)^2 < (r_a + r_b)^2$$
 *
 * **Squared on both sides**, so there is no square root. Section 1.3's shortcut, and this is the place
 * it earns its keep: a broad-phase check runs this thousands of times a frame.
 *
 * Strictly less than, so circles that touch exactly are **not** overlapping. That is a choice rather
 * than a fact, and the one to make: resting on the ground is touching, and a test that calls it a
 * collision leaves a character permanently colliding with the floor it is standing on.
 */
export function circlesOverlap(a: Circle, b: Circle): boolean {
  const reach = a.radius + b.radius;
  return distanceSquared(a.centre, b.centre) < reach * reach;
}

/**
 * The mistake this test invites: squaring the radii **separately** instead of squaring their sum.
 *
 * $$r_a^2 + r_b^2 \quad\text{instead of}\quad (r_a + r_b)^2 = r_a^2 + 2r_ar_b + r_b^2$$
 *
 * The missing $2r_ar_b$ is not a small correction. For two circles of equal radius it shrinks the reach
 * from $2r$ to $r\sqrt{2}$, so contact is not reported until the circles are already $29\%$ past where
 * they should have touched - a gap that reads as "collision feels late" rather than as a bug.
 */
export function circlesOverlapWrongSquare(a: Circle, b: Circle): boolean {
  return (
    distanceSquared(a.centre, b.centre) <
    a.radius * a.radius + b.radius * b.radius
  );
}

/** How far apart their surfaces are. Negative when they overlap. Section 5.4 builds on this. */
export function circleSeparation(a: Circle, b: Circle): number {
  return length(displacement(a.centre, b.centre)) - (a.radius + b.radius);
}

// ---- Test two: two boxes --------------------------------------------------------------------

/**
 * Do two ranges on one axis overlap? The whole box test is this, twice.
 *
 * Pulling it out is not tidiness. It is the idea Section 5.3's separating-axis test generalises, and
 * seeing the box test as "check every axis" here makes that Section a small step rather than a new
 * subject.
 */
export function rangesOverlap(
  minA: number,
  maxA: number,
  minB: number,
  maxB: number,
): boolean {
  return minA < maxB && minB < maxA;
}

/**
 * Do two axis-aligned boxes overlap? Only if they overlap on **both** axes.
 *
 * Easier to get right in its negative form: they miss if there is **any** axis on which one is
 * entirely to one side of the other. One separating axis is enough to prove a miss, and that is the
 * sentence Section 5.3 turns into a general algorithm.
 */
export function aabbsOverlap(a: Aabb, b: Aabb): boolean {
  return (
    rangesOverlap(a.min.x, a.max.x, b.min.x, b.max.x) &&
    rangesOverlap(a.min.y, a.max.y, b.min.y, b.max.y)
  );
}

/**
 * The overlap on each axis, negative when there is a gap. How deep, not just whether.
 *
 * The **smaller** of the two is the one that matters for pushing a shape back out, because it is the
 * shorter way to separate them. That is the minimum translation vector, and it is Section 5.4's
 * subject; here it is only the measurement.
 */
export function aabbOverlapDepth(a: Aabb, b: Aabb): { x: number; y: number } {
  return {
    x: Math.min(a.max.x, b.max.x) - Math.max(a.min.x, b.min.x),
    y: Math.min(a.max.y, b.max.y) - Math.max(a.min.y, b.min.y),
  };
}

/** Is this point inside the box? The degenerate case of the test above, with a box of no size. */
export function aabbContains(box: Aabb, p: Point): boolean {
  return (
    p.x >= box.min.x && p.x <= box.max.x && p.y >= box.min.y && p.y <= box.max.y
  );
}

/** The box grown outward by the same amount on every side. Used by the corner bug below. */
export function expanded(box: Aabb, by: number): Aabb {
  return {
    min: { x: box.min.x - by, y: box.min.y - by },
    max: { x: box.max.x + by, y: box.max.y + by },
  };
}

// ---- Test three: a circle and a box, which is test one in disguise ---------------------------

/**
 * The point of the box closest to `p`: **clamp the point into the box, one axis at a time.**
 *
 * $$q = \left(\text{clamp}(p_x, \min_x, \max_x),\ \text{clamp}(p_y, \min_y, \max_y)\right)$$
 *
 * Two clamps. That is the entire circle-versus-box test, and it is worth pausing on why it works: the
 * axes are independent, so the nearest allowed $x$ cannot depend on $y$. It handles all three cases -
 * nearest to a face, nearest to a corner, and the point already inside - without a single branch
 * distinguishing them.
 *
 * When `p` is inside the box the answer is `p` itself, which is correct for a containment test and
 * **not** enough for a push-out direction. Section 5.4 needs the nearest point on the boundary, which
 * is a different question and needs the branch this function avoids.
 */
export function closestPointInAabb(box: Aabb, p: Point): Point {
  return {
    x: Math.min(Math.max(p.x, box.min.x), box.max.x),
    y: Math.min(Math.max(p.y, box.min.y), box.max.y),
  };
}

/**
 * Does a circle overlap a box? Clamp the centre into the box, then it is a distance against a radius.
 *
 * Test three collapses into test one, which is the pleasant part of this Section. Still squared on both
 * sides, still no square root.
 */
export function circleAabbOverlap(circle: Circle, box: Aabb): boolean {
  const nearest = closestPointInAabb(box, circle.centre);
  return (
    distanceSquared(circle.centre, nearest) < circle.radius * circle.radius
  );
}

/**
 * The wrong version, and it is the one people reach for: **grow the box by the radius and test the centre.**
 *
 * It is right along the faces and wrong at the corners, because growing a rectangle by $r$ gives square
 * corners where the true region has rounded ones. So it reports a hit while the circle is still short of
 * the corner - a shot that stops in mid-air near a crate, which is exactly the kind of bug that gets
 * blamed on the renderer.
 *
 * The size of the mistake is not a matter of opinion. The false region is four corner squares minus
 * four quarter-discs, so its area is
 *
 * $$4r^2 - \pi r^2 = (4 - \pi)\,r^2 \approx 0.8584\,r^2$$
 *
 * independent of the box. The build measures it by sampling and compares against that expression.
 */
export function circleAabbOverlapNaive(circle: Circle, box: Aabb): boolean {
  return aabbContains(expanded(box, circle.radius), circle.centre);
}

/** How far the circle's edge is from the box. Negative when they overlap. */
export function circleAabbSeparation(circle: Circle, box: Aabb): number {
  const nearest = closestPointInAabb(box, circle.centre);
  return length(displacement(circle.centre, nearest)) - circle.radius;
}

/**
 * The exact area the naive test gets wrong, for comparing a measurement against.
 *
 * Stated as a function rather than as a comment so the check can call it, and so the claim in the
 * Section is arithmetic rather than a remembered figure.
 */
export function cornerErrorArea(radius: number): number {
  return (4 - Math.PI) * radius * radius;
}

Godot: Rect2.intersects() for box–box, Rect2.has_point() for containment, and Rect2.grow() is literally the naive expansion above — useful, and not a circle test. Real circle collision goes through CircleShape2D and the physics server, or Geometry2D helpers for one-off queries. Rect2.abs() is the normalizing step, and it exists because inverted rectangles are common enough to need it.

Unity 2D: Bounds.Intersects(), Bounds.Contains(), and Bounds.ClosestPoint() — that last one is the two clamps, already written. Physics2D.OverlapCircle is the engine-side version. Bounds is centre-and-extents, and extents is the half size while size is the full one; mixing them up is the representation bug above with a specific name.

Both engines separate a cheap bounding-volume pass from an exact one, which is the broad-phase idea in the tip above rather than an implementation detail.

Where This Shows Up

Section 5.2, where the same clamp idea gives the closest point on a line segment.
Section 5.3, which turns “one separating axis proves a miss” into a general algorithm.
Section 5.4, which needs the depth this Section only measures, and the push-out direction it deliberately does not compute.
Section 1.3’s squared distance, finally doing the job it was introduced for.
The capstone, whose character is an AABB moving against tiles.

Three pairings, one idea. Circle–circle compares centre distance against the sum of the radii, squared on both sides so there is no square root — and square the sum, because dropping the $2r_ar_b$ costs 29.29% of the reach for equal radii. Box–box is two range checks, and one separating axis is enough to prove a miss, which is Section 5.3 in a sentence. Circle–box is circle–circle with the centre clamped into the box first, two lines handling face, corner and inside with no branch. Do not instead grow the box by the radius: that gives square corners where the truth is rounded, over-reporting by $(4-\pi)r^2$ of area and reaching $0.4142\,r$ past contact at every corner. And normalize any box whose corners came from a drag, because an inverted box collides with nothing and says nothing.