The Herd That Bunches

// internal/field/flock.go

// Separate is the push-apart rule: a direction away from every
// neighbour, each one weighted by how close it is, so the body nearest
// gets the loudest vote. Dividing the offset by the distance twice is
// the whole of that weighting: once to throw the length away, once to
// make the vote fall off with range.
func (g Gait) Separate(b Body, near []Body) Vec2 {
	var away Vec2
	n := 0
	for _, o := range near {
		d := b.Pos.Sub(o.Pos)
		r := d.Len()
		if r == 0 {
			continue // two bodies on the same pixel name no direction
		}
		away = away.Add(d.Scale(1 / (r * r)))
		n++
	}
	if n == 0 {
		return Vec2{}
	}
	return g.Steer(b, away.Unit().Scale(g.MaxSpeed))
}

// Align is the match-heading rule: the average of the neighbours'
// velocities, taken as a direction and asked for at full speed. The
// average's own length is thrown away, so a body surrounded by slow
// neighbours still wants to travel; what it copies is where they are
// going, not how fast.
func (g Gait) Align(b Body, near []Body) Vec2 {
	if len(near) == 0 {
		return Vec2{}
	}
	var sum Vec2
	for _, o := range near {
		sum = sum.Add(o.Vel)
	}
	avg := sum.Scale(1 / float64(len(near)))
	if avg.Len() == 0 {
		return Vec2{}
	}
	return g.Steer(b, avg.Unit().Scale(g.MaxSpeed))
}

// Cohere is the pull-toward-the-middle rule: average the neighbours'
// positions and seek the point that comes out. Nobody stores that point
// and no two bodies compute the same one, because each body averages a
// different set of neighbours and leaves itself out.
func (g Gait) Cohere(b Body, near []Body) Vec2 {
	if len(near) == 0 {
		return Vec2{}
	}
	var sum Vec2
	for _, o := range near {
		sum = sum.Add(o.Pos)
	}
	return g.Seek(b, sum.Scale(1/float64(len(near))))
}

// Cut is the limit a gait puts on a force, and it is the same limit
// Steer already applies to one behavior: keep the direction, and if the
// length is more than this body can push with, set it to what it can.
// Adding several behaviors together produces a vector no single
// behavior could have produced, so a combination has to be cut too.
func (g Gait) Cut(f Vec2) Vec2 {
	if f.Len() > g.MaxForce {
		return f.Unit().Scale(g.MaxForce)
	}
	return f
}

$ go run ./cmd/herd -mode hand
herd: one body at 96.000,64.000 doing 1.800,0.600, max speed 2.4, max force 0.3
      neighbour radius 16
  neighbour      position       velocity          offset  distance          vote
          0 92.000,67.000   0.600,-2.000    4.000,-3.000     5.000  0.160,-0.120
          1 80.000,64.000    2.400,0.000    16.000,0.000    16.000   0.062,0.000
          2 104.000,70.000  -0.300,-1.600   -8.000,-6.000    10.000 -0.080,-0.060

  rule       what the three neighbours make       desired       steering  |steer|         force
  separate  votes add to 0.143,-0.180         1.490,-1.882  -0.310,-2.482    2.501 -0.037,-0.298
  align     mean velocity 0.900,-1.200        1.440,-1.920  -0.360,-2.520    2.546 -0.042,-0.297
  cohere    middle at 92.000,67.000           -1.920,1.440   -3.720,0.840    3.814  -0.293,0.066

  weighted 1.6, 1.0, 0.9: -0.365,-0.714, length 0.802
  cut to the gait's 0.3: -0.137,-0.267
  one tick later it is at 97.663,64.333 doing 1.663,0.333

Every column of the hand calculation is there, and one pair of rows repays a second look. Separation and alignment produce almost the same force, (−0.037, −0.298) against (−0.042, −0.297), from completely unrelated inputs: one is built from where three bodies are, the other from how three bodies are moving. They agree here by accident. Cohesion, meanwhile, points the other way entirely, because the middle of the crowd is behind and to the left while the crowd itself is drifting north.

