Indexing 6,000+ Map Points for an Extraction Game: Spatial Queries That Don't Stutter

Extraction shooters and PvPvE ARPGs put a strange burden on their community tooling. A normal wiki page answers "what is this item?" An interactive map has to answer a much harder question, dozens of times per second, while the user pans around: which of the thousands of points of interest are inside this rectangle, at this zoom level, with these filters enabled?

When I started sketching a companion map for Mistfall Hunter — Bellring Games' third-person PvPvE extraction ARPG that launched July 29 on Xbox, Steam and Game Pass — the point count looked manageable until it wasn't: spawns, loot containers, objectives, locked doors and extraction zones add up to roughly 6,300 verified coordinates across the game's maps. A naive points.filter(p => inViewport(p)) works in a demo and dies on a mid-range phone. This post walks through the data model and the indexing structure that made the map feel instant, and what I'd do differently next time.

The data model: one table, typed points, no cleverness

The first temptation is to model each point kind as its own entity — a Spawn table, a LootContainer table, an ExtractionZone table. Resist it. On a map, everything is a point with a type and a payload:

type PointType =
  | 'spawn'
  | 'loot'
  | 'objective'
  | 'extraction'
  | 'door';

interface MapPoint {
  id: string;
  map: string;          // map id, if the game has several
  x: number;            // world coordinates, not screen pixels
  y: number;
  type: PointType;
  tier?: number;        // loot rarity tier, objective difficulty, ...
  label: string;
  payload: Record<string, unknown>; // free-form: loot table ref, rotation info, ...
}

A single flat collection matters for two reasons:

1. Filtering is a bitmask, not a join. The UI has a row of toggle chips ("show loot", "show extractions"). If types live in separate tables, every pan/zoom/filter change becomes N queries and a merge. With one table, a filter is (point.type & activeMask) !== 0.
2. The index can be built once. Whatever spatial structure you choose, it wants a homogeneous array of {x, y, id} records.

Store world coordinates, never image pixels. The map art will get re-exported at higher resolution the week after you ship, and pixel coordinates silently rot. Keep a single worldToImage transform per map instead.

The query pattern you're actually optimizing for

Profile before you pick a structure. The real workload of an interactive game map is:

• Dominant query: axis-aligned bounding-box (AABB) read — "everything inside the current viewport rect."
• Frequency: every pointermove / wheel event, so 30–120 Hz, but cheap to debounce to animation frames.
• Writes: essentially zero at runtime; the dataset ships as a static JSON and changes on redeploy.
• Size: thousands, not millions. ~6,300 points is 300–600 KB as compact JSON, less after gzip.

That profile — read-heavy, static, medium-N — points directly at a static structure built at load time, not a dynamic quadtree.

Why not a quadtree

Quadtrees are the textbook answer and the wrong one here. They shine when points move (players, mobs) or when N is huge. For a static 6k-point dataset:

• Rebalancing logic is dead code — nothing ever mutates.
• Pointer-chasing through a tree in JS means cache-hostile object graphs.
• AABB queries still visit many internal nodes near the rectangle edge.

What worked: a flat grid hash + typed buckets

The structure I settled on is embarrassingly simple: a uniform grid over the map's bounding box, with each cell holding indexes into the flat point array.

class GridIndex {
  private cells: Map<number, number[]> = new Map();
  private cellSize: number;

  constructor(
    private points: MapPoint[],
    private bounds: { minX: number; minY: number; maxX: number; maxY: number },
    targetCellsPerSide = 64,
  ) {
    const w = bounds.maxX - bounds.minX;
    const h = bounds.maxY - bounds.minY;
    this.cellSize = Math.max(w, h) / targetCellsPerSide;
    points.forEach((p, i) => {
      const key = this.key(p.x, p.y);
      let cell = this.cells.get(key);
      if (!cell) this.cells.set(key, (cell = []));
      cell.push(i);
    });
  }

  private key(x: number, y: number): number {
    const cx = Math.floor((x - this.bounds.minX) / this.cellSize);
    const cy = Math.floor((y - this.bounds.minY) / this.cellSize);
    return cy * 4096 + cx; // cheap integer hash; 4096 > cells per side
  }

