The Map Draws Itself

// internal/render/tilemap.go

// Kind is what the ground is at one cell, as far as this package is
// concerned: three numbers, and no idea what a tick or a seed is.
// Whoever owns a world converts its own terrain into these.
type Kind uint8

const (
	KindRock Kind = iota
	KindSoil
	KindWater
)

// wet reports whether cell (cx,cy) of a cols-by-rows kind rectangle is
// water. A coordinate off the rectangle is not water: there is no cell
// out there to be wet, and nothing can stand, swim or grow in it.
func wet(cols, rows int, kind []Kind, cx, cy int) bool {
	if cx < 0 || cx >= cols || cy < 0 || cy >= rows {
		return false
	}
	return kind[cy*cols+cx] == KindWater
}

// NeighbourMask is the four-bit mask of one water cell: a bit is set
// when that neighbour is land, so the answer is 0 for open water and 15
// for a single wet cell with a bank on every side. The sheet is drawn in
// mask order, so the answer is also the cell that draws it. (The short
// name was taken: chapter 14 gave Mask to the picture that paints a
// pixel diff red.)
func NeighbourMask(cols, rows int, kind []Kind, cx, cy int) int {
	m := 0
	if !wet(cols, rows, kind, cx, cy-1) {
		m |= LandN
	}
	if !wet(cols, rows, kind, cx+1, cy) {
		m |= LandE
	}
	if !wet(cols, rows, kind, cx, cy+1) {
		m |= LandS
	}
	if !wet(cols, rows, kind, cx-1, cy) {
		m |= LandW
	}
	return m
}

// cmd/worldc/main.go

// ground copies a terrain grid into the rectangle of kind bytes the
// renderer draws from. The switch is not decoration: sim.Terrain and
// render.Kind are two iota blocks written in two packages, and nothing
// anywhere says their numbers agree. Naming every case is what keeps a
// renumbering in one of them from silently repainting the other.
func ground(g *sim.Grid) []render.Kind {
	k := make([]render.Kind, g.W*g.H)
	for y := range g.H {
		for x := range g.W {
			t, err := g.At(sim.Coord{X: x, Y: y})
			if err != nil {
				fmt.Fprintln(os.Stderr, "worldc:", err)
				os.Exit(1)
			}
			switch t {
			case sim.Rock:
				k[y*g.W+x] = render.KindRock
			case sim.Soil:
				k[y*g.W+x] = render.KindSoil
			case sim.Water:
				k[y*g.W+x] = render.KindWater
			}
		}
	}
	return k
}

LandN, LandE, LandS and LandW are already in the package: they were written beside the sheet as the terms it was drawn to, and the four if statements above are the first code to read them. Nothing here re-derives what 1, 2, 4 and 8 mean. One file says it and two programs obey it.

The switch in ground looks like a longer way to write Kind(t), and the shorter way happens to work today by coincidence alone. Two packages, written months apart, each numbered their own list of ground from zero; that the lists agree anywhere is luck, and a cast would bake the luck into the program without saying so anywhere a reader would look.

$ go run ./cmd/worldc -edges
a 4x3 pond, every cell water

  off the grid is not water        off the grid is more water
     9   1   1   3                    0   0   0   0
     8   0   0   2                    0   0   0   0
    12   4   4   6                    0   0   0   0

Twelve cells of water and nothing else. On the left, a grid four by three; on the right, the identical twelve cells cut out of the middle of a six-by-five pond, so that every off-grid neighbour on the left is a water neighbour on the right. The left column of numbers is a shoreline: 9, 8 and 12 down the west side, 1 at the top, 4 along the bottom, and 0 for the two interior cells that really are surrounded. The right is twelve tiles of open water, which would tile a pond with no edge anywhere in it.

Both readings come out of one line, and the line reads as the plain fact rather than as a policy: a coordinate off the grid is not water. Nothing special-cases the corners, nothing checks whether the map has a rim, and the top-left cell scores 9 because the two neighbours it does not have are, by that rule, not wet.

// internal/render/tilemap.go