That disagreement is normal, and it is the reason for the last two lines. Three forces that each obey a limit of 0.3, added with weights of 1.6, 1.0 and 0.9, come to 0.802, and a walker that can push at 0.802 is a different animal from the one that grazed in the last chapter. The weights say who is heard and the gait says how hard the body can push, and those are separate decisions. Cut keeps them apart, and it is the arithmetic Steer was already doing, lifted out so a sum can use it too.

// internal/field/near.go

// Query is how a body finds its neighbours. Build is given every body
// once a tick, before any body asks; Near answers for one of them with
// the indices of the bodies inside r of it, itself excluded, in the
// order those indices run. Count reports the distance comparisons made
// since the last Reset, which is the number that tells two
// implementations apart on any machine.
//
// The order in that contract is not decoration. Every rule in flock.go
// adds its neighbours up, floating-point addition gives a different
// answer for a different order, and a world that answers differently is
// a different world however fast it answered.
type Query interface {
	Build(bodies []Body)
	Near(bodies []Body, i int, r float64, dst []int) []int
	Count() int
	Reset()
}

// Everybody is the neighbour query written the obvious way: to find one
// body's neighbours, measure to every other body. It is correct, it is
// four lines, and the count it runs up is the reason the rest of this
// file exists.
type Everybody struct{ Tests int }

// Build has nothing to prepare: this query looks at the slice it is
// handed, every time it is asked.
func (e *Everybody) Build([]Body) {}

// Near appends the index of every body inside r of body i to dst and
// returns it. The loop runs in index order, so the answer comes back in
// index order without anybody having to arrange it.
func (e *Everybody) Near(bodies []Body, i int, r float64, dst []int) []int {
	dst = dst[:0]
	for j := range bodies {
		if j == i {
			continue
		}
		e.Tests++
		if bodies[i].Pos.Sub(bodies[j].Pos).Len() <= r {
			dst = append(dst, j)
		}
	}
	return dst
}

// cmd/herd/main.go — the tick

func (h *herd) tick() {
	h.q.Build(h.bodies)
	for i := range h.bodies {
		b := h.bodies[i]
		h.idx = h.q.Near(h.bodies, i, Radius, h.idx)
		near := field.Gather(h.bodies, h.idx, h.scratch)
		h.scratch = near

		f := walk.Separate(b, near).Scale(wSep).
			Add(walk.Align(b, near).Scale(wAli)).
			Add(walk.Cohere(b, near).Scale(wCoh))

		f = f.Add(h.wanders[i].Force(walk, b, h.rng).Scale(wWan))
		f = f.Add(h.rim(b).Scale(wRim))
		h.bodies[i].ApplyForce(walk.Cut(f))
	}
	for i := range h.bodies {
		h.bodies[i].Step()
	}
}

Two forces in that tick are not herd rules. The wander is the drifting heading from the last chapter, kept so a walker with nobody near it still moves like an animal. The rim is the edge of the field: inside fourteen pixels of it a walker wants to be travelling away. Both are ordinary steering forces and neither knows a herd exists. The program wraps the three-line sum in a switch on its -rule flag, so the next few runs can hear one rule at a time; every other line above is what it always runs.

$ go run ./cmd/herd -mode alone -n 120 -ticks 400 -shot yes
herd: 120 walkers on the seed 5 valley, 400 ticks, neighbour radius 16
  rules heard    neighbours   nearest  together   groups         frame
  none                 4.02     6.739     0.059       11  f42d95f4dcf1
  push apart           3.58     9.008     0.031        2  c92dba1ae064
  match heading       59.67     0.613     0.999        2  0c1cb97d16fd
  pull to middle      27.57     0.915    -0.139        6  298dcde7069c
  all three            5.95     8.411     0.951        3  b88eb16bed9e
wrote adrift.png
wrote separate.png
wrote align.png
wrote cohere.png
wrote herd.png

Read one row at a time and each rule confesses to exactly one thing. Push apart raises the distance to the nearest walker from the aimless run's 6.739 to 9.008 and does nothing else: agreement stays at 0.031, the number a crowd of strangers produces. separate.png is the valley evenly stippled with walkers, almost a lattice, no two of them near each other.

