The Spring Feeds the Soil

// internal/cells/store.go

// Store is a sheet that holds an amount per cell instead of a kind.
// Everything a sheet promises, a store promises the same way: one grid
// every rule reads, a second grid every sweep writes, neither of them
// reachable from outside this package. What changes is the number. A
// State names what a cell is; an amount says how much of something is
// standing in it, and an amount can be added, taken and counted.
type Store struct {
	W, H int

	now  []float64
	next []float64
}

// NewStore allocates a w-by-h store with every cell holding nothing.
func NewStore(w, h int) *Store {
	return &Store{W: w, H: h, now: make([]float64, w*h), next: make([]float64, w*h)}
}

// In reports whether a coordinate names a cell of this store.
func (s *Store) In(x, y int) bool { return x >= 0 && x < s.W && y >= 0 && y < s.H }

// At is the amount in one cell as it stood when this sweep began. Past
// the edge it answers 0, and a store needs no equivalent of the
// sheet's Off to say so: 0 is a state like any other and had to be
// distinguished, where 0 of something is exactly what an absent cell
// holds.
func (s *Store) At(x, y int) float64 {
	if !s.In(x, y) {
		return 0
	}
	return s.now[y*s.W+x]
}

// Amount is one cell's law over quantities: given the store and a cell
// on it, how much that cell holds next. Like a Rule it may read
// anything on the store and may write nothing.
type Amount func(s *Store, x, y int) float64

// Sweep applies one law to every cell of the store, each cell read out
// of the grid the sweep began with and written into the other one, and
// swaps the two when the last cell has been written.
func (s *Store) Sweep(a Amount) {
	for y := 0; y < s.H; y++ {
		for x := 0; x < s.W; x++ {
			s.next[y*s.W+x] = a(s, x, y)
		}
	}
	s.now, s.next = s.next, s.now
}

// Apply changes every cell out of its own amount alone. Nothing here
// reads a neighbour, so there is no order for a law to be spoiled by
// and the second grid goes untouched. It stays safe to leave it stale
// only because Sweep writes every cell of it before any rule reads
// one; the thrifty sweep that did not is in sheet.go, with the run it
// ruins.
func (s *Store) Apply(f func(x, y int, v float64) float64) {
	for y := 0; y < s.H; y++ {
		for x := 0; x < s.W; x++ {
			i := y*s.W + x
			s.now[i] = f(x, y, s.now[i])
		}
	}
}

Apply is the half that is new. Four laws run on this page's tick and only one of them looks at a neighbour; the other three change a cell out of what that cell alone is holding. A law like that cannot be tripped by the order it walks the grid in, so it does not need the second buffer and does not pay for it. Keeping the two apart in the package is a way of stating which kind a law is at the moment you write it.

// internal/cells/store.go, the rest of the file

// Add puts an amount into one cell from outside any sweep, the way a
// spring puts water into the cell it rises in. It is the one way an
// amount enters a store that no law wrote, so every unit a run adds is
// added here and counted here.
func (s *Store) Add(x, y int, v float64) {
	if !s.In(x, y) {
		return
	}
	s.now[y*s.W+x] += v
}

// Total is everything the store is holding, added up in row order. The
// order is written down because adding the same numbers in another
// sequence gives another answer in the last few bits, and this total is
// one side of a ledger that has to balance.
func (s *Store) Total() float64 {
	t := 0.0
	for _, v := range s.now {
		t += v
	}
	return t
}

// Bits is every cell's amount as raw float64 bits, big-endian, in row
// order. Two runs that part in the seventeenth digit print identical
// tables, so the digest runs over the numbers themselves and never over
// the columns.
func (s *Store) Bits() []byte {
	out := make([]byte, 0, len(s.now)*8)
	var buf [8]byte
	for _, v := range s.now {
		binary.BigEndian.PutUint64(buf[:], math.Float64bits(v))
		out = append(out, buf[:]...)
	}
	return out
}

