Boids Flocking

3 min read•1 page

Reynolds Flocking (Boids Model): In 1987, Craig Reynolds proved that complex emergent collective behavior (such as starling murmurations and fish schools) does not require a central leader. Instead, it emerges from three simple local steering forces: Separation (collision avoidance), Alignment (velocity matching), and Cohesion (flock centering).

Three Steering Vectors:

1. Separation (Red): Repels from nearby agents within a short personal safety radius. 2. Alignment (Yellow): Matches the average velocity orientation of flock neighbors. 3. Cohesion (Green): Pulls toward the centroid (center of mass) of local neighbors.

python

1import numpy as np
2
3def compute_boid_steering(boid, neighbors, w_sep=1.5, w_ali=1.0, w_coh=1.0):
4    """
5    Craig Reynolds (1987) Boids Flocking Model.
6    Synthesizes 3 steering forces: Separation, Alignment, Cohesion.
7    """
8    # 1. Separation: steer to avoid crowding local flockmates (inverse distance)
9    f_sep = np.zeros(3)
10    for other in neighbors:
11        diff = boid.pos - other.pos
12        dist = np.linalg.norm(diff)
13        if dist > 1e-4:
14            f_sep += (diff / dist) / dist  # 1/r force
15            
16    # 2. Alignment: steer towards average heading of local flockmates
17    avg_vel = np.mean([other.vel for other in neighbors], axis=0) if neighbors else boid.vel
18    f_ali = avg_vel - boid.vel
19    
20    # 3. Cohesion: steer to move toward average position (center of mass) of flockmates
21    avg_pos = np.mean([other.pos for other in neighbors], axis=0) if neighbors else boid.pos
22    f_coh = avg_pos - boid.pos
23    
24    # Combined acceleration vector
25    accel = w_sep * f_sep + w_ali * f_ali + w_coh * f_coh
26    return accel

Separation Weight

1.60

Cohesion Weight

1.00

3 min read•1 page

Spatial Hashing ($O(N)$ Neighbor Discovery): Computing pair-wise distances across thousands of boids costs $O(N^2)$ checks per frame, choking CPU/GPU simulations. By quantizing space into a regular grid of bucket size $R$ (the visual perception radius), agents only query the 27 neighboring grid bins, reducing computational complexity to strict $O(N)$ linear time.

Uniform Grid Partitioning:

1. Cell Quantization: Continuous point $(x, y, z)$ hashes to integer voxel $(\lfloor x/R \rfloor, \lfloor y/R \rfloor, \lfloor z/R \rfloor)$. 2. Adjacent Bin Lookup: Queries 9 cells in 2D or 27 cells in 3D, pruning distant agents before distance math. 3. Scalable Swarm Dynamics: Enables real-time simulation of tens of thousands of particles or biological agents.

python

1class SpatialHashGrid:
2    """
3    Accelerates boid neighbor discovery from O(N^2) to O(N).
4    Maps 3D continuous space into discrete hash buckets sized by perception radius.
5    """
6    def __init__(self, cell_size):
7        self.cell_size = cell_size
8        self.grid = {}
9
10    def _hash(self, point):
11        return (
12            int(point[0] // self.cell_size),
13            int(point[1] // self.cell_size),
14            int(point[2] // self.cell_size)
15        )
16
17    def insert(self, boid_id, point):
18        key = self._hash(point)
19        if key not in self.grid:
20            self.grid[key] = []
21        self.grid[key].append(boid_id)
22
23    def query_neighbors(self, point):
24        cx, cy, cz = self._hash(point)
25        candidates = []
26        # Inspect 3x3x3 adjacent bucket neighborhood (27 cells)
27        for dx in (-1, 0, 1):
28            for dy in (-1, 0, 1):
29                for dz in (-1, 0, 1):
30                    key = (cx + dx, cy + dy, cz + dz)
31                    if key in self.grid:
32                        candidates.extend(self.grid[key])
33        return candidates

Hash Cell Size R

1.50