  query(rect: { minX: number; minY: number; maxX: number; maxY: number },
        typeMask: number): MapPoint[] {
    const out: MapPoint[] = [];
    const x0 = Math.floor((rect.minX - this.bounds.minX) / this.cellSize);
    const x1 = Math.floor((rect.maxX - this.bounds.minX) / this.cellSize);
    const y0 = Math.floor((rect.minY - this.bounds.minY) / this.cellSize);
    const y1 = Math.floor((rect.maxY - this.bounds.minY) / this.cellSize);
    for (let cy = y0; cy <= y1; cy++) {
      for (let cx = x0; cx <= x1; cx++) {
        const cell = this.cells.get(cy * 4096 + cx);
        if (!cell) continue;
        for (const i of cell) {
          const p = this.points[i];
          if (!(typeMask & (1 << typeIndex(p.type)))) continue;
          if (p.x >= rect.minX && p.x <= rect.maxX &&
              p.y >= rect.minY && p.y <= rect.maxY) out.push(p);
        }
      }
    }
    return out;
  }
}

Two details do the heavy lifting:

• Cell size chosen from N, not vibes. With ~6,300 points, 64×64 cells give an average of ~1.5 points per occupied cell. A viewport query touches a few hundred cells, examines a few hundred points, and keeps maybe a few dozen. That's microseconds, not milliseconds.
• The grid returns candidates; the final AABB test returns exact hits. Cells overlap rectangle borders, so the inner loop re-checks bounds. Skipping that check is the classic bug that makes markers "bleed" one cell past the viewport edge — harmless until you use the same query for hit-testing clicks.

Build cost at load is O(N) and takes ~2 ms for 6k points. The whole index is a Map<number, number[]> and a typed flat array — trivially serializable, trivially testable.

Clustering at low zoom is a separate problem

Zoomed all the way out, an AABB query correctly returns 4,000 points — which no renderer and no human wants. Don't solve this by degrading the index; solve it at the rendering layer:

• When query() returns more than a threshold (I use ~300), switch the renderer to density rendering: accumulate the candidate points into a coarse screen-space grid and draw one cluster badge per occupied cell with a count.
• Keep the same spatial index for both modes. Clustering libraries that rebuild their own tree per zoom level are wasted work on a static dataset.

const hits = index.query(viewport, typeMask);
if (hits.length > 300) renderClusters(hits);
else renderMarkers(hits);

Click hit-testing: reuse the index in reverse

The other query a game map needs is "which point did the user just click?" — a point query, not a rectangle query. The grid handles it for free: build a tiny AABB around the cursor (say ±8 px converted to world units at current zoom), run the same query(), then pick the nearest hit by Euclidean distance. No second index, no O(N) scan.

Testable invariants worth writing down

Map data is crowd-verified and drifts. Two cheap property tests caught more bad data than any manual review:

1. Every point lies inside its map's declared bounds. Off-by-one-tile coordinates from a data-entry error show up as markers in the void — or worse, silently dropped by the index key function.
2. Querying the full map bounds returns every point of the requested types. This round-trip test catches both index bugs and corrupted payloads in one assertion.

it('index round-trips all points', () => {
  const all = index.query(mapBounds, ALL_TYPES_MASK);
  expect(new Set(all.map(p => p.id)).size).toBe(points.length);
});

Seeing it in the wild

If you want to see what this feels like at full scale, the community database Mistfall Hunter Wiki & Build Tools runs exactly this kind of interactive map over its ~6,300 verified spawn/loot/objective/extraction points, layered with its item and recipe data. Toggling the loot/spawn/extraction layers while panning is a live demo of why the filter-as-bitmask + static-grid combination works: the query cost stays flat no matter which layers are on.

Takeaways

• One flat, typed point collection beats per-type entities for map data.
• Static dataset + AABB-dominant reads = uniform grid hash, not a quadtree.
• Cell size from point density (~1–2 points per cell), exact bounds re-check inside the loop.
• Clustering is a rendering decision, not an indexing decision.
• Round-trip property tests turn map data drift from silent rot into CI failures.

6,000 points feels like "too many to hand-place, too few to engineer for." It's exactly the range where a hundred lines of deliberate indexing turn a janky demo into something players actually leave open on a second monitor.