None of those three is a law, and that is why they sit outside the sweep: they are how a store is written to, added up and hashed between ticks rather than during one. The digest is over the bits and not the printed columns for the reason volume 3 hashed the bits of a position: two runs that part in the seventeenth digit draw identical maps. And notice what is missing beside the sheet, which has a Set that writes a state into both of its buffers at once. A store has nothing of the kind. A kind is assigned; an amount is added to and taken from, and anything that could assign one from outside would be a way of moving water past the ledger.

// internal/terra/bed.go

// Soak puts water into one cell of ground and reports how much of it
// the ground took: nothing at all where a root could not live, and
// never past a full cell.
func (b *Bed) Soak(c sim.Coord, water, cap float64) float64 {
	if !b.Rootable(c) || water <= 0 {
		return 0
	}
	s := &b.cells[b.index(c)]
	took := math.Min(water, math.Max(cap-s.Moisture, 0))
	s.Moisture += took
	return took
}

// Held is everything in the bed, added up in row order. The order is
// written down because adding the same numbers in another sequence
// gives another answer in the last few bits, and this total is one side
// of a ledger that has to balance.
func (b *Bed) Held() Cell {
	var t Cell
	for _, s := range b.cells {
		t.Moisture += s.Moisture
		t.Nutrient += s.Nutrient
	}
	return t
}

// Bits is every cell's two numbers as raw float64 bits, big-endian, in
// row order: the same digest volume 3 took over positions, pointed at
// the ground instead.
func (b *Bed) Bits() []byte { ... }

// internal/cells/chain.go

// AddBits folds a run of raw bytes into the chain. Not every part of a
// world lives in this package, and a history is only worth hashing if
// it covers all of it: anything that can write its own state as bytes
// can be folded into the same chain as a sheet and a store.
func (c *Chain) AddBits(p []byte) {
	sum := sha256.New()
	sum.Write(c.h[:])
	sum.Write(p)
	copy(c.h[:], sum.Sum(nil))
}

// AddStore folds one tick's store into the chain, over the raw bits of
// every amount rather than the printed columns.
func (c *Chain) AddStore(s *Store) { c.AddBits(s.Bits()) }

Soak is Draw with the sign turned round, and writing it that way settles two arguments at once. The bed already knows which cells a root can live in and how full each one is, so it is the right place to decide how much water the ground accepts; and because it reports what it took, the film can subtract that exact number instead of working the amount out a second time. One number, computed once, used at both ends.

Chain itself is neither new nor moved: the type, the Add that folds a sheet into it and the Sum that prints it are still in sheet.go, byte for byte as volume 3 left them. chain.go is a second file of the same package holding the two methods this page needed — legal Go, and a way of saying in the file name that they arrived later. The chain now folds two things per tick, the film and the bed, which is the whole state this page can change. A digest over half a world is a digest that goes on matching while the other half drifts.

Regen retires here. It stays in the file, with a second paragraph of three lines added to its comment saying what replaced it, because deleting a placeholder is how the next reader ends up reinventing it: Chapter 37 retires it. Once water arrives at a cell because it ran there, the refill is a fact about the ground and not a constant, and Soak below is what puts it back. Nothing in this chapter calls it again.

// cmd/soak/main.go

const (
	Spring = 0.80  // what the spring adds to its own cell every tick
	Rise   = 2.00  // how much water it takes to fill one step of the valley's side
	Soak   = 0.05  // the most one cell of soil takes off the surface in a tick
	Cap    = 1.00  // how much water a cell of soil holds when it is full
	Sun    = 0.02  // the sun's allowance: what it lifts off one wet cell in a tick
	Damp   = 0.001 // the least a cell can hold and still be called wet
	Pool   = 0.10  // the least standing water a printed map draws as a puddle
)

// level is the top of the water at one cell: the ground plus whatever
// is standing on it. Chapter 34 compared ground heights, because a
// cell was wet or dry and had no depth. A quantity has one, and the
// top of the water is what decides which way it goes.
func (v *valley) level(x, y int) float64 {
	return v.ground[y*Cols+x] + v.surf.At(x, y)
}

