Fire Crosses the Grid
A cell changes because of neighbours
Ten chapters of this volume have written the same kind of law. Something is at a position, several things push on it, the pushes are added into one accumulator, and the position changes. That covers a leaf on a draught, a plank riding a pool, a raindrop, a walker startling, a herd closing ranks. It does not cover a fire.
A fire has no position. It is never in one place and then another; it is a condition of ground, and ground does not travel. A rule decides one cell and writes one cell: its own. Every cell reads its neighbours as they stood before the sweep began, out of a copy nothing is writing to, and no cell reaches out to change another. Fire spreading is not a burning square setting the next one alight; it is a dry square looking round and catching.
The Hollow has had those squares since chapter 3. Twelve across, eight down, rock and soil and water, built from a seed, and for thirty-one chapters they have been scenery: something to walk on, a wall for a walker to bump into, a colour for the renderer. Nothing has ever happened to them except one soil cell every four seconds turning to water when the spring seeps.
This volume has two halves and they can be named plainly. A body composes forces: it asks what is pushing on me, adds the answers, and moves. A cell composes neighbours: it asks what is around me, reads the answers, and becomes something. The second half has one trap the first does not, and an earlier flood rule fell into it on its first afternoon. Flooding every soil cell that touched water, in a single pass over the grid, put the whole valley under in one tick, because a cell the loop had already flooded was water by the time its eastern neighbour was examined. A tick has to be an instant every law sees identically.
This chapter builds one small package, three laws written against it, and a digest of every sweep. Fire crosses dry grass with a chance drawn from a seeded stream. The same fire burns under a wind field. Water runs downhill because height becomes one value per cell. A sickness runs on the ground under a moving herd.
Two sheets for one sweep
The machinery is smaller than the laws it carries. A sheet is a grid of small numbers with a second grid behind it. Rules read the first and can reach nothing else; the sweep writes the second and nobody has read it yet; at the end of the sweep the two change places. Put both slices out of reach of everything outside the package and the promise stops being a comment that asks nicely.
// internal/cells/sheet.go
// Package cells is the other half of this world's arithmetic. Package
// field takes one body and adds up everything pushing on it. This one
// takes one cell and looks at everything standing around it.
package cells
// State is what one cell is right now. It is a small number, and this
// package attaches no meaning to any of them: fire, water and sickness
// each name their own.
type State uint8
// Off is what a neighbour past the edge of the sheet answers. No rule
// may produce it and every rule may test for it, so a cell on the rim
// asks its four neighbours exactly the way a cell in the middle does
// and never indexes outside the slice.
const Off State = 255
// Step is one move to a neighbour.
type Step struct{ DX, DY int }
// Steps are the four neighbours of any cell, in the order every rule in
// this book walks them. The order is fixed because a rule that draws a
// random number once per burning neighbour draws them in the order it
// met them, and a world that meets them in another order is a different
// world.
var Steps = [4]Step{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
// Rule is one cell's law: given the sheet and a cell on it, what that
// cell is next. A rule may read anything on the sheet and may write
// nothing.
type Rule func(s *Sheet, x, y int) State
// Sheet is a grid of states with a second grid behind it: the one every
// rule reads and the one every sweep writes. Neither slice can be
// reached from outside this package.
type Sheet struct {
W, H int
now []State
next []State
}
// At is the state of one cell as it stood when this sweep began.
func (s *Sheet) At(x, y int) State {
if !s.In(x, y) {
return Off
}
return s.now[y*s.W+x]
}
// Sweep applies one rule to every cell and reports how many came out
// different from how they went in. Every cell is read out of the buffer
// the sweep started with and written into the other one, so no rule can
// see a neighbour that has already moved on, and the two change places
// once the last cell is written.
func (s *Sheet) Sweep(r Rule) int {
changed := 0
for y := 0; y < s.H; y++ {
for x := 0; x < s.W; x++ {
i := y*s.W + x
v := r(s, x, y)
s.next[i] = v
if v != s.now[i] {
changed++
}
}
}
s.now, s.next = s.next, s.now
return changed
}
At is the whole guarantee. It reads now and only
now, and now is not the slice being written this sweep, so a
rule asking about its western neighbour gets that neighbour as it was when the sweep
started even if the sweep passed over it four cells ago. The old flood is not merely
discouraged here; a rule cannot write the thing it is reading, because it cannot write
at all. It returns a value and the sweep decides where that value goes.
Off earns its place at the rim. Without it every rule needs bounds checks
around every neighbour lookup, and four copies of a bounds check is where an
off-by-one goes to live. With it, a cell in the corner asks the same four questions as a
cell in the middle and gets two answers that no rule will match against anything.
Fire needs five states and takes them from the ground it is standing on: rock will not burn, open water will not burn, soil is fuel. A cell that catches burns for two ticks, flame and then embers, and embers still light a neighbour.
// cmd/spread/main.go
const (
Bare cells.State = iota // rock: nothing to burn
Wet // open water: nothing to burn
Dry // fuel, standing and unburnt
Ash // burnt out, and it stays burnt out
Ember // the second tick alight
Flame // the first
)
// alight reports whether a cell can light a neighbour this tick.
func alight(v cells.State) bool { return v == Flame || v == Ember }
fire := func(sh *cells.Sheet, x, y int) cells.State {
switch v := sh.At(x, y); v {
case Flame:
return Ember // the flame drops to embers
case Ember:
return Ash // and the embers go out
case Dry:
default:
return v // water, rock and ash have nothing left to do
}
for _, d := range cells.Steps {
if !alight(sh.At(x+d.DX, y+d.DY)) {
continue
}
if rng.Float64() < chance(x, y, d) {
return Flame
}
}
return Dry
}$ go run ./cmd/spread -mode fire -ticks 20 -from 0 -to 3
spread: fire on the seed 5 valley, 44 cells of fuel, lit at (5,1)
fire seed 4, base catch 0.55, still air, writing every cell every sweep
# rock ~ water " dry grass * flame + embers . ash
tick alight dry ash changed sheet
0 1 43 0 0 5b37763066ef
############
#""""*"""""#
#""""""""""#
#"~~~~~""""#
#"~~~~~~"""#
#"""~~~~"""#
#"""~""""""#
############
1 2 42 0 2 4dcfcb573019
############
#"""*+"""""#
#""""""""""#
#"~~~~~""""#
#"~~~~~~"""#
#"""~~~~"""#
#"""~""""""#
############
2 3 40 1 4 9a7020c52666
############
#"""+.*""""#
#""""*"""""#
#"~~~~~""""#
#"~~~~~~"""#
#"""~~~~"""#
#"""~""""""#
############
3 5 37 2 6 1b44be035e92
############
#""*..+*"""#
#"""*+"""""#
#"~~~~~""""#
#"~~~~~~"""#
#"""~~~~"""#
#"""~""""""#
############
4 5 35 4 7 abb80a37661e
5 6 31 7 9 fd44e525dd25
6 7 28 9 9 3a5170f9eebf
7 5 26 13 9 bf32546df58c
8 4 24 16 7 82a81fb0d07d
9 5 21 18 7 cad39ca7036d
10 7 17 20 9 7d749253c97c
11 8 13 23 11 09f3716d8085
12 7 10 27 11 26c7f6b7a22c
13 7 6 31 11 e792faba1fc6
14 6 4 34 9 f44c9ed3fe47
15 3 3 38 7 87b4e1f35766
16 2 2 40 4 5c20b8d5c35e
17 1 2 41 2 ac0467237d5c
20 0 2 42 0 9aaf065e4ffc
42 of 44 cells of fuel burnt, 2 still standing, out by tick 17
the burnt cells average +0.76 cells east of the spark
every sweep hashed and folded together: 8cf9c43cca88103b
Follow cell (5, 1), the one the flame was set in. Tick 1 it is embers, tick 2 it is
ash, and it stays ash for the rest of the run. Nothing else could happen to it: the rule
has no arrow leaving Ash. Meanwhile the front leaves it. At tick 1 the cell
to its west has caught; at tick 2 the cell to its east and the one directly south; by
tick 13 there are six cells of fuel left in the valley.
The pond does the work no code did. Rows 3 and 4 are mostly water and the fire has to go round them, and the whole burn takes seventeen ticks to cross ten cells of grass. Two of those cells are never reached at all, and the summary counts them.
The last line is the run's whole history in sixteen characters. The sheet is hashed at every one of the twenty sweeps and each digest is folded into the one before it, so two runs that agree at every printed tick and differ at a tick nobody printed still come out with different chains. That is cheap insurance on a rule that draws random numbers: the printed rows are a summary, and a summary is exactly the sort of thing a bug hides inside.
Figure 34.1 — the sweep, for one cell of ninety-six. Everything a rule can see is on the left, the one value it produces lands on the right, and the two slices trade names only after the last cell has been written.
The chance a jump succeeds is one number so far, and one number is the same everywhere. But the valley already carries a force written down cell by cell: a wind lies over this exact grid, an eastward push scaled by what each kind of ground lets past and spilled sideways off every rock wall. A cellular automaton lives on the cells themselves, so it takes the wind whole out of the cell it is standing in instead of blending four of them the way a body at a float position had to.
// cmd/spread/main.go
// gust is how much of the wind at one cell pushes along one step. The
// four steps run along a row or a column, so this is one component of
// the wind with a sign on it and no arithmetic anybody has to be
// taught.
func gust(w field.Vec2, d cells.Step) float64 {
return w.X*float64(d.DX) + w.Y*float64(d.DY)
}
// chance is how likely a neighbour alight in direction d is to light
// the cell at (x, y). The fire travels the opposite way to the step
// that found the neighbour, so the wind is asked about the reverse
// of d: a neighbour to the west lights this cell on an eastward
// gust.
chance := func(x, y int, d cells.Step) float64 {
if !wind {
return catch
}
travel := cells.Step{DX: -d.DX, DY: -d.DY}
p := catch * (1 + push*gust(l.Cell(x, y), travel))
if p < 0 {
return 0
}
if p > 1 {
return 1
}
return p
}$ go run ./cmd/spread -mode hand -at 6,1
spread: one cell of the seed 5 valley, and the four questions it asks
cell (6,1) is dry grass with a flame west of it, wind here 0.500,0.150
catch 0.55 in still air, the wind leaning at 1.0
step neighbour the fire would come gust chance
east (7,1) dry grass travelling west -0.500 0.275
west (5,1) flame travelling east +0.500 0.825
south (6,2) dry grass travelling north -0.150 0.468
north (6,0) rock travelling south +0.150 0.632
only the west neighbour is alight, so this cell draws once a tick
fire seed 4 draws 0.3859 first, and 0.3859 is under 0.825
Read the sign column first, because getting it backwards is a mistake that still
produces a plausible-looking fire. The loop walks to a neighbour along d;
the fire comes the other way, along the reverse of d. A flame in the west
arrives on an eastward gust, so the step the wind is asked about is east, the wind's own
0.500 counts in full, and 0.55 becomes 0.825. From the east it would arrive against the
wind and be worth 0.275, three times less likely, out of the same base number.
The north row is arithmetic about a rock face and will never be used, because the rule
tests alight before it asks about chance. The 0.150 in it is the spill
every cell beside a wall keeps: air that cannot go through rock goes along it,
and here that sideways component is the small difference between the north and south
entries.
$ go run ./cmd/spread -mode fire -wind -ticks 20 -from 20 -to 20
spread: fire on the seed 5 valley, 44 cells of fuel, lit at (5,1)
fire seed 4, base catch 0.55, wind leaning at 1.0, writing every cell every sweep
# rock ~ water " dry grass * flame + embers . ash
tick alight dry ash changed sheet
0 1 43 0 0 5b37763066ef
1 2 42 0 2 1b10532c3598
2 3 40 1 4 3b49e2316044
3 5 37 2 6 90d1f7f8cf32
4 5 35 4 7 721e13710a8b
5 6 31 7 9 21f384f03562
6 7 28 9 9 cb9906c0684c
7 5 26 13 9 5f3519f65bb0
8 4 24 16 7 7a39fe1eb571
9 4 22 18 6 75d92ad18e50
10 4 20 20 6 9bebcd84e82d
11 2 20 22 4 7d41005e980b
12 1 19 24 3 8e81a9b7e109
13 1 19 24 1 fb2cb0aed5e0
20 0 19 25 0 a02e17427f58
############
#""""......#
#""""......#
#"~~~~~....#
#"~~~~~~...#
#"""~~~~...#
#"""~"""...#
############
25 of 44 cells of fuel burnt, 19 still standing, out by tick 13
the burnt cells average +3.20 cells east of the spark
every sweep hashed and folded together: 7df99814795dd0c4
The map is the result and it barely needs reading. Columns 1 to 4 are standing grass from the northern rim to the southern one, top to bottom, and the fire was lit in column 5. It never once went west. The other three survivors are the pocket at (5, 6), (6, 6) and (7, 6), tucked behind the pond where the only approach was from the west. Four columns of unburnt fuel, and the firebreak is made of air nobody can see.
The numbers say the same thing twice. The burnt cells average 3.20 cells east of the spark where the still-air burn averaged 0.76, and this fire went out four ticks sooner having taken 25 cells against 42. That second number surprises people, so be exact about it: the wind did not add chance to this world, it moved chance around. Three of the four directions were made harder so that one could be made easier, and a front that can only advance one way runs out of fuel the moment it reaches the rim. Wind makes a fire that travels, not a fire that eats more.
One run of a rule with a coin in it is an anecdote. The same spark on the same ground with a different stream behind it is a different fire, and the honest way to describe a stochastic automaton is to light it many times and look at the pile.
$ go run ./cmd/spread -mode many -runs 60
spread: 60 fires on the seed 5 valley, lit at 5,1, catch 0.55, 44 cells of fuel
fire seeds 1 to 60
air mean burnt least most under 5 over 30 mean cells east
still air 33.3 3 44 1 43 1.16
wind leaning at 1.0 28.3 18 43 0 17 2.63
Both eastings survive sixty runs, and the gap between 1.16 and 2.63 is the wind's
signature rather than one lucky picture. The least column carries the other
half of the story. In still air a fire can fizzle at three cells; in wind the worst of
sixty still took eighteen, because a front that has one strongly favoured direction
keeps finding somewhere to go. A directional bias makes a fire smaller on average and far
harder to kill.
A cell with one alight neighbour catches with probability 0.55, so it escapes with 0.45. Two alight neighbours mean two draws, and it escapes both only if the first fails and the second fails too: 0.45 multiplied by 0.45, which is 0.2025. Three of them leave 0.45 × 0.45 × 0.45 = 0.0911. Escaping gets harder by the same factor each time a neighbour is added, so the count that matters is how many neighbours are alight, not which.
escapes = (1 − p)k, so catches = 1 − (1 − p)k
The same arithmetic covers time as well as neighbours. A cell burns for two ticks, so one neighbour gets two attempts and its total chance of passing the fire on is 1 − 0.452 = 0.7975. Halve the burn to a single tick and that drops to 0.55, and it is exactly that difference that decides whether a fire crosses a field or dies in the square it was lit in.
Walk the base number up and the whole valley changes character. Sixty fires at each setting, counting how many fizzled under five cells and how many took more than thirty:
$ go run ./cmd/spread -mode curve -runs 60
spread: 60 fires at each catch, seed 5 valley, lit at 5,1, still air
catch mean burnt under 5 over 30 most
0.20 3.6 46 0 21
0.25 5.5 39 0 22
0.30 8.6 24 0 30
0.35 12.9 16 4 38
0.40 17.6 11 12 42
0.45 24.2 5 19 44
0.50 28.7 1 29 44
0.55 33.3 1 43 44
0.60 36.6 0 48 44
0.70 39.6 0 55 44
0.80 43.0 0 60 44
The two counted columns cross over between 0.35 and 0.40 while the mean climbs steadily through them, and the mean is the column to distrust. At 0.30 the average fire burns 8.6 cells and almost no fire burns 8.6 cells: 24 of the 60 died under five, and one of them took thirty. The average is a number sitting in a gap between the two things that actually happen. Below the crossover a fire is a nuisance that usually goes out on its own; above it, a fire is an event. Nobody typed that transition. It came out of one probability and the fact that a square has four sides.
Ninety-six cells are swept every tick and on a quiet tick two of them change. Writing all ninety-six to record two looks like waste, and the thrifty version of the sweep is one line different: work out the value, and write it only if it is not the value already sitting there.
// internal/cells/sheet.go
// SweepThrift is the sweep with the writing cut down: nearly every cell
// comes out of a rule exactly as it went in, so this one writes only
// the cells that changed.
func (s *Sheet) SweepThrift(r Rule) int {
changed := 0
for y := 0; y < s.H; y++ {
for x := 0; x < s.W; x++ {
i := y*s.W + x
v := r(s, x, y)
if v != s.now[i] {
s.next[i] = v
changed++
}
}
}
s.now, s.next = s.next, s.now
return changed
}$ go run ./cmd/spread -mode fire -thrift -ticks 12 -from 2 -to 3
spread: fire on the seed 5 valley, 44 cells of fuel, lit at (5,1)
fire seed 4, base catch 0.55, still air, writing only the cells that changed
# rock ~ water " dry grass * flame + embers . ash
tick alight dry ash changed sheet
0 1 43 0 0 5b37763066ef
1 2 42 0 2 4dcfcb573019
2 3 40 1 4 9a7020c52666
############
#"""+.*""""#
#""""*"""""#
#"~~~~~""""#
#"~~~~~~"""#
#"""~~~~"""#
#"""~""""""#
############
3 6 37 1 6 58c36cab0de8
############
#""*.++*"""#
#"""*+"""""#
#"~~~~~""""#
#"~~~~~~"""#
#"""~~~~"""#
#"""~""""""#
############
4 6 35 3 8 6c0cc7624c3e
5 9 31 4 10 5f482060efe7
6 11 28 5 12 689ea0fc6181
7 10 26 8 13 7cd4078ff51f
8 12 24 8 12 d71d2f10ea95
9 13 21 10 15 b951d01c798d
10 17 17 10 17 4aba6936dccf
11 18 13 13 21 0833b809203e
12 20 10 14 21 73e78cb19093
14 of 44 cells of fuel burnt, 10 still standing, out by tick 12
the burnt cells average +1.86 cells east of the spark
every sweep hashed and folded together: 86a8511a031d6e01
Ticks 0, 1 and 2 match the working run digit for digit. Tick 3 does not, and the ash column names the damage before the maps do: the correct run has two cells of ash at tick 3 and this one has one.
Put the two maps side by side at cell (5, 1), the square the fire was lit in. At
tick 2 it is ., ash. At tick 3 it is +, embers. Nothing in this
program turns ash back into embers. Read the rule again and there is no arrow leaving
Ash at all; the only line that can produce Ember is the one
that reads Flame, and that cell has not been flame since tick 1.
Tick 1 is the answer. That is precisely when (5, 1) was embers. The value did not come from the rule and it did not come from this tick: it is the state from two sweeps ago, still sitting in the buffer, because the buffer being written is not a blank sheet. It is the sheet from the tick before last, handed back by the swap. The thrifty sweep writes the cells that changed and leaves every other cell holding a value that was correct two ticks ago, and a cell whose value has changed once and then settled is exactly the cell that gets resurrected.
Left alone, that never ends:
$ go run ./cmd/spread -mode fire -thrift -ticks 200 | tail -8
196 24 0 20 20 9a9222258125
197 20 0 24 24 52207a6ff331
198 24 0 20 20 9a9222258125
199 20 0 24 24 52207a6ff331
200 24 0 20 20 9a9222258125
20 of 44 cells of fuel burnt, 0 still standing, out by tick 200
the burnt cells average +1.40 cells east of the spark
every sweep hashed and folded together: 481167d3aaa7e730
Every cell of fuel has been consumed, twenty or twenty-four of them are alight depending on which tick you look at, and the sheet has become a two-position clock: ticks 196, 198 and 200 carry one digest and 197 and 199 carry another, forever. The double buffer that makes the read side safe has turned into a machine for playing the tick before last back into the present, at exactly the period two slices taking turns would give it.
The general form of the mistake outlives fire. Double buffering promises that no reader sees a half-finished state; it promises nothing whatever about the half of the buffer you did not write. Any scheme where the destination is recycled has the same obligation: write every cell, or bring the destination up to date before writing any of them. The earlier flood bug was a rule reading its own output. This one reads correctly all the way through and writes an incomplete answer, which is harder to see, because the symptom turns up one tick after the cause.
Water with a height
Fire is a rule with a coin in it. The next one has no coin at all, and it is the same machinery. Water spreads into a neighbouring cell when there is water beside it and that water is higher up. The second clause is the entire law, and this world has not been able to state it, because no cell of The Hollow has ever had a height.
Giving it one costs a short walk over the grid. The pond is the bottom of the valley, so call open water zero and let the ground rise by one for every cell you have to cross to reach it. Rock is above everything. That single number per cell is the same sort of object the wind was, one value written down for every square, and it is computed once before the first sweep because nothing in this section moves the rock.
// cmd/spread/main.go
// heights is the one number per cell this world did not have: how far
// the ground stands above the water line, counted in cells you would
// have to cross to reach open water. The pond is the bottom of the
// valley at 0, the ground rises one step for every cell away from it,
// and the rim is above everything.
func heights(g *sim.Grid) []int { ... }
downhill := func(sh *cells.Sheet, x, y int) cells.State {
if sh.At(x, y) != Land {
return sh.At(x, y)
}
for _, d := range cells.Steps {
nx, ny := x+d.DX, y+d.DY
if sh.At(nx, ny) != Pool {
continue
}
if flat || h[ny*Cols+nx] > h[y*Cols+x] {
return Pool
}
}
return Land
}$ go run ./cmd/spread -mode water -ticks 8 -from 5 -to 5
spread: water on the seed 5 valley, a cell goes under only when a wet neighbour stands above it
the spring runs from (10,1), 6 cells above the water line
how far every cell stands above the water line
# # # # # # # # # # # #
# 3 2 2 2 2 2 3 4 5 6 #
# 2 1 1 1 1 1 2 3 4 5 #
# 1 0 0 0 0 0 1 2 3 4 #
# 1 0 0 0 0 0 0 1 2 3 #
# 2 1 1 0 0 0 0 1 2 3 #
# 3 2 1 0 1 1 1 2 3 4 #
# # # # # # # # # # # #
tick water changed sheet
0 16 0 a57358819394
1 19 2 f1bce2838bd3
2 22 3 b0cd53492da1
3 26 4 bfc640b9f782
4 30 4 8a74066b9715
5 33 3 641c7a0ded88
############
#.....~~~~~#
#.....~~~~~#
#.~~~~~~~~~#
#.~~~~~~~~~#
#...~~~~...#
#...~......#
############
8 33 0 641c7a0ded88
every sweep hashed and folded together: 978e7fd2bfce33d8
Two things happen in that run and only one of them is the spring. The pond itself never moves. Every cell touching it stands at 1 while the pond stands at 0, so no soil cell anywhere has a wet neighbour above it, and the rule refuses every single time it is asked. A pond at the bottom of a bowl staying where it is required no special case: it fell out of a comparison.
The spring at (10, 1) is at height 6, and the water works its way down one step per tick, which the height table lets you predict before running anything. A cell at height 5 goes under on tick 1, height 4 on tick 2, and a cell at height n goes under on tick 6 − n. It runs out at tick 5, when the last cells at height 1 go under and the pond below them is already water, so the sheet stops changing and repeats its digest. The water took every route from the spring to the pond that runs downhill the whole way, and left everything west of that fan, and the whole southern shore, exactly as it found it.
Delete the height comparison and this is the old flood exactly, which is what the
flat flag does. It prints the same height table first, so skip past the
eleven lines of it:
$ go run ./cmd/spread -mode water -flat -ticks 10 -from 4 -to 4 | tail -n +12
tick water changed sheet
0 16 0 a57358819394
1 35 18 d9d11ee44c20
2 51 16 b6d871660960
3 59 8 115c97c19a69
4 60 1 294d3bf66c25
############
#~~~~~~~~~~#
#~~~~~~~~~~#
#~~~~~~~~~~#
#~~~~~~~~~~#
#~~~~~~~~~~#
#~~~~~~~~~~#
############
10 60 0 294d3bf66c25
every sweep hashed and folded together: 115dde4ed6477968
Sixty water cells, every square of the interior, in four sweeps. The earlier version got the whole valley in one tick because its bug let the flood race ahead of the scan; corrected, it still got everything, because a rule that floods any soil beside any water is a rule that fills a closed basin and stops only at the rim. That law was replaced by the timed spring for a reason nobody wrote down at the time, and the reason has a name now. It was missing a height.
Taint under 120 walkers
Both automata so far have been about terrain, and terrain is where a rule of this kind is easiest to see. The case that reaches further is a rule on the cells that something standing on them can read. A hundred and twenty animals bunch and turn on this same grid, each at a float position with a velocity, none of them aware that a cell exists. Lay a sheet under them.
The ground's states are a countdown: a taint is how many more ticks this square can pass the sickness on, and zero is clean. A sick creature fouls whatever square it is standing in. Fouling fades by one a tick, and a clean cell beside a fouled one may pick it up, which gives contamination a small life of its own between visits.
// cmd/herd/main.go
// taint is the whole of the ground's law: fouling fades by one tick
// a tick, and clean ground beside fouled ground may pick it up.
taint := func(sh *cells.Sheet, x, y int) cells.State {
if v := sh.At(x, y); v > Clean {
return v - 1
}
for _, d := range cells.Steps {
if v := sh.At(x+d.DX, y+d.DY); v != cells.Off && v > Clean {
if rng.Float64() < Drift {
return 1
}
}
}
return Clean
}// cmd/herd/main.go — one tick, in the order it has to happen
for t := 1; t <= ticks; t++ {
h.tick()
// Every sick creature fouls the ground it is standing on.
for i := range h.bodies {
if who[i] == Sick {
cx, cy := cellOf(h.bodies[i])
sheet.Set(cx, cy, Foul)
}
}
// Every creature then reads the one cell it is standing on.
for i := range h.bodies {
cx, cy := cellOf(h.bodies[i])
switch who[i] {
case Well:
if sheet.At(cx, cy) > Clean && rng.Float64() < Take {
who[i], left[i] = Sick, Ill
}
case Sick:
if left[i]--; left[i] <= 0 {
who[i] = Over
}
}
}
sheet.Sweep(taint)
}$ go run ./cmd/herd -mode sick -rule herd -n 120 -ticks 400
herd: 120 walkers on the seed 5 valley, all three rules, weighted
one sick at tick 0, 60 ticks ill, 0.20 to catch on fouled ground, 0.04 to drift a cell
tick well sick over fouled ground herd
0 119 1 0 0 2ea9ab9198d1 efa4abd607952d18
40 43 77 0 39 817b5a8591de c3efc83c716bbe67
80 5 83 32 41 b638ebb7c044 16611ceb4f5f9c5f
120 0 14 106 18 d3def7d70366 4d694be4caa8484e
160 0 1 119 1 1cdb19a98443 11b627fd32ce7e52
200 0 0 120 0 2ea9ab9198d1 8b91972a8701cde8
240 0 0 120 0 2ea9ab9198d1 9413aff316d25737
280 0 0 120 0 2ea9ab9198d1 bd73c504678050b9
320 0 0 120 0 2ea9ab9198d1 64f455525f23da44
360 0 0 120 0 2ea9ab9198d1 2e8487d294b274a9
400 0 0 120 0 2ea9ab9198d1 af85abbb3b768594
every sweep hashed and folded together: 3c0319f841b9faff
One animal was sick at tick 0 and nothing else was arranged. The sick column runs up to
83 by tick 80 and is back to 14 by tick 120, the over column climbs to all 120, and the
fouled column tops out on the same tick the sickness does, at 41 of the 96 squares. By
tick 200 the ground's digest is 2ea9ab9198d1 again, which is what it was at
tick 0: the valley is clean, because a taint is a countdown and countdowns run out.
The herd column is the walkers themselves, hashed over every position and
velocity, and it is in the table to make one thing checkable. A walker wanders out of
stream 3 and the sickness draws from stream 35, so an epidemic laid over a herd takes no
number out of the sequence the walking uses. Retune the sickness, or move it to another
stream, and that column does not budge: the animals go where they were going before
anybody fell ill.
Run the same seed with the herd rules switched off and the animals scatter instead of bunching:
$ go run ./cmd/herd -mode sick -rule none -n 120 -ticks 400
herd: 120 walkers on the seed 5 valley, no herd rules at all
one sick at tick 0, 60 ticks ill, 0.20 to catch on fouled ground, 0.04 to drift a cell
tick well sick over fouled ground herd
0 119 1 0 0 2ea9ab9198d1 efa4abd607952d18
40 59 61 0 40 85ebc890fa7d c84974c1e335145f
80 9 80 31 62 d42de1a3331b f376651e355fff15
120 0 29 91 33 e40acdc745b1 145cbe7829a5e617
160 0 2 118 2 a867232718cb f71e43f68c1d80e9
200 0 0 120 0 2ea9ab9198d1 b2320729164f3fdc
240 0 0 120 0 2ea9ab9198d1 0526c64a2141d072
280 0 0 120 0 2ea9ab9198d1 bbcc492183c8d93f
320 0 0 120 0 2ea9ab9198d1 3035677132aa3f39
360 0 0 120 0 2ea9ab9198d1 ccaf379ddd32ab82
400 0 0 120 0 2ea9ab9198d1 1e765dc4b93e3f75
every sweep hashed and folded together: 0c66dddd1b793b0f
Everybody catches it either way, because a hundred and twenty animals on ninety-six squares of ground cannot avoid each other for long, and both crowds are through it inside two hundred ticks. What separates them is how much of the valley they ruin on the way. At tick 80 the scattered crowd has fouled 62 of the 96 squares against the herd's 41, and at tick 120 it is still carrying 33 against 18. Bunching keeps a herd treading the same few squares over and over, so most of what it fouls is ground it had already fouled, while a crowd that spreads out finds clean ground to spoil. No line of code says any of that. It fell out of three steering rules meeting one countdown on a sheet.
The columns that come out close say as much as the ones that do not. Both runs are one draw of a rule with a coin in it, and the sick counts at tick 80, 83 against 80, sit near enough together that another stream would put them in either order. The fouled counts keep their gap, and they are the ones the arrangement of the animals decides.
The two laws know almost nothing about each other. The ground's rule has never heard of an animal; it fades and it drifts. A creature's rule has never heard of a neighbour; it reads the one square it is standing in. Everything a reader would call an epidemic happens in the gap between them, and the gap is one cell lookup wide.
One cell, one writer
The accumulator was built so anything could push on a body without knowing what else was pushing. The sweep is the same courtesy pointed the other way: any rule can decide a cell without knowing which cells have already been decided, because none of them have. Both arrangements buy the same thing, which is that a law can be written, read and debugged on its own. Fire never mentions water. The taint on the ground never mentions an animal. Neither of them mentions the sweep that runs them.
Writing one cell is what makes that possible, and it is the discipline to carry away. A rule that could set its neighbour alight would have to agree with every other rule about who gets to write a given cell this tick, and the moment two of them disagree the answer depends on which ran first. Turn the law round so each cell decides only itself, out of what it can see, and the question cannot come up. Every spread in this chapter is written from the point of view of the thing being spread to, and that inversion costs nothing and removes a whole class of argument.
The double buffer is what makes the instant real. Read one whole state, write one whole next state, never a mixture: the string rewriter said the same sentence, where rewriting in place made a single generation run away forever. The failure above is that rule's other half. Reading correctly is not sufficient on its own, because the buffer being written is not empty. It holds an old world, and every cell you decline to write is a cell that keeps it.
Name the differences between these three laws because they are the axes any rule of this kind varies along. Fire draws from a stream and water does not, so one of them needs a seed and the other replays on arithmetic alone. Fire's chance is a function of place, taken from a field laid over the same grid, where water's is a function of two heights. The sickness runs on cells but is read by things that are not on cells at all. That last one is the direction of travel: a grid rule is cheap, it is local, and it is a perfectly good way to carry a quantity that anything standing on the ground can ask about. Smoke, scent, moisture, trampling, light under a canopy. Each is one number per cell, one rule about neighbours, and one sweep.
A valley that still does not eat
Take stock of what this volume added. Two numbers kept together and given arithmetic. Position, velocity and acceleration, updated in a fixed order on a tick the world already had. An accumulator that lets anything push on anything without coordination, and a mass that decides how much a push is worth. A force that varies with where you are standing, and a drag that gives the world a speed limit. A wave read off a point going round a circle, then many of them side by side making water. Thousands of short-lived bodies out of one pool that never allocates. A creature that wants to be somewhere, then forty of them that want to be near each other. A plant written as text and read back as lines. And now a law on the ground itself.
Everything in The Hollow moves under forces, bobs and ripples, rains and burns, startles and bunches, grows out of a string and spreads from cell to cell. All of it comes from a seed, all of it is hashed, all of it replays. None of it is thinking. Not one thing built in these eleven chapters chooses anything: a walker steers toward a point somebody typed, a plant grows to a generation somebody typed, and a fire takes whatever chance somebody typed. That is the correct order to have built them in, because a creature that decides needs something to decide about, and the something is a world with consequences in it.
There is also a gap this volume opened and did not close. The plants are drawings. A bracken stalk with a hundred and twenty-five segments is a picture of a plant that grew from a grammar, and it does not drink, it does not need light, it does not care that it is standing three cells from open water or on rock, and it is exactly as tall in January as in June. The ground under it is a painting: soil is a colour and a word, and the height this chapter computed was invented on the spot for one rule, out of distance to a pond. Fire took the fuel away and nothing grows back.
- Given a rule and a small grid of states, I can work out the next grid by hand, reading every neighbour from the grid as it stood before I started.
- I can say why a spread rule is written from the point of view of the cell catching rather than the cell burning, and what goes wrong when two rules can write one cell.
- Given a catch probability and a count of alight neighbours, I can work out the chance a cell escapes, and say what a second tick alight does to it.
- Shown a state that no rule in the program can produce, I check what is in the buffer being written before I look at the rule.
- I can read a per-cell height table and predict, tick by tick, which cells a downhill rule will wet and which it will refuse.
- I can couple an automaton to things that are not on its grid: write to the cell they stand in, read from the cell they stand in, and keep the two rules ignorant of each other.
Exercise 1 — move the spring. Using only the height table
printed by -mode water, predict how many cells go under if the spring runs
from (3, 1) instead of (10, 1), and on which ticks. Then run
-mode water -src 3,1.
(3, 1) sits at height 2. Its neighbours are (2, 1) and (4, 1) at 2, level with it and therefore refused, and (3, 2) at 1, which goes under on tick 1. From there the only lower neighbour is (3, 3), which is already pond. Two cells, one tick, and then nothing, where the same rule from (10, 1) wetted seventeen over five ticks. Height is the whole difference.
$ go run ./cmd/spread -mode water -src 3,1 -ticks 8 -from 4 -to 4
spread: water on the seed 5 valley, a cell goes under only when a wet neighbour stands above it
the spring runs from (3,1), 2 cells above the water line
how far every cell stands above the water line
# # # # # # # # # # # #
# 3 2 2 2 2 2 3 4 5 6 #
# 2 1 1 1 1 1 2 3 4 5 #
# 1 0 0 0 0 0 1 2 3 4 #
# 1 0 0 0 0 0 0 1 2 3 #
# 2 1 1 0 0 0 0 1 2 3 #
# 3 2 1 0 1 1 1 2 3 4 #
# # # # # # # # # # # #
tick water changed sheet
0 16 0 a57358819394
1 18 1 47328cb4d5cf
4 18 0 47328cb4d5cf
############
#..~.......#
#..~.......#
#.~~~~~....#
#.~~~~~~...#
#...~~~~...#
#...~......#
############
8 18 0 47328cb4d5cf
every sweep hashed and folded together: e0b809933d769956
Eighteen: the pond's sixteen, the spring cell, and one cell of channel. A spring high on the rim makes a stream and a spring next to the pond makes a puddle, and the rule that produced both is one comparison.
Exercise 2 — find where a fire stops being a nuisance. Before
running -mode curve, predict roughly which catch value first sends more
than half of sixty fires past thirty cells. Work from the chance one alight neighbour
passes the fire on over its two ticks.
Over two ticks a single neighbour passes the fire on with 1 − (1 − p)2: 0.51 at p = 0.30, 0.64 at 0.40, 0.75 at 0.50. A newly lit cell has three neighbours it did not arrive from, so the crude estimate says a front keeps itself going as soon as three attempts at that chance can be expected to land one, which is true by about p = 0.20. The table flatly disagrees: at 0.20, 46 of 60 fires died under five cells.
The estimate is wrong in an instructive way. It assumes three fresh neighbours, and a compact burn does not have three. Every cell except the ones on the outer edge is facing ground that is already ash, so most of a fire's attempts are spent on cells that cannot catch, and what actually has to keep up is the outward-facing edge alone. The table puts that changeover between 0.35 and 0.40, where the fizzle count and the took-most count cross.
The column to sit with afterwards is most. At every catch from 0.45 up
it reads 44, the whole valley, including settings where the average fire burns 24
cells. A stochastic rule does not have a typical outcome just because it has an
average one, and any parameter chosen off a mean is a parameter chosen off a number
that may describe nothing that ever happens.
Exercise 3 — make the thrifty sweep honest. Add one line to
SweepThrift that brings the buffer being written up to date before
anything goes into it, then check the mended version against the full sweep by chain
digest rather than by looking at it.
The line is copy(s.next, s.now) at the top. After it, every cell the
rule leaves alone already holds this tick's value in place of the one from two
sweeps ago, and the writes that follow only have to record the changes.
// internal/cells/sheet.go
func (s *Sheet) SweepMend(r Rule) int {
copy(s.next, s.now)
return s.SweepThrift(r)
}$ go run ./cmd/spread -mode fire -thrift -mend -ticks 20 | tail -4
20 0 2 42 0 9aaf065e4ffc
42 of 44 cells of fuel burnt, 2 still standing, out by tick 17
the burnt cells average +0.76 cells east of the spark
every sweep hashed and folded together: 8cf9c43cca88103b
8cf9c43cca88103b is the full sweep's chain from stage 2, so all twenty
sweeps agree and not merely the printed ones. Now count what the optimisation bought.
The copy touches ninety-six cells, and the writes it saved were the ones no rule
changed, which on a quiet tick is ninety-four of them. The thrifty sweep with its
bug fixed does the same amount of work as the plain one and carries a branch the
plain one does not, which is the ordinary ending for this kind of idea.