Why Our Ghost Collision Checks Were Melting the Frame Budget

Previewing a building in the level editor should feel instant, even on city-sized maps. Instead, our profiler showed getBuildingCollisionMap eating several milliseconds per mouse move, and the cost climbed linearly with every placement on the map. Here’s how we replaced that O( placements × footprint² ) monster with a simple occupancy cache and reclaimed the frame budget.

The Old Loop

Every time the mouse moved, we:

1. Built a ghost placement representing the building under your cursor.
2. Ran getBuildingCollisionMap, which internally:
   • Iterated every other placement O(n).
   • Recomputed its collidable footprint array (new allocations).
   • Nested some calls comparing every ghost cell to every existing cell.

Pseudo-code:

for each existingPlacement:
  const otherCells = getCollidableCellsForPlacement(existingPlacement);
  if (ghostCells.some(cell =>
        otherCells.some(o => o.x === cell.x && o.y === cell.y))) {
    markCollision(cell);
  }

If you had 150 placements averaging 6 collidable tiles, the collision highlight touched ~5,400 cell comparisons on every RAF tick—before React even had a chance to re-render. Double the level density and the cost doubled too.

Enter the Occupancy Index

We asked a simpler question: why keep expanding every placement when the world grid already tells us which tiles are occupied? The fix involved two small pieces:

1. Precompute per-placement metadata—tile identity, tree/unique flags, and its collidable cells (from domain/footprints).
2. Bucket those cells by coordinate in a Map<"x,y", Placement[]>.

That gives us an O(n) preprocessing step we can memoize any time the placement list changes. Once the map exists, checking a ghost footprint becomes trivial:

function hasCollision(tileX, tileY) {
  const occupants = occupancy.byCell.get(`${tileX},${tileY}`) ?? [];
  return occupants.some(o => conflictsWithGhost(o));
}

• Ghost footprints are tiny (e.g., 4 tiles for a house), so the per-frame work is now O(ghostFootprint) rather than O(totalPlacements × footprint²).
• The conflictsWithGhost guard lets us keep special cases (trees overlapping trees, unique buildings replacing themselves) without extra lookups.

Numbers

Scenario	Before	After
150 placements, 6-tile average footprint	~5,400 cell comparisons per frame	~20 lookups per frame
Complexity	O(numPlacements × footprint²)	O(ghostFootprint)
Allocation pressure	Arrays rebuilt each mouse move	None (index reused until placements change)

The editor’s collision highlight now tracks the cursor without stutter, even when we load a late-game save full of structures. More importantly, the cost no longer scales with scene density; it only scales with the building you’re previewing.

Takeaways

• Mouse-move handlers fire every frame. Anything that scales with total scene population will eventually dominate your budget.
• If you’re repeatedly asking “who occupies tile (x, y)?”, build a spatial index once and reuse it.
• Memoizing derived data alongside placement lists fits nicely into React/Zustand patterns—you rebuild the index only when the source array changes.

Next on the menu: share the same occupancy cache with placement validation and undo/redo, so we don’t re-walk the world during clicks either. Stay tuned.