// spill is how much cell (x, y) hands to each of its four neighbours
// this tick. A cell hands its whole film to the ground below it, split
// between the ways down in proportion to how far each of them falls,
// and never enough down any one of them to put that neighbour above
// the cell it came from. This is the only place in the program that
// number is worked out, and both ends of every exchange call it.
func (v *valley) spill(x, y int) [4]float64 {
	var out, drop [4]float64
	have := v.surf.At(x, y)
	if have <= 0 || v.solid(x, y) {
		return out
	}
	top := v.level(x, y)
	fall, ways := 0.0, 0
	for i, d := range cells.Steps {
		nx, ny := x+d.DX, y+d.DY
		if v.solid(nx, ny) {
			continue
		}
		if f := top - v.level(nx, ny); f > 0 {
			drop[i] = f
			fall += f
			ways++
		}
	}
	if ways == 0 {
		return out
	}
	for i := range out {
		if drop[i] <= 0 {
			continue
		}
		share := have * drop[i] / fall
		even := drop[i] / float64(ways+1)
		out[i] = math.Min(share, even)
	}
	return out
}

Two clauses, and each does a job the other cannot. share is the runoff clause: water on a slope does not sit there, it goes, and the steepest way down takes the largest part of it. On its own that clause would slosh a puddle back and forth across a flat forever, since a cell sitting a hair above its neighbour would hand over everything it has and be handed most of it back. even stops that. Dividing the drop between the cell and the ways out of it gives the most that can move without putting the receiver above the giver, so a puddle spread over four level cells settles into four equal depths and stays. The smaller of the two clauses wins, every time.

Notice what the pond needed before it would behave like a pond: nothing. Its cells all sit at ground 0, so the only drop between them is the water itself and the levelling clause is the one that binds. The slope wets, the basin fills, and neither is a special case.

// cmd/soak/main.go

// flow is the law: what one cell keeps, less what it hands to the
// neighbours below it, plus what the neighbours above it hand down.
// The steps are written in pairs, east then west and south then north,
// so flipping the low bit of an index turns a step into the step back:
// what the neighbour I reached going east hands to me is its own
// westward share.
func (v *valley) flow(s *cells.Store, x, y int) float64 {
	if v.solid(x, y) {
		return 0
	}
	w := s.At(x, y)
	for _, gift := range v.spill(x, y) {
		w -= gift
	}
	for i, d := range cells.Steps {
		nx, ny := x+d.DX, y+d.DY
		if v.solid(nx, ny) {
			continue
		}
		w += v.spill(nx, ny)[i^1]
	}
	return w
}

This is chapter 34's discipline holding under a heavier load. A rule decides one cell and writes one cell, its own, so a cell cannot push water into its neighbour; it can only ask the neighbour what it is sending. Every exchange is therefore computed twice, once by the giver working out what it hands over and once by the receiver working out what it is handed, and the two agree because they are the same call: spill on the giving cell, out of the grid nobody is writing to.

That claim is checkable and this is a chapter about checking things, so check it. Take a settled valley, pick one cell on the north-east slope, and print the four exchanges it is part of.

$ go run ./cmd/soak -mode hand -ticks 1200 -at 8,2
soak: cell (8,2) at tick 1200, and the four exchanges it is part of
      one step up the valley side is 2 units of water, so ground 3 is 6.00

  step   neighbour     ground     film        top       drop   hands over   takes back
  east   (9,2)         8.00   0.3357     8.3357    -2.1052     0.000000     0.167851
  west   (7,2)         4.00   0.1311     4.1311     2.0994     0.117375     0.000000
  south  (8,3)         4.00   0.2071     4.2071     2.0234     0.113124     0.000000
  north  (8,1)         8.00   0.1721     8.1721    -1.9417     0.000000     0.082648
  here   (8,2)         6.00   0.2305     6.2305

      0.230499 here, less 0.230499 handed away, plus 0.250499 handed in
      leaves 0.250499, and the rule returns 0.250499

      the whole grid this tick: 4.027525017 handed over, 4.027525017 taken in
      film before the sweep 35.925463791, after it 35.925463791, difference 7.105427357601002e-15

