Scaling Boids for Multiplayer Games: Fast Flocking with Spatial Grids & Zero-Copy Optimization

Turning O(n²) neighbor searches into silky smooth herding behavior.

TL;DR 📝

We'll walk through concrete optimizations—spatial grids, zero-copy neighbor lookups, squared-distance checks, and how profiling guided the changes that let Shepherd's World run many more boids smoothly.

Related Articles

Rendering and Client Prediction
Building Multiplayer Game in TS

Who this is for

intermediate devs comfortable with basic flocking who want to scale simulations and profile hot paths effectively.

Why Naive Flocking Melts CPUs

A classic boids implementation loops every boid over every other boid to compute separation, alignment, and cohesion. That’s O(n²) work per frame: double your boids, quadruple your cost. In a multiplayer game with server authority, wasteful cycles quickly become latency spikes. Shepherd's World avoids this trap through spatial partitioning, layered behaviors, and careful math choices (like squared distances).

Core Optimization Principles

The Forces

• Separation: "Don't crowd me."

• Alignment: "Match heading with flockmates."

• Cohesion: "Stay with the group."

• Flee: "Run from nearby players."

• Boundary / Zone Logic: "Walls and zone edges matter more than casual nudges."

Excerpt from BoidsManager.calculateFlockingForces:

const separation = this.calculateSeparation(boid, sameZoneNeighbors);
const alignment = this.calculateAlignment(boid, sameZoneNeighbors);
const cohesion = this.calculateCohesion(boid, sameZoneNeighbors);
const flee = this.calculateFleeFromPlayers(boid, nearestPlayer);
const boundaryAvoidance = this.calculateBoundaryAvoidance(boid, herdingZone);
const zoneAvoidance = this.calculateZoneAvoidance(boid, herdingZone, sameZoneNeighbors);

Check out my article about Vectors for Autonomous Agents https://arnauld-alex.com/introduction-to-vectors-for-autonomous-agents-in-p5js

Spatial Grid Optimization

Instead of scanning all boids, I bucket them by position using a numerically hashed grid.

Key locations:

• src/shared/SimpleGrid.ts — rebuild, getNearbyBoidsZeroCopy, getNearbyPlayersZeroCopy

• src/server/BoidsManager.ts — Requests neighbors once per boid per frame

Hashing approach:

private hash(x: number, y: number): number {
  const cellX = Math.floor(x / this.cellSize);
  const cellY = Math.floor(y / this.cellSize);
  return cellY * this.gridWidth + cellX; // numeric hash
}

Range query zero-copy pattern:

getNearbyBoidsZeroCopy(boid: Boid, range: number = 50): ReadonlyArray<Boid> {
  const allNearby = this.queryRangeZeroCopy(boid.position.x, boid.position.y, range, 'boids');
  return allNearby.filter(other => other !== boid); // exclude self
}

Deep Dive: Spatial Partitioning

A uniform grid divides space so each cell holds only local entities. For each boid I derive a small set of candidate cells based on its interaction radius rather than scanning the full flock. Even if boids total 500, any one boid might only inspect a few dozen neighbors. This slashes CPU time, making higher flock sizes viable without frame drops.

Layered Zone & Threat Behavior

Boids react differently when inside vs. outside the herding zone, and when pressured by players.

if (boid.isInZone) {
    // Graduated containment
    this.enforceZoneContainment(boid, herdingZone);
} else {
    // Avoid walls & zone boundary
    this.applyBoundaryCollision(boid, herdingZone);
}

Threat detection snippet:

nearbyPlayers.forEach(player => {
    const d2 = boid.position.distanceSquared(player.position);
    if (d2 < this.threatRadiusSquared) {
        boid.isThreatened = true;
        // track nearest threatening player
    }
});

Deep Dive: Layered Zone Containment

Instead of a single hard boundary, containment uses soft inward forces near edges, velocity damping close to critical thresholds, and final positional clamping. This multi-stage approach prevents jittery "bouncing" while still guaranteeing boids remain inside once herded, producing natural-looking confinement.

Collision & Separation Efficiency

The collision resolver only computes Math.sqrt after confirming overlap via a squared distance comparison.

const distanceSquared = boid.position.distanceSquared(otherBoid.position);
if (distanceSquared < this.collisionRadiusSquared) {
    const distance = Math.sqrt(distanceSquared); // Only now
    // separation & position correction
}

Deep Dive: Squared Distances

Most distance comparisons only need relative ordering, not the actual distance. Using squared distances avoids thousands of square root operations per second. Square roots appear only when we must scale corrections by the true distance value (e.g., overlap resolution intensity).

Profiling to Guide Improvements

Decorator-based profiling in non-production builds highlights hotspots:

• @ProfileMethod annotations on updateFlock, calculateFlockingForces, etc.

• PerformanceProfiler.getFormattedReport() prints average, min, max times.

export function ProfileMethod(target: any, prop: string, descriptor: PropertyDescriptor) {
    const original = descriptor.value;
    descriptor.value = function (...args: any[]) {
        if (process.env.NODE_ENV === 'production') return original.apply(this, args);
        if (!this._profiler) this._profiler = new PerformanceProfiler();
        const start = performance.now();
        const result = original.apply(this, args);
        this._profiler.recordExecution(prop, performance.now() - start);
        return result;
    };
}

Deep Dive: Data-Driven Optimization

Rather than guessing, profiling quantifies exactly where time is spent. Once separation showed minimal cost, focus shifted to reducing redundant neighbor queries, halving total frame time. Measurement sharpens intuition and prevents premature complexity.

Optimization Comparison: Shared Neighbor Lists

A major performance win came from sharing the same neighbor list across all per-boid computations, instead of querying the spatial grid repeatedly. This change slashed redundant work and improved both average and worst-case frame times.

Profiler Results (Before vs After Optimization):

By reusing neighbor lists, the average flock update time dropped by ~60%, and worst-case spikes were cut by over half. This enables much larger flocks and smoother gameplay, with only a tiny increase in grid update cost. Profiling guided the change, proving that targeted optimizations—especially reducing duplicate neighbor queries—deliver the biggest real-world gains.

The Flocking Update Loop (Putting It Together)

Common Performance Wins Recap

Key Takeaways

• Spatial partitioning is the single biggest scaling lever.

• Optimize based on profiling, not hunches.

• Use squared distances and only compute expensive math when essential.

• Layer behaviors to produce emergent strategy cues.

• Keep data structures simple; clarity aids performance.

• Always confirm a hotspot with numbers before rewriting logic.

• Behavior composition beats monolithic “do everything” loops.

What could be next ?

1. Increase FLOCK_SIZE progressively; chart profiler output.

2. Introduce dynamic obstacles requiring avoidance force.

3. Add predator entity with different threat radius or pursuit logic.

4. Swap grid for a quadtree; compare complexity vs. gains.

5. Visualize cells occupancy live (debug overlay).

6. Add per-force weighting UI sliders; observe stability thresholds.

7. Implement adaptive cell size (benchmark vs. fixed cells).

Glossary

---

Note about process: I used AI to help write parts of code, but I made the conception, design choices, reviewed and tested the code as well as written the majority of it. It was a great tool to iterate over ideas.

---

Thank you for reading my blog ! If you enjoyed this post and want to stay connected, feel free to connect with me on LinkedIn. I love networking with fellow developers, exchanging ideas, and discussing exciting projects.

Connect with me on LinkedIn 🔗

Looking forward to connecting with you ! 🚀