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
| Principle | Plain Explanation |
| Spatial Partitioning | Only look at neighbors that share nearby grid cells |
| Zero-Copy Lists | Return direct arrays to avoid allocations per frame |
| Squared Distances | Skip expensive Math.sqrt until truly required |
| Behavior Layering | Combine simple forces for emergent strategy |
| Profiling-Driven | Measure first, optimize where it counts |
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;
}
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);
}
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) {
this.enforceZoneContainment(boid, herdingZone);
} else {
this.applyBoundaryCollision(boid, herdingZone);
}
Threat detection snippet:
nearbyPlayers.forEach(player => {
const d2 = boid.position.distanceSquared(player.position);
if (d2 < this.threatRadiusSquared) {
boid.isThreatened = true;
}
});
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);
}
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):
| Function | Calls | Avg Time (ms) | Max Time (ms) | Calls After | Avg After | Max After |
| updateFlock | 1,654 | 8.70 | 49.54 | 1,602 | 3.52 | 18.50 |
| calculateFlockingForces | 132,400 | 0.089 | 2.67 | 128,240 | 0.030 | 2.77 |
| getNearbyBoidsZeroCopy | 333,793 | 0.003 | 1.05 | 128,240 | 0.002 | 0.54 |
| resolveCollisions | 132,400 | 0.006 | 1.31 | 128,240 | 0.000 | 0.09 |
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)
| Technique | Benefit |
| Numeric Cell Hash | Fast constant-time cell lookup |
| Pre-Allocated Temp Arrays | Avoid GC churn |
| Zero-Copy Neighbor Lists | Minimize allocations & copying |
| Squared Distance Comparisons | Avoid unnecessary sqrt |
| Shared Neighbor Queries | Prevent duplicate grid scans |
| Layered Containment | Natural feel without physics engine |
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 ?
Increase FLOCK_SIZE progressively; chart profiler output.
Introduce dynamic obstacles requiring avoidance force.
Add predator entity with different threat radius or pursuit logic.
Swap grid for a quadtree; compare complexity vs. gains.
Visualize cells occupancy live (debug overlay).
Add per-force weighting UI sliders; observe stability thresholds.
Implement adaptive cell size (benchmark vs. fixed cells).
Glossary
| Term | Simple Definition |
| Boid | Autonomous flocking entity |
| Spatial Grid | Grid indexing for nearby queries |
| Zero-Copy | Returning internal arrays without cloning |
| Containment | Forces keeping boids within a zone |
| Squared Distance | Distance without square root (fast compare) |
| Profiling | Measuring runtime performance |
| Herd Pressure | Emergent directional bias from threatened neighbors |
| Branch Prediction | CPU guessing next instruction path (keep tight loops simple) |
| Cache Coherence | Keeping frequently accessed data contiguous |
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 ! 🚀