Read the drop column first, because every other number follows from its sign. Two of this cell's neighbours stand above it and two below, and the rule has nothing to say to the two above: a cell never reaches uphill, so both of those rows hand over 0.000000. What comes down from them is their business, worked out in their own spill, and it arrives as 0.167851 from the east and 0.082648 from the north. Meanwhile this cell empties itself completely, 0.117375 west and 0.113124 south, which together are its whole film to the last digit. It is a piece of channel. Everything that arrives leaves the same tick, and the film it carries is water in flight rather than water in store.

The last two lines are the ones to keep. Asked of all ninety-six cells at once, the water handed over and the water taken in are the same number to nine decimal places, and the film across the whole valley after the sweep is what it was before, short by 7.1 × 10⁻¹⁵. That is one step of the arithmetic at that size, the smallest amount by which two float64 values near 36 can differ, and it comes from adding ninety-six numbers in a different order, not from losing water. A sweep that moves water changes only where the water is.

// cmd/soak/main.go

// soak hands the film to the ground under it. The bed is the authority
// on how much it can take, so the amount is asked for once, the ground
// answers with what it kept, and the film gives up exactly that. Both
// ends of the transfer are the same number because only one of them
// ever worked it out.
func (v *valley) soak() {
	for y := 0; y < Rows; y++ {
		for x := 0; x < Cols; x++ {
			c := sim.Coord{X: x, Y: y}
			v.into[y*Cols+x] = v.bed.Soak(c, math.Min(Soak, v.surf.At(x, y)), Cap)
		}
	}
	v.surf.Apply(func(x, y int, w float64) float64 { return w - v.into[y*Cols+x] })
}

// sun takes the same allowance from every cell holding anything: off
// the film first, and out of the ground underneath for whatever the
// film could not cover. The second half is the bed's own Draw with a
// root of no radius at all, because evaporation takes water out of the
// ground exactly the way a root does and the clamp inside Draw is
// already the right clamp. This is the only place water leaves the
// valley, so it is the only place the gone column grows.
//
// It counts as it goes: how many cells it took anything from, and how
// many of those could pay the whole allowance. The interlude at the
// end of this chapter is about those two numbers.
func (v *valley) sun() float64 {
	took := 0.0
	v.wet, v.full = 0, 0
	for y := 0; y < Rows; y++ {
		for x := 0; x < Cols; x++ {
			i := y*Cols + x
			v.film[i] = math.Min(Sun, v.surf.At(x, y))
			dry := v.bed.Draw(sim.Coord{X: x, Y: y}, 0, terra.Cell{Moisture: Sun - v.film[i]})
			took += v.film[i]
			took += dry.Moisture
			if lift := v.film[i] + dry.Moisture; lift > 0 {
				v.wet++
				if lift >= Sun {
					v.full++
				}
			}
		}
	}
	v.surf.Apply(func(x, y int, w float64) float64 { return w - v.film[y*Cols+x] })
	v.gone += took
	return took
}

// step is one tick of the water cycle, in the order it happens: the
// spring puts water in, the ground under it drinks what it can hold,
// what is left runs downhill, and the sun lifts its allowance back
// out.
func (v *valley) step() float64 {
	v.tick++
	v.surf.Add(v.spring.X, v.spring.Y, v.rate)
	v.added += v.rate
	v.soak()
	v.surf.Sweep(v.flow)
	lifted := v.sun()
	v.chain.AddStore(v.surf)
	v.chain.AddBits(v.bed.Bits())
	return lifted
}

// held is the water still in the valley: the film on top of the
// ground plus the moisture inside it.
func (v *valley) held() float64 { return v.surf.Total() + v.bed.Held().Moisture }

// check is the books: everything put in, less everything still here,
// less everything taken out. Nothing else may move water, so this is
// zero or there is a bug.
func (v *valley) check() float64 { return v.added - v.held() - v.gone }