Match heading wins its own column outright at 0.999, which is 120 walkers travelling one way to within a tenth of a degree, and pays with the other three columns: nearly sixty neighbours each, and a nearest neighbour six tenths of a pixel off. Nothing in alignment has an opinion about space, so the crowd converges on one heading and then on one spot. align.png is an empty valley with two dense knots in it.

Pull to the middle fails most picturesquely. Agreement goes slightly negative, meaning a walker on average heads a little against its neighbours, because everyone is falling inward past everyone else. The groups column settles at 6 and stays there for two hundred ticks: six knots, frozen, with wide empty ground between them. At a radius of 16 cohesion can only pull a walker toward the crowd it has already found, so it never makes one herd out of six.

The last row has no column of its own and that is the point. 8.411 apart, which is better spacing than the aimless run manages. 0.951 agreement, within five hundredths of what pure alignment achieves. Three groups instead of eleven. Every one of those numbers comes out of a sum of three forces, none of which was asked for a herd, and none of which could have produced that row on its own.

// internal/field/flock_test.go

// BenchmarkNeighbours times one tick of the same crowd at four sizes
// through both queries, and reports the distance tests each one made.
// The nanoseconds belong to whatever machine ran it; the tests do not.
func BenchmarkNeighbours(b *testing.B) {
	for _, n := range []int{32, 128, 512, 2048} {
		for _, q := range []struct {
			name    string
			buckets bool
		}{{"everybody", false}, {"buckets", true}} {
			b.Run(fmt.Sprintf("%s/%d", q.name, n), func(b *testing.B) {
				c := newBenchCrowd(n, q.buckets)
				c.tick()
				c.q.Reset()
				b.ResetTimer()
				for i := 0; i < b.N; i++ {
					c.tick()
				}
				b.StopTimer()
				b.ReportMetric(float64(c.q.Count())/float64(b.N), "tests/tick")
			})
		}
	}
}

$ go test -run '^$' -bench 'BenchmarkNeighbours/everybody' -benchtime 200x ./internal/field/
goos: linux
goarch: amd64
pkg: theworld/internal/field
cpu: AMD Ryzen 7 3700X 8-Core Processor
BenchmarkNeighbours/everybody/32-16         	     200	      8568 ns/op	       992.0 tests/tick
BenchmarkNeighbours/everybody/128-16        	     200	     77756 ns/op	     16256 tests/tick
BenchmarkNeighbours/everybody/512-16        	     200	    759489 ns/op	    261632 tests/tick
BenchmarkNeighbours/everybody/2048-16       	     200	  10237126 ns/op	   4192256 tests/tick
PASS
ok  	theworld/internal/field	2.257s

These times were taken on the machine this chapter was written on and yours will read differently; the ratios travel, and the tests column is the same everywhere. The benchmark has a slot for a second query and the rest of the chapter fills it, so only the double loop is run here. The tests go 992, 16,256, 261,632, 4,192,256, which is 32×31, 128×127, 512×511 and 2048×2047: every quadrupling of the crowd multiplies the questions by sixteen exactly, with no measurement error in it because it is not a measurement.

The nanoseconds follow at a distance: 8,568 to 77,756 to 759,489 to 10,237,126, which is 9.1 then 9.8 then 13.5 times per quadrupling instead of sixteen. The gap is the fixed cost per body, three rules and an integration step, which is real work that does not grow with the crowd and which the quadratic term slowly buries. At 2,048 bodies the tick takes 10.2 milliseconds. This world runs at ten ticks a second, so that is a tenth of the budget spent on one flock, and 4,096 bodies would take about 41 milliseconds and 8,192 about 163, which is more than a whole tick.

// internal/field/near.go

// Buckets is the neighbour query on a grid. Every cell of the world's
// own grid holds the indices of the bodies standing in it, rebuilt once
// a tick, and a body's neighbours are looked for in its cell and the
// eight around it and nowhere else. That is only correct while a cell is
// at least as wide as the radius being asked for, and Near refuses to
// answer quietly when it is not.
type Buckets struct {
	Cols, Rows int
	T          float64 // cell size, in world pixels

	cell  [][]int // one list of body indices per cell, in row order
	cand  []int   // this query's candidates, reused so nothing allocates
	Tests int
}