// mix turns a coordinate into one 32-bit number that looks unrelated to
// both halves of it. Three odd primes, two shifts and two exclusive-ors:
// each step spreads the bits of the inputs further across the output, so
// coordinates one step apart land nowhere near each other. Same
// coordinate, same number, on every machine and every run.
func mix(cx, cy int) uint32 {
	h := uint32(cx)*374761393 + uint32(cy)*668265263
	h = (h ^ (h >> 13)) * 1274126177
	return h ^ (h >> 16)
}

// Variant is which of two tiles a cell uses, 0 or 1, taken from the
// bottom bit of the mixed coordinate.
func Variant(cx, cy int) int { return int(mix(cx, cy) & 1) }

$ go run ./cmd/worldc -field 256
256x256 cells of soil, 65536 in all

  rule                 soil A   soil B   same as east   same as south
  (x+y) % 2             32768    32768           0.0%            0.0%
  mixed coordinate      32832    32704          50.2%           49.7%

Both rules split the field down the middle, and only one of them is usable. The count columns are identical to within a rounding error, so a tally of A against B says nothing about which picker is which. The two columns on the right are the measurement that separates them: how often a cell and the cell beside it landed on the same variant.

Zero percent is the chessboard, stated as a number. Not one of the 65,280 east-west pairs shares a variant, and not one of the north-south pairs either, because the rule guarantees the opposite every time. The mixed coordinate agrees with its neighbour about half the time in both directions, which is what having no rule at all looks like from the outside. Runs of two and three appear, then break; nothing repeats at any spacing the eye can lock onto.

Open water takes the same treatment for the same reason. Mask 0 covers the middle of a pond, where a repeat announces itself sooner than anywhere on the map, and the sheet's twentieth tile was drawn as a second open water for exactly this. So a cell whose mask is 0 and whose variant is 1 draws from cell 19 instead, and every other mask keeps the tile its number names.

// internal/render/tilemap.go

// TileMap is one tile index per cell, held in a flat slice the same way
// the framebuffer holds pixels. By the time ground reaches this type
// every decision about what to draw has already been made: the numbers
// in it are cells of the sheet, not kinds of ground.
type TileMap struct {
	Cols, Rows int
	Cell       []uint8
}

// At is the sheet cell one map cell is drawn from.
func (m *TileMap) At(cx, cy int) int { return int(m.Cell[cy*m.Cols+cx]) }

// TileOf is the sheet cell one cell of ground is drawn from: stone and
// soil by their kind alone, water by its four neighbours.
func TileOf(cols, rows int, kind []Kind, cx, cy int) int {
	switch kind[cy*cols+cx] {
	case KindRock:
		return CellRock
	case KindSoil:
		if Variant(cx, cy) == 1 {
			return CellSoilB
		}
		return CellSoilA
	}
	m := NeighbourMask(cols, rows, kind, cx, cy)
	if m == 0 && Variant(cx, cy) == 1 {
		return CellWaterB // open water gets a second tile too
	}
	return m
}

// Autotile turns a rectangle of ground into a rectangle of tile indices,
// asking TileOf once per cell. A cell's answer depends on itself and its
// four neighbours and on nothing else, so a map is built once and only
// the cells around a change are ever asked again.
func Autotile(cols, rows int, kind []Kind) *TileMap {
	m := &TileMap{Cols: cols, Rows: rows, Cell: make([]uint8, cols*rows)}
	for cy := range rows {
		for cx := range cols {
			m.Cell[cy*cols+cx] = uint8(TileOf(cols, rows, kind, cx, cy))
		}
	}
	return m
}

// DrawMap blits every cell of a tile map onto the buffer, with the map's
// own cell (0,0) landing at screen pixel (ox,oy). It returns how many
// cells it drew. Whatever falls outside the buffer is thrown away by the
// clip rectangle, one blit at a time.
func DrawMap(b *Buffer, m *TileMap, s *Sheet, ox, oy int) int {
	n := 0
	for cy := range m.Rows {
		for cx := range m.Cols {
			i := m.At(cx, cy)
			b.Blit(s, s.Frame(i%TileCols, i/TileCols), ox+cx*TileCell, oy+cy*TileCell)
			n++
		}
	}
	return n
}