Both transfers in that tick are written the same way and it is not a coincidence. Ask one owner for a number, take the number it gives back, apply it to the other side. soak asks the bed and the film pays what the bed accepted; sun asks the bed and the sky is credited with what the bed gave up. The second is Draw with a radius of zero, which is worth a moment: a root and an afternoon of sunshine take water out of the ground by exactly the same operation, and the difference between them is only where the water goes next.

check costs three reads and two subtractions, and it is the most valuable line in the program.

$ go run ./cmd/soak -ticks 60 -every 10 -from 60 -to 60
soak: water as a quantity on the seed 5 valley, counted in and counted out
      the spring at (10,1) adds 0.80 a tick, the sun lifts 0.02 from every wet cell
      soil takes 0.05 a tick and holds 1.00; a cell hands its film to the ground below it
      # rock   . dry   , damp   : wet ground   o standing water   O deeper than the soil holds
  tick     added      film      soil      gone        check   cells         water
     0      0.00      0.00      0.00      0.00    0.000e+00       0  ef115a0e0c15
    10      8.00      1.69      4.02      2.29   -4.441e-16      15  bff25d98e2e8
    20     16.00      1.69      9.26      5.04    1.776e-15      15  9669d132e4af
    30     24.00      2.79     12.62      8.58    5.329e-15      27  106569263717
    40     32.00      3.75     14.82     13.43    1.066e-14      30  b97806907801
    50     40.00      4.87     15.99     19.14   -2.487e-14      34  84ba398687e5
    60     48.00      6.06     16.52     25.42   -5.684e-14      36  2ea804af362e
        ############
        #.....,:oo:#
        #.....:oooo#
        #...,oooooo#
        #..,,ooooo:#
        #...,ooo,..#
        #..........#
        ############
      48.00 in, 22.58 still here, 25.42 gone up; the sun took 0.651 on the last tick
      the sun took from 36 cells on that tick, 30 of them holding enough to pay in full
      the books, to every digit they have: -5.684341886080802e-14
      every tick hashed and folded together: d83216798a5602ce

Sixty ticks, forty-eight units delivered into one cell on the rim, and the water has taken the route chapter 34's fan took, because it is the same table deciding. Then it went further: the standing water reaching into rows 3 and 4 is the basin taking its first delivery. The count the count to inspect is the third column against the fifth. The valley is holding 22.58 units and has already lost 25.42, so more than half of everything the spring ever produced has left the world entirely, and no earlier version of this world could have told you that. Water leaves.

The check column is doing its job in the least dramatic way available. The last of those residuals is −5.684 × 10⁻¹⁴, and it is useful to recognize that number by sight. Adjacent float64 values near 48 are 7.105 × 10⁻¹⁵ apart, so the books are out by exactly eight of the smallest steps the arithmetic can take at that size: what you get for adding a hundred numbers in one order and a hundred in another. A residual the size of rounding is rounding. A residual the size of water is a leak.

$ go run ./cmd/soak -ticks 1200 -every 200 -from 1200 -to 1200
soak: water as a quantity on the seed 5 valley, counted in and counted out
      the spring at (10,1) adds 0.80 a tick, the sun lifts 0.02 from every wet cell
      soil takes 0.05 a tick and holds 1.00; a cell hands its film to the ground below it
      # rock   . dry   , damp   : wet ground   o standing water   O deeper than the soil holds
  tick     added      film      soil      gone        check   cells         water
     0      0.00      0.00      0.00      0.00    0.000e+00       0  ef115a0e0c15
   200    160.00     19.24     17.98    122.78    4.263e-14      38  c8e50a188d69
   400    320.00     32.95     19.98    267.07    2.103e-12      41  44c2f1b3eda4
   600    480.00     35.66     21.02    423.32    4.604e-12      42  e9c11423dbf6
   800    640.00     35.74     21.41    582.85   -2.728e-12      42  4ceea24d3dd5
  1000    800.00     35.76     21.82    742.41   -1.137e-11      42  766c85ab7b7a
  1200    960.00     35.93     21.98    902.09   -2.046e-11      43  46e1b3b2bffa
        ############
        #.....::oo:#
        #...::ooooo#
        #.OOOOOoooo#
        #.OOOOOOoo:#
        #...OOOOo..#
        #...O,:o...#
        ############
      960.00 in, 57.91 still here, 902.09 gone up; the sun took 0.800 on the last tick
      the sun took from 43 cells on that tick, 39 of them holding enough to pay in full
      the books, to every digit they have: -2.0463630789890885e-11
      every tick hashed and folded together: 729363b91fb2c453