// Build empties every bucket and refills it from the bodies, in index
// order, so each bucket's list is sorted before anybody reads it. The
// slices keep their capacity, so after the first tick this allocates
// nothing.
func (bk *Buckets) Build(bodies []Body) {
	for c := range bk.cell {
		bk.cell[c] = bk.cell[c][:0]
	}
	for i := range bodies {
		cx, cy := bk.at(bodies[i].Pos)
		bk.cell[cy*bk.Cols+cx] = append(bk.cell[cy*bk.Cols+cx], i)
	}
}

// at is the cell a position stands in. Off the grid reads as the nearest
// edge cell, which can only ever bring distant bodies into an edge
// bucket, never take a near one out of it.
func (bk *Buckets) at(p Vec2) (int, int) {
	return clamp(int(p.X/bk.T), 0, bk.Cols-1), clamp(int(p.Y/bk.T), 0, bk.Rows-1)
}

// Near gathers the candidates out of nine buckets and measures to each.
// Everything the double loop did is still here; what has gone is the
// bodies that were never candidates.
func (bk *Buckets) Near(bodies []Body, i int, r float64, dst []int) []int {
	if r > bk.T {
		panic("field: a radius wider than a bucket needs more than nine buckets")
	}
	dst = dst[:0]
	cx, cy := bk.at(bodies[i].Pos)

	bk.cand = bk.cand[:0]
	for gy := cy - 1; gy <= cy+1; gy++ {
		if gy < 0 || gy >= bk.Rows {
			continue
		}
		for gx := cx - 1; gx <= cx+1; gx++ {
			if gx < 0 || gx >= bk.Cols {
				continue
			}
			bk.cand = append(bk.cand, bk.cell[gy*bk.Cols+gx]...)
		}
	}

	for _, j := range bk.cand {
		if j == i {
			continue
		}
		bk.Tests++
		if bodies[i].Pos.Sub(bodies[j].Pos).Len() <= r {
			dst = append(dst, j)
		}
	}
	return dst
}

Nothing about the rules changed and nothing about the tick changed. The same three functions receive the same kind of list from a different Query, and that list holds precisely the same walkers: the nine buckets provably contain every body inside the radius, and the distance test at the bottom throws out the candidates that turned out to be too far.

The same walkers ought to mean the same world. They do not.

$ go run ./cmd/herd -mode sweep -rule herd -n 120 -ticks 400
herd: 120 walkers on the seed 5 valley, all three rules, weighted
      the same scene through every body, nine buckets, and nine buckets unordered
      the two same? columns are the frame and then the numbers behind it
  tick   every body: frame       numbers   buckets same?  unordered same?     tests each
     0  edd70571b572  efa4abd607952d18   yes  yes     yes  yes            0      0
    40  39ffcc25d74b  c3efc83c716bbe67   yes  yes     yes  NO         14280   1448
    80  737752fc4480  16611ceb4f5f9c5f   yes  yes     yes  NO         14280   2614
   120  027b773e8926  4d694be4caa8484e   yes  yes     yes  NO         14280   2594
   160  4185b5ba16f4  11b627fd32ce7e52   yes  yes     yes  NO         14280   1762
   200  64bbf42c23ab  8b91972a8701cde8   yes  yes     NO   NO         14280   3066
   240  1a0ccf5c1b7b  9413aff316d25737   yes  yes     NO   NO         14280   3234
   280  407c313a8606  bd73c504678050b9   yes  yes     NO   NO         14280   2032
   320  c8c2d3adbd65  64f455525f23da44   yes  yes     NO   NO         14280   2584
   360  50a57b8210ce  2e8487d294b274a9   yes  yes     NO   NO         14280   3876
   400  b88eb16bed9e  af85abbb3b768594   yes  yes     NO   NO         14280   1880
      over 400 ticks the ordered buckets disagreed on 0 of them
      the unordered buckets disagreed on 400