$ go run ./cmd/worldc -shot valley.png
worldc 0.0.1 sheet assets/tiles/valley-tileset.png 64x80, 20 cells of 16, 4 across
valley seed 5, 12x8 cells: 36 rock, 44 soil, 16 water

  row  ground        tiles
    0  ############  18 18 18 18 18 18 18 18 18 18 18 18
    1  #..........#  18 16 17 16 16 17 16 16 16 16 16 18
    2  #..........#  18 17 17 16 17 16 17 16 17 16 16 18
    3  #.~~~~~....#  18 16  9  1  1  1  3 17 17 17 17 18
    4  #.~~~~~~...#  18 16 12  4 19  0  0  3 17 17 17 18
    5  #...~~~~...#  18 16 16 17  8  4  4  6 16 17 17 18
    6  #...~......#  18 16 17 17 14 17 17 16 16 17 17 18
    7  ############  18 18 18 18 18 18 18 18 18 18 18 18

  16 water cells draw from 10 tiles:
     cell  0 x2  cell  1 x3  cell  3 x2  cell  4 x3  cell  6 x1
     cell  8 x1  cell  9 x1  cell 12 x1  cell 14 x1  cell 19 x1
  44 soil cells: 21 of cell 16, 23 of cell 17
  36 rock cells, every one of them cell 18

cell (2,3) is water
  N ( 2, 2) soil     land  +1
  E ( 3, 3) water    wet   +0
  S ( 2, 4) water    wet   +0
  W ( 1, 3) soil     land  +8
  mask 9 -> sheet cell 9, column 1 row 2

cell (4,6) is water
  N ( 4, 5) water    wet   +0
  E ( 5, 6) soil     land  +2
  S ( 4, 7) rock     land  +4
  W ( 3, 6) soil     land  +8
  mask 14 -> sheet cell 14, column 2 row 3

frame 192x128, 96 cells blitted at origin (0,0)
sha256 8fdff25f39f196d0bc7781112aa5278a0a5b6af2c7f1162fbba75aea77ebe4b6
wrote valley.png

The two columns in the middle of that table are the check the whole chapter rests on. On the left is what volume 1 has printed since its third chapter, one glyph per cell, straight out of the grid. On the right is what the renderer made of it, and the two can be read against each other by eye: every # is an 18, every . is a 16 or a 17, and every ~ is a number from 0 to 15 or the second open water at 19.

Read row 3 across. Rim, soil, then 9 where the pond's north-west corner starts, three 1s along its northern bank, a 3 where the bank turns the corner, and soil after that. Row 4 has 12 at its western end and three cells in the middle where the water is surrounded on all four sides: two of them drew cell 0 and the third drew 19, because its variant said so. The two hand calculations from the interlude are printed underneath, each with its four questions itemised, and both land where the paper said.

Sixteen water cells drew from nine of the transition tiles plus the second open water, so seven of the sixteen never appeared. That is not a fault in the sheet. A twelve-by-eight valley has room for one pond and a stub, and the masks it does not contain are the ones needing an inlet, a one-cell island, or a corner shaped in a way this pond does not have.

$ go run ./cmd/worldc -diff valley.png inside-out.png
valley.png sha256 8fdff25f39f196d0bc7781112aa5278a0a5b6af2c7f1162fbba75aea77ebe4b6
inside-out.png sha256 f619ad6c7f925077860e41ba0c0d525a8308edacd95f713465c1d384379abc5f
1492 of 24576 pixels differ, first at (32,48): ff243e6b became ff3d7799

1,492 pixels of 24,576, and the first of them is the corner of the cell the interlude worked through: world pixel (32, 48) is map cell (2, 3), the top-left pixel of its sixteen-by-sixteen square. In the correct frame that pixel is the dark band of a northern bank; in the broken one it is plain mid-tone water. 1,458 of the 1,492 sit in the outermost two pixels of a tile, which is the only place the sixteen transition tiles differ from one another at all. The remaining 34 are one cell: (4, 4) drew the second open water in the correct map and cell 15 in the broken one, and those two disagree in their middles as well as at their edges.

