Bridges Without the Quadratic Tax

Bridge segments are deceptively expensive to draw. Each one has to decide whether nearby buildings should render in front or behind, which means sampling their footprints and nudging z-bias values. Our original applyBridgeBuildingZBias implementation did that by re-scanning the entire render list for every bridge. On dense towns the profiler showed the z-order pass dominating the frame, so we restructured it to scale with real interactions instead of the total doodad count.

The Old Pass: Bridges × Everything

for (const bridge of doodadsToRender) {
  if (!bridge.name.startsWith("bridge")) continue;
  for (const item of doodadsToRender) {
    if (!item.isBuilding) continue;
    evaluateBridgeBuilding(item, bridge);
  }
}

• Every bridge walked the full y-sorted doodad array — trees, rocks, signs, anything.
• Even though only buildings can actually collide, foliage and props were still visited twice per frame (once per bridge).
• Complexity was O(B × n), which in a 900-doodad scene with 8 bridges meant ~7,200 interaction checks every render tick.

The Fix: Bucket Once, Compare Only Candidates

1. Single classification pass — While zeroing zBias, we bucket render items into bridgeItems and buildingItems. Non-candidates are ignored for the rest of the pass.
2. Early exits — If either bucket is empty we bail immediately; no reason to touch the rest of the list.
3. Targeted comparisons — We only evaluate bridgeItems × buildingItems, so the work now scales with real overlap possibilities. This also makes the cache-friendly evaluateBridgeBuilding logic hot only when needed.

const bridgeItems = [];
const buildingItems = [];
for (const item of doodadsToRender) {
  item.zBias = 0;
  if (isBridge(item)) bridgeItems.push(item);
  else if (isBuilding(item)) buildingItems.push(item);
}
for (const bridge of bridgeItems) {
  for (const building of buildingItems) {
    applyBiasIfRelevant(building, bridge);
  }
}

Results

Scene	Before ( B × n )	After ( n + B × G )	Win
Busy town (900 doodads, 8 bridges, 200 buildings)	~7,200 interactions/frame	~1,600 interactions/frame	4.5× fewer comparisons
No bridges	~0 (loop skipped)	~900 ops for init pass	All bridge work avoided
No buildings	~0 (loop skipped)	~900 ops for init pass	Bridge-only maps stop early

Because the classification pass is linear and cache-friendly, the renderer no longer pays a quadratic tax when foliage counts explode. The remaining work is proportional to actual bridge/building interactions, so a map filled with trees costs the same as an empty plain as far as the z-order phase is concerned.

Takeaways

• Y-sorted render lists often contain heterogeneous data; bucket once up front so expensive passes only touch relevant items.
• Even seemingly “small” nested loops become hotspots when they run every frame — profile and look for places where n includes objects that can never participate.
• Small structural tweaks (like separating bridge and building arrays) are enough to drop layers of work without changing the underlying bias math or visuals.