The shepherding problem. One dog, many sheep, no leader: how can a single pursuer move a flock to a target? Strömbom, Mann, Tarry, Garnier, Couzin et al. (J. R. Soc. Interface 11:20140719, 2014) showed that two simple dog rules plus a standard sheep flocking model are enough.
Sheep (each time step, 1 ts ≈ 1 s). Heading is a weighted sum of unit vectors:
H(t+1) = h·H(t) + c·A + ρa·Ra + ρs·S + e·ε
A = toward the centre of mass of the k nearest sheep
Ra = away from sheep closer than r_a
S = away from the dog, only if the dog is within r_s
ε = random unit vector (angular noise)
If the dog is farther than r_s the sheep graze: they move only with probability p and without the dog term. The new heading is normalised and the sheep step v metres.
Dog. Let G be the flock centre of mass and T the target. If every sheep is within f(N) = r_a·N^(2/3) of G the flock is cohesive and the dog drives: it runs to the point G + r_a√N · (G−T)/|G−T| behind the flock. Otherwise it collects: it runs behind the sheep farthest from G, on the side away from G, so that sheep is pushed back to the group.
Published defaults used here: N=100, r_s=65 m, r_a=2 m, ρa=2, c=1.05, ρs=1, h=0.5, e=0.3, p=0.05, k=50, sheep 1 m/ts, dog 1.5 m/ts. These are the values as I recall them from the paper's Table 1 — treat them as approximate and check the paper for exact numbers. The grazing step (0.3 m) is my own choice.
What is added here, and is not in the paper: obstacles (walls, water, rocks), a pen with a gate, dog sliding around obstacles, level waypoints (gate apron, bridge), and a “sweep the stragglers to the gate” rule. Without them the published algorithm cannot get through a gate or over a bridge — try the levels with the checkbox off.
Why f(N) = r_a N^(2/3)? It is the paper's rule of thumb for how wide a loose flock of N sheep is. The “Cohesion f(N)” check measures the real equilibrium radius of a grazing flock; in this implementation the largest distance from the centre is roughly 0.5–0.8 of f(N) (so f(N) acts as an upper bound), and the fitted exponent comes out near 0.7, close to 2/3.