The counts in the earlier table also moved in a way that reads as a symptom once you know what to look for. The correct map uses cell 0 twice and cell 15 never; the broken one uses cell 15 three times and cell 0 not at all. Cell 15 draws a lone wet cell with a bank on every side, and every one of this pond's sixteen cells has at least one wet neighbour, so that tile belongs nowhere on this map.

$ go run ./cmd/worldc -window | tail -2
frame 96x64, 96 cells blitted at origin (-48,-32)
sha256 9cd77d1b26198e80aab9402550599d78b83e46c31b71d6bd448ebbe97ae4fc16

DrawMap takes the screen pixel its cell (0, 0) lands on, and moving that corner is the only lever anything outside the renderer needs. Here it is (−48, −32) on a buffer a quarter of the valley's size, and the picture is the middle of the map: the blits at negative coordinates are cut away by the clip rectangle, which has been refusing writes outside itself since it was written, and the ones that survive land where the subtraction puts them. All 96 cells were still offered, which is honest work for a twelve-by-eight map and would stop being honest on a large one.

// cmd/worldc/main_test.go

// valleyHash is the SHA-256 of the pixels seed 5's valley draws to.
const valleyHash = "8fdff25f39f196d0bc7781112aa5278a0a5b6af2c7f1162fbba75aea77ebe4b6"

// TestValleyMatchesItsHash is the whole chapter in one assertion: the
// generator's grid, the tileset on disk, and the picture they make
// together. This test lives here rather than in internal/render because
// this file is the only one in the program that imports both packages.
func TestValleyMatchesItsHash(t *testing.T) {
	s, err := render.LoadSheet(filepath.Join("..", "..", sheetPath), render.TileCell)
	if err != nil {
		t.Fatal(err)
	}
	g := sim.Generate(valleyW, valleyH, valleySed)
	b := render.NewBuffer(g.W*render.TileCell, g.H*render.TileCell)
	render.DrawMap(b, tiles(g), s, 0, 0)
	if got := b.Hash(); got != valleyHash {
		if err := b.SavePNG("valley.got.png"); err != nil {
			t.Fatal(err)
		}
		t.Fatalf("pixels hash %s\n          want %s\n    wrote valley.got.png", got, valleyHash)
	}
}

$ go test -count=1 -v ./internal/render/ ./cmd/worldc/
=== RUN   TestOverKeepsItsEnds
--- PASS: TestOverKeepsItsEnds (0.00s)
=== RUN   TestSheetIsStraight
--- PASS: TestSheetIsStraight (0.00s)
=== RUN   TestSpriteSceneMatchesItsHash
--- PASS: TestSpriteSceneMatchesItsHash (0.00s)
=== RUN   TestMaskReadsFourNeighbours
--- PASS: TestMaskReadsFourNeighbours (0.00s)
=== RUN   TestOffTheGridIsLand
--- PASS: TestOffTheGridIsLand (0.00s)
=== RUN   TestVariantDoesNotCheckerboard
--- PASS: TestVariantDoesNotCheckerboard (0.00s)
PASS
ok  	theworld/internal/render	0.00s
=== RUN   TestValleyMatchesItsHash
--- PASS: TestValleyMatchesItsHash (0.00s)
PASS
ok  	theworld/cmd/worldc	0.00s

Three of the six in internal/render are new and none of them needs a world. TestMaskReadsFourNeighbours builds the five-cell pond from the last chapter's first exercise out of a string of dots and ws and checks the five answers that exercise worked out by hand. TestOffTheGridIsLand pins the boundary decision on a two-by-two grid of pure water, where all four cells are corners. TestVariantDoesNotCheckerboard is the measurement from stage 3 with limits on it: near half the cells on soil B, and near half of the east-west pairs matching. The chessboard rule passes the first and fails the second at every cell on the field.