Eighteen seconds to seven hundred milliseconds, and the test that proved nothing changed

Faster, and still the same answer

Every time I make something faster I'm making two claims, that it's faster and that it still gives the same answer. Timing it proves the first. The second usually just gets assumed, and that's the one that bites later.

This is how I took a layout sweep from roughly eighteen seconds to about seven hundred and fifty milliseconds, and the two structural decisions (an optional parameter and a parametrised equivalence test) that made the second claim something I could check.

What the sweep is doing

The engine packs fixed-size rectangular units into an irregular plot (a boundary polygon, a setback inside it, some obstacles and one entrance), leaving lanes wide enough to drive along. An arrangement is only valid if every unit sits inside the buildable area, no two overlap by more than a rounding error, consecutive rows sit at least a lane's width apart, and the point in front of every unit's access side can be reached from the entrance.

That last check is a raster. The drivable area is sampled on a 0.5m grid, cells blocked by the setback, an obstacle or a placed unit are marked, and the rest is flood-filled from the entrance.

Generating a layout means sweeping about 108 candidates (a range of row angles crossed with a few start offsets), building each one and putting it through the whole validator. A full sweep ran eighteen to twenty seconds locally and thirty-four on CI, which is why the test timeout had been set to a forgiving 120 seconds.

The obvious fix barely helped

Boundary minus setback minus obstacles doesn't change across a sweep, only the units move. So the static part of the raster is now built once per sweep, not once per candidate.

export interface PlotMask {
  minX: number;
  minY: number;
  step: number;
  nx: number;
  ny: number;
  // 1 iff that cell's centre is inside the buildable area and outside every obstacle
  allowed: Uint8Array;
}

That removed redundant work and was clearly correct. Then I profiled the sweep again, expecting most of the time to have gone, and it hadn't. The raster rebuild was never the dominant cost.

Two other things were. The overlap check compared every pair of footprints with a full polygon-intersection call, which is quadratic in the most expensive operation in the file. And the connectivity check tested every cell in the grid against every footprint using a general containment predicate, which comes to millions of calls per sweep.

I already knew to profile first. What I noticed was that a redundant computation being easy to see doesn't mean it's the slow one.

Three safe speed-ups

Each fix had to come with an argument that its cheap answer and the expensive answer can never differ.

A bounding-box pre-reject. Two polygons whose axis-aligned bounding boxes are disjoint can't overlap.

function bboxesOverlap(a: BBox, b: BBox): boolean {
  return a.minX <= b.maxX && a.maxX >= b.minX && a.minY <= b.maxY && a.maxY >= b.minY;
}

It only ever skips pairs whose intersection area is already guaranteed to be zero, so it only saves time and never changes the answer.

A bounded cell range. A footprint can only contain a cell centre that lies inside its own bounding box, because containment implies being in the box. So the connectivity pass only walks each footprint's own bbox-derived range of cells. That turns cells × units into units × cells-per-footprint, with one cell of padding for the floor-and-ceil edges.

An exact point-in-quadrilateral test. This is the one I like. It replaces the general containment predicate.

function pointInFootprint(ring: Ring, p: Point): boolean {
  for (let k = 0; k < ring.length; k++) {
    const a = ring[k];
    const b = ring[(k + 1) % ring.length];
    if ((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x) <= 0) return false;
  }
  return true;
}

For a convex polygon wound counter-clockwise, "strictly inside" is the same as "strictly to the left of every directed edge". Both conditions hold here, and neither by luck. Footprints are quadrilaterals from a single generator that emits its four corners in a fixed order in the unit's own frame, and rotation preserves winding. The <= 0 keeps boundary points out, which matches the general predicate's interior-only semantics.

So this isn't an approximation. It's exact for these footprints, because the generator guarantees their winding. The generator documents that guarantee, and the replacement cites it, so anyone reordering those corners finds out why they can't.

Together the three took the sweep to about 750ms.

The optional fourth parameter

export function validate(
  units: Unit[],
  plot: PlotInput,
  settings: Settings,
  mask?: PlotMask,
): Validation;

Leave out the mask and the function builds its own. The standalone contract hasn't changed, so nothing outside the sweep had to learn that masks exist.

Optional caching parameters often sneak in a second way of being right, and I think that's a bad trade whatever it buys you. This one doesn't. Both paths run the same code over the same raster, and the parameter only decides whether that raster gets rebuilt. Grid origin, step and cell count can't drift, because one function decides all three and both paths call it.

The equivalence test

The equivalence test is parametrised over every scenario the validator's own suite already covers. That's an overlapping pair, a valid row, an island walled in by obstacles, another walled in by units, an entrance with no drivable cell in reach, two rows too close, and a unit straddling the setback edge.

it.each(scenarios)("%s: a precomputed mask matches no mask", (_name, s) => {
  const withoutMask = validate(s.units, s.plot, s.settings);
  const withMask = validate(s.units, s.plot, s.settings, buildPlotMask(s.plot, s.settings));
  expect(withMask).toEqual(withoutMask);
});

It compares the whole result object, not just the boolean, so the list of failure kinds and the human-readable detail strings are in there too, and those strings carry coordinates to two decimal places. A change that flipped a single cell would move a number inside a message, and the comparison would catch it. So "semantics-preserving" is something the build checks, on the cases I already care about.

Tightening the test timeout

The sweep test's timeout came down from 120 seconds to 30. A ceiling set for the slow version stops being a guard once the slow version's gone, and turns into somewhere a regression can sit unnoticed for months. Thirty seconds is still plenty of headroom for a slow runner, and it would catch anything that brought back a fortyfold cost. All 54 tests stayed green throughout.