Zero disagreements in 401 frames and 401 state hashes, against 400 for the version that skipped the sort. The unordered run's frame column is instructive on its own: at tick 160 it still reads yes, and sampling every fortieth tick would have let it through. The state hash catches it at tick 1, which is the argument for hashing the numbers and not only the picture.

The tests columns say what the trade bought. Every body measures 14,280 distances on every tick, unchanging, because that count does not depend on where anybody is standing. The buckets measure between 1,448 and 3,876, and the variation is the crowd itself: a bunched herd shares cells and gives more to check, a strung-out one less. The work now follows the crowd instead of the roster.

// internal/field/flock_test.go

// TestQueriesAgree is the claim the grid makes, written as a test: the
// crowd steered from nine buckets is the crowd steered from every body,
// bit for bit, at every body, after three hundred ticks. A query that
// answers faster and differently has not made the world faster; it has
// made a different world.
func TestQueriesAgree(t *testing.T) {
	slow := newBenchCrowd(512, false)
	fast := newBenchCrowd(512, true)
	for i := 0; i < 300; i++ {
		slow.tick()
		fast.tick()
	}
	for i := range slow.bodies {
		s, f := slow.bodies[i], fast.bodies[i]
		if s.Pos != f.Pos || s.Vel != f.Vel {
			t.Fatalf("body %d after 300 ticks: every body has it at %v doing %v, the buckets at %v doing %v",
				i, s.Pos, s.Vel, f.Pos, f.Vel)
		}
	}
	if slow.q.Count() <= fast.q.Count() {
		t.Errorf("the buckets measured %d distances and every body %d", fast.q.Count(), slow.q.Count())
	}
	t.Logf("300 ticks, 512 bodies: every body measured %d distances, the buckets %d",
		slow.q.Count(), fast.q.Count())
}

$ go test -count=1 -v -run TestQueriesAgree ./internal/field/
=== RUN   TestQueriesAgree
    flock_test.go:134: 300 ticks, 512 bodies: every body measured 78489600 distances, the buckets 3436228
--- PASS: TestQueriesAgree (0.37s)
PASS
ok  	theworld/internal/field	0.369s

Seventy-eight million distance measurements against three and a half million, and 512 walkers standing on identical coordinates at the end of it. Now run the benchmark with both queries in it.

$ go test -run '^$' -bench BenchmarkNeighbours -benchtime 200x ./internal/field/
goos: linux
goarch: amd64
pkg: theworld/internal/field
cpu: AMD Ryzen 7 3700X 8-Core Processor
BenchmarkNeighbours/everybody/32-16         	     200	      8589 ns/op	       992.0 tests/tick
BenchmarkNeighbours/buckets/32-16           	     200	     15472 ns/op	       446.4 tests/tick
BenchmarkNeighbours/everybody/128-16        	     200	     77300 ns/op	     16256 tests/tick
BenchmarkNeighbours/buckets/128-16          	     200	     92141 ns/op	      2584 tests/tick
BenchmarkNeighbours/everybody/512-16        	     200	    760794 ns/op	    261632 tests/tick
BenchmarkNeighbours/buckets/512-16          	     200	    406764 ns/op	     10252 tests/tick
BenchmarkNeighbours/everybody/2048-16       	     200	  10216898 ns/op	   4192256 tests/tick
BenchmarkNeighbours/buckets/2048-16         	     200	   1749183 ns/op	     42367 tests/tick
PASS
ok  	theworld/internal/field	2.714s

760,794 nanoseconds a tick against 406,764 at 512 bodies, and 10,216,898 against 1,749,183 at 2,048: a factor of 1.9 where the crowd is middling and 5.8 where it is largest, which is where the tick budget had started to look uncomfortable.

The 32-body rows are the honest part of that table. The buckets take 15,472 nanoseconds where the double loop takes 8,589, so on a small crowd the fix costs 80% more than what it replaced. Emptying sixteen cell lists, filling them, and putting a short candidate list in order once per body all cost something, and at 32 bodies there was never enough waste to pay for it. The curves cross somewhere around 250 walkers, and past that the grid pulls away and does not come back.