Lay the deep cells of that map over the terrain the seed drew back in chapter 3 and they are the same cells, row for row: five across on row 3, six on row 4, four on row 5, one on row 6. Nobody told the water where the pond was. The pond is the set of cells at height 0, and the arithmetic put the water at the bottom because the bottom is where two clauses of one function send it. Those cells hold no soil moisture at all, and the soil column is lower than it looks for that reason: the bed refuses open water, so a pond in this world is standing water and never damp ground.

The rest of the map is what chapter 34 could not have drawn. A wet fan runs from the spring down to the water, a damp fringe reaches a cell or two beyond it, and the whole column against the west wall never takes a drop, though the ground there is no higher than the ground the fan crosses. From tick 600 on, the film, the soil and the count of paying cells barely move: 960 units have gone in, the valley holds 58 of them, and the other 902 left through the sun. Eight tenths of a unit in, and on the last tick, exactly eight tenths back out.

$ go run ./cmd/soak -mode sites -ticks 1200
soak: 1200 ticks of spring, then none, seed 5 valley
      a root reaches its own cell and the four around it, so five cells of soil,
      and a cell of soil holds 1.00 when it is full

  site               ground   soil in reach   first wet   the film on its own cell
  the shoulder (2,1)        2           0.000       never                      0.000
  the run (8,2)             3           5.000      tick 3                      0.230
  the shore (8,5)           1           2.000     tick 26                      0.510

      the spring shuts off at tick 1200 and the sun keeps its allowance
  tick   the shoulder      the run    the shore     valley held
  1200          0.000        5.000        2.000           57.91
  1220          0.000        3.200        1.767           42.43
  1240          0.000        1.200        0.967           27.23
  1260          0.000        0.000        0.167           14.46
  1280          0.000        0.000        0.000            7.74
  1300          0.000        0.000        0.000            1.34
  1320          0.000        0.000        0.000            0.00
      the run's five cells empty at tick 1253, the shore's at 1265, the valley at 1305

The shoulder is the result to sit with. It stands at height 2 and the run stands at height 3, so the cell that never sees a drop in twelve hundred ticks is the lower of the two. Height was never the question. The question is whether water passes through, and this water comes out of one cell on the north-east rim and takes the ways down the heights offer it, which do not go west. A seed landing on the shoulder has ground that is perfectly good in every respect except the one that decides.

The shore is the other kind of disappointment, and it is the previous chapter's rule doing the damage. It sits one step above the water with a full film on it, and three of the five cells in its reach still give it nothing: one is open water, which no root can live in, and two are ground the fan never got to. A seedling there has a pond in sight and 2.000 of soil to drink, against the run's 5.000 on ground that never floods.

Now the drying. The run's five cells are full at tick 1,200 and empty at 1,253. Predicting that is arithmetic anyone can do: five cells at 0.02 each per tick is 0.10 a tick, and 5.00 divided by 0.10 is 50 ticks. The measured answer is 53, and the extra three ticks are the film. The sun takes its allowance off standing water first and only reaches the ground when the film is gone, so the 0.230 sitting on that cell buys the bed beneath it a few ticks of grace, and so does every film in reach of it. The shore starts with less than half as much and outlasts it anyway, to tick 1,265, because the pond spends those ticks draining through it. Same rule, same rates, different address.

Then the last column empties the place: 57.91 units at tick 1,200, nothing at all by 1,305, and every one of them left through the allowance that had been quietly taking 0.02 a cell all along. The sun has been a colour in the sky for thirty-six chapters. It has a job now, it is the only door out of the valley, and its allowance is one constant that nothing in this world yet turns up or down.