Where the Camera Stands

// internal/render/tiles.go — what the camera is looking at

// The map this chapter looks at, and the window it is looked at through.
const (
	TileSize = 16
	MapCols  = 48
	MapRows  = 30
	ViewW    = 256
	ViewH    = 144
)

// Void is what the screen holds where the map does not reach.
const Void Color = 0xFF16181C

// Tiles is a grid of colored cells: one color per cell, held in a flat
// slice the same way the framebuffer holds pixels, and no idea what any
// of the colors mean.
type Tiles struct {
	Cols, Rows, T int
	Cell          []Color
}

// At is the color of one cell.
func (m *Tiles) At(cx, cy int) Color { return m.Cell[cy*m.Cols+cx] }

// PixW and PixH are the map's size in world pixels, which is what the
// camera clamps against.
func (m *Tiles) PixW() int { return m.Cols * m.T }
func (m *Tiles) PixH() int { return m.Rows * m.T }

// Walker is one creature standing in the world: the world pixel of its
// top-left corner and the sheet column it is drawn from.
type Walker struct {
	X, Y int
	Col  int
}

// internal/render/camera.go
package render

// Camera is where the window stands in the world: the world pixel that
// is drawn at screen (0,0), and the size of the screen it fills. It
// holds no map, no entities and no opinion about what is being drawn.
type Camera struct {
	X, Y int // the world pixel that lands at screen (0,0)
	W, H int // the viewport, in pixels
}

// ToScreen turns a world pixel into a screen pixel. The answer may name
// a pixel that is nowhere near the screen, which is a fact about where
// the thing is, not an error.
func (c Camera) ToScreen(wx, wy int) (int, int) { return wx - c.X, wy - c.Y }

// ToWorld turns a screen pixel back into the world pixel it shows.
func (c Camera) ToWorld(sx, sy int) (int, int) { return sx + c.X, sy + c.Y }

// View is the piece of the world the screen can show, in world pixels.
func (c Camera) View() Rect { return Rect{c.X, c.Y, c.X + c.W, c.Y + c.H} }

$ go run ./cmd/worldc -lands
worldc 0.0.1 map 48x30 cells of 16 = 768x480, viewport 256x144
camera 448,96 sees world x 448..704, y 96..240

  thing                 world      screen
  cell (28,6)        448,  96      0,   0
  cell (40,12)       640, 192    192,  96
  cell (20,20)       320, 320   -128, 224
  cell (47,29)       752, 464    304, 368
  east walker        696, 200    248, 104

screen 192,96 is world 640,192, which is cell (40,12)

Ground(48, 30) fills that grid with a rock rim, a river bending south and east, a pond and a scatter of stone, by arithmetic with no randomness anywhere in it, and Herd() stands eight creatures on it at positions chosen by hand. The cells hold flat colours so that every number on this page can be checked against the picture by hand; a cell painted out of a tileset lands in exactly the same place, because the camera is not told what is in it. Where the cell lands is the entire question.

Five coordinates, three of them off the screen in one direction or another, and the round trip at the bottom returning the cell the interlude worked out. The camera's own cell lands at (0,0), as it has to: that is the definition, printed back.

View is where the type starts earning its keep. A camera at (448, 96) filling a 256 by 144 screen can show world x from 448 up to but not including 704, and world y from 96 up to 240. That is a Rect, half-open in the same way every rectangle has been since chapter 13, and it is stated in world pixels instead of screen pixels. Two rectangles now describe the same picture in two coordinate systems, and the camera is the pair of numbers that converts between them.

The last row of the table is the one to keep an eye on. That creature stands at world pixel 696, its sprite is sixteen wide, so it covers world 696 through 711 and the window stops at 704. Eight of its columns are on the screen and eight are not. It is going to matter twice.

// cmd/worldc/main.go

// Speed is how far the camera moves per frame while a key is held, in
// world pixels.
const Speed = 3

// view is the client as the shell sees it: something that takes one step
// per frame from the keyboard and paints one frame.
type view struct {
	cam  render.Camera
	m    *render.Tiles
	herd []render.Walker
	s    *render.Sheet
}

// Step scrolls the camera while a direction is held, then puts it back
// inside the map.
func (v *view) Step(in *input.State) error {
	if in.Down(input.Left) {
		v.cam.X -= Speed
	}
	if in.Down(input.Right) {
		v.cam.X += Speed
	}
	if in.Down(input.Up) {
		v.cam.Y -= Speed
	}
	if in.Down(input.Down) {
		v.cam.Y += Speed
	}
	v.cam.Clamp(v.m.PixW(), v.m.PixH())
	return nil
}

// internal/render/camera.go

// Clamp keeps the view inside a world worldW by worldH pixels, so no
// frame ever shows what is past the map's edge.
func (c *Camera) Clamp(worldW, worldH int) {
	c.X = clampTo(c.X, 0, worldW-c.W)
	c.Y = clampTo(c.Y, 0, worldH-c.H)
}

// Center puts a world pixel in the middle of the screen, then clamps.
func (c *Camera) Center(wx, wy, worldW, worldH int) {
	c.X, c.Y = wx-c.W/2, wy-c.H/2
	c.Clamp(worldW, worldH)
}

// clampTo pins v into lo..hi. When hi is below lo, which is what a world
// smaller than the screen produces, lo wins: the map sits against the
// top-left corner instead of drifting off it.
func clampTo(v, lo, hi int) int {
	if v > hi {
		v = hi
	}
	if v < lo {
		v = lo
	}
	return v
}

$ go run ./cmd/worldc -keys
map 768x480, viewport 256x144, camera limits x 0..512, y 0..336

  frame  keys          camera     world x seen   world y seen
  start               448,  96     448..704        96..240
      1  -            448,  96     448..704        96..240
      2  right        451,  96     451..707        96..240
      3  right        454,  96     454..710        96..240
      4  right        457,  96     457..713        96..240
      5  right+down   460,  99     460..716        99..243
      6  right+down   463, 102     463..719       102..246
      7  left         460, 102     460..716       102..246
      8  left         457, 102     457..713       102..246
     48  right x40    512, 102     512..768       102..246
     88  up x40       512,   0     512..768         0..144

The keyboard in that run is a written-down one: a list of which keys are held on which frames, pushed into the same input.State a window fills. Chapter 15 put the physical keys in one table inside the platform layer so that every other package would name actions instead of hardware, and the payment for that discipline arrives here. A camera can be driven, tested and printed with no window open at all.

Two limits are doing work. The map is 768 wide and the window is 256, so the furthest east the camera can stand is 768 − 256 = 512: any further and the frame's right-hand columns would show world coordinates the map does not have. Forty frames of held right from 457 would reach 577, and the camera stops dead at 512 instead, which is the line the last two rows demonstrate on both axes.

Three pixels a frame is a deliberate number. Sixteen would scroll a whole cell per frame and look like a slideshow; three is a walking pace at sixty frames a second, and it means the camera stands on a cell boundary about one frame in sixteen. For the other fifteen the window's edges fall inside cells, halfway through a tile, with a partial column of one cell at the left and a partial column of the next at the right. That remainder matters.

$ go run ./cmd/worldc -edges
  map          asked for       camera     world x seen   world y seen
   768x480   moved to      -40,  -40     0,   0       0..256         0..144
   768x480   moved to     9000, 9000   512, 336     512..768       336..480
   768x480   centered on   640,  192   512, 120     512..768       120..264
   768x480   centered on    40,   40     0,   0       0..256         0..144
   192x128   centered on    96,   64     0,   0       0..256         0..144

The first four rows are ordinary. Ask for a position off the north-west corner and the camera lands on (0,0); ask for one nine thousand pixels out and it lands on the south-east limit. Center puts a world pixel in the middle of the screen where there is room and gives up gracefully where there is not: centring on (640, 192) wants a camera at (512, 120) and gets it, while centring on (40, 40) wants (−88, −32) and is pulled back to the corner.

The last row is the honest case. That map is 192 by 128 pixels, smaller than the 256 by 144 window in both directions. The camera's own limit, worldW - c.W, works out to −64, which is below its lower limit of 0, and the two comparisons inside clampTo disagree about what to do. Order settles it: the high test runs first and the low test overrules it, so the answer is 0 and the map sits in the top-left corner with 64 columns and 16 rows of empty frame beside it. Swap those two if statements and the answer becomes −64, which centres the small map and leaves empty frame on all four sides. Both are defensible. What is not defensible is not knowing which one you wrote, because the case only appears on maps you built to test something else.

// internal/render/camera.go

// Cells is the range of cells of size t the view touches, cut down to a
// map that is cols by rows cells. The four numbers count cells, not
// pixels; what it borrows from Rect is the half-open convention, so
// X1 and Y1 are one past the last cell.
func (c Camera) Cells(t, cols, rows int) Rect {
	v := c.View()
	r := Rect{
		X0: v.X0 / t,
		Y0: v.Y0 / t,
		X1: v.X1 / t,
		Y1: v.Y1 / t,
	}
	return r.Intersect(Rect{0, 0, cols, rows})
}

Four divisions and one intersection. The view runs from world 448 to 704 across, so the range is 448/16 = 28 up to 704/16 = 44, and half-open means columns 28 through 43: sixteen of them, and 16 · 16 = 256 covers the window with nothing left over. The intersection at the end is the same guard Clamp provides in pixels, applied in cells, so a range reaching past the map comes back cut to the map.

// internal/render/tiles.go

// Frame is the work one render did. Two renderers that agree about
// pixels can still be compared on this.
type Frame struct {
	Cells, Sprites int
}

// DrawAll draws every cell and every walker on the map, wherever the
// camera puts them, and leans on the clip rectangle to throw away
// whatever misses the screen.
func DrawAll(b *Buffer, m *Tiles, ws []Walker, s *Sheet, cam Camera) Frame {
	b.Fill(Void)
	var f Frame
	for cy := range m.Rows {
		for cx := range m.Cols {
			sx, sy := cam.ToScreen(cx*m.T, cy*m.T)
			b.FillRect(Rect{sx, sy, sx + m.T, sy + m.T}, m.At(cx, cy))
			f.Cells++
		}
	}
	for _, w := range ws {
		sx, sy := cam.ToScreen(w.X, w.Y)
		b.Blit(s, s.Frame(w.Col, 0), sx, sy)
		f.Sprites++
	}
	return f
}

// DrawVisible draws the same picture, touching only the cells and
// walkers the viewport can reach.
func DrawVisible(b *Buffer, m *Tiles, ws []Walker, s *Sheet, cam Camera) Frame {
	b.Fill(Void)
	var f Frame

	vis := cam.Cells(m.T, m.Cols, m.Rows)
	for cy := vis.Y0; cy < vis.Y1; cy++ {
		for cx := vis.X0; cx < vis.X1; cx++ {
			sx, sy := cam.ToScreen(cx*m.T, cy*m.T)
			b.FillRect(Rect{sx, sy, sx + m.T, sy + m.T}, m.At(cx, cy))
			f.Cells++
		}
	}

	view := cam.View()
	for _, w := range ws {
		box := Rect{w.X, w.Y, w.X + s.Cell, w.Y + s.Cell}
		if box.Intersect(view).Empty() {
			continue
		}
		sx, sy := cam.ToScreen(w.X, w.Y)
		b.Blit(s, s.Frame(w.Col, 0), sx, sy)
		f.Sprites++
	}
	return f
}

$ go run ./cmd/worldc
worldc 0.0.1 map 48x30 cells of 16 = 768x480, viewport 256x144
camera 448,96 sees world x 448..704, y 96..240

visible cells x 28..44, y 6..15
whole map:  1440 cells, 8 sprites, sha256 a29ba1be61868183dc6382eb933195c804c063a63645403fa99d48cd96f3780b
culled:      144 cells, 6 sprites, sha256 a29ba1be61868183dc6382eb933195c804c063a63645403fa99d48cd96f3780b
the two frames differ in 0 of 36864 pixels

Ten times the fills, two extra sprites, and the same sixty-four hexadecimal characters. That equality is the whole point of the exercise. Skipping work is easy; skipping only work that could not have changed a pixel is the part that needs proving, and a hash is a proof a machine can repeat. Culling is a claim about a set: every skipped cell would have written nothing. Two frames and one comparison turn that claim into something the client can be held to.

Note which creatures survived the second pass. Six of eight, and one of the six is the one at world 696 with half its body past the window's edge. Its rectangle reaches into the view, the intersection is not empty, and it gets drawn with chapter 16's blit doing what it did there: cutting the source rectangle down and keeping the offsets in step so the visible half is the half that would have been visible anyway.

$ go run ./cmd/worldc -sweep
every position draws 1440 cells the slow way

  camera     culled   whole frame   culled frame   same
  448, 96     144    a29ba1be6186  a29ba1be6186   yes
  449, 96     144    364ee73dc816  7325148f7c96   NO
             137 pixels differ, first at (255,0): ff77664a became ff16181c
  451, 96     144    38114407061e  ad4ee912f317   NO
             404 pixels differ, first at (253,0): ff77664a became ff16181c
  454, 96     144    c849da8666a5  5482c5c0d1c9   NO
             814 pixels differ, first at (250,0): ff77664a became ff16181c
  464, 96     144    92b65b1698ce  92b65b1698ce   yes
  451, 99     144    7640059d51f6  d896eb8b8b98   NO
             1157 pixels differ, first at (253,0): ff77664a became ff16181c
  512,336     144    1a7d23a9dc5d  1a7d23a9dc5d   yes

Four of seven positions disagree, and the two that pass alongside 448 are 464 and 512. Every position that agrees is a multiple of sixteen.

// internal/render/camera.go — two of the four divisions change
	r := Rect{
		X0: v.X0 / t,
		Y0: v.Y0 / t,
		X1: ceilDiv(v.X1, t),
		Y1: ceilDiv(v.Y1, t),
	}

// ceilDiv divides and rounds up, for two numbers that are not negative.
// Clamp keeps the camera at zero or beyond, so the far edge of a view is
// always a positive number of pixels.
func ceilDiv(a, b int) int { return (a + b - 1) / b }

$ go run ./cmd/worldc -sweep
every position draws 1440 cells the slow way

  camera     culled   whole frame   culled frame   same
  448, 96     144    a29ba1be6186  a29ba1be6186   yes
  449, 96     153    364ee73dc816  364ee73dc816   yes
  451, 96     153    38114407061e  38114407061e   yes
  454, 96     153    c849da8666a5  c849da8666a5   yes
  464, 96     144    92b65b1698ce  92b65b1698ce   yes
  451, 99     170    7640059d51f6  7640059d51f6   yes
  512,336     144    1a7d23a9dc5d  1a7d23a9dc5d   yes

(a + b - 1) / b is division that rounds up, and it works by pushing the numerator to the top of its bucket before the remainder is discarded: 704 + 15 is 719, which is still 44 buckets of sixteen, while 705 + 15 is 720, which is 45. An edge exactly on a boundary keeps the count it had, and an edge one pixel past a boundary adds a cell. That is the difference between the three rows still drawing 144 cells and the three that now draw 153.

The counts are the interesting column now. 153 is 17 columns by 9 rows, and the row at 451 and 99 is 17 by 10 = 170 because both edges fell inside cells. The work the client does changes by a column or a row as it scrolls, which is what honest culling looks like from the outside, and the frames it produces do not change at all. There is a picture of the damage on disk if you took the shot the failure box asked for; write the repaired frame beside it with go run ./cmd/worldc -x 451 -y 96 -shot map.png and measure the difference with the comparison chapter 14 built:

$ go run ./cmd/worldc -diff map.png seam.png
map.png sha256 38114407061e3d3807a57594c6dab4fc0b1dacc9d0b047a0af26a23e20ff969e
seam.png sha256 ad4ee912f317d615b1da8cb9d7322423badfd1c8be4f8bdd4e398ec2532a0b3f
404 of 36864 pixels differ, first at (253,0): ff77664a became ff16181c

Open the two files side by side. They are the same ground, the same creatures, the same pond, and the broken one has a dark stripe three pixels wide down its right edge with a bite taken out of it where a creature stands. On a scrolling map that stripe flickers: it is three pixels at one camera position, one at the next, gone entirely every sixteenth frame. Anybody watching would call it tearing and go looking for the window code.

// internal/render/camera_test.go

// TestCullingKeepsThePicture is the claim culling makes, written as a
// test: the frame drawn from the visible cells alone is the frame drawn
// from the whole map, pixel for pixel, wherever the camera stands. The
// positions include every offset inside one tile, because a camera that
// scrolls three pixels at a time lands between tile boundaries far more
// often than on them.
func TestCullingKeepsThePicture(t *testing.T) {
	s, err := LoadSheet(filepath.Join("..", "..", "assets", "atlas.png"), 16)
	if err != nil {
		t.Fatal(err)
	}
	m := Ground(MapCols, MapRows)
	herd := Herd()
	all := NewBuffer(ViewW, ViewH)
	cut := NewBuffer(ViewW, ViewH)

	var cams []Camera
	for d := range TileSize {
		cams = append(cams,
			Camera{X: 448 + d, Y: 96, W: ViewW, H: ViewH},
			Camera{X: 448, Y: 96 + d, W: ViewW, H: ViewH},
			Camera{X: d, Y: d, W: ViewW, H: ViewH},
			Camera{X: m.PixW() - ViewW - d, Y: m.PixH() - ViewH - d, W: ViewW, H: ViewH})
	}

	for _, cam := range cams {
		fa := DrawAll(all, m, herd, s, cam)
		fc := DrawVisible(cut, m, herd, s, cam)
		if all.Hash() == cut.Hash() {
			continue
		}
		d := Diff(all, cut)
		gotPath := filepath.Join("testdata", "culled.got.png")
		if err := cut.SavePNG(gotPath); err != nil {
			t.Fatal(err)
		}
		t.Fatalf("camera %d,%d: %d cells culled to %d, and %d pixels changed, first at (%d,%d)\n    wrote %s",
			cam.X, cam.Y, fa.Cells, fc.Cells, d.Count, d.At.X, d.At.Y, gotPath)
	}
}

$ go test -count=1 -v ./internal/render/
=== RUN   TestToScreenAndBack
--- PASS: TestToScreenAndBack (0.00s)
=== RUN   TestClampStaysOnTheMap
--- PASS: TestClampStaysOnTheMap (0.00s)
=== RUN   TestCullingKeepsThePicture
--- PASS: TestCullingKeepsThePicture (0.04s)
=== RUN   TestFrameMatchesItsHash
--- PASS: TestFrameMatchesItsHash (0.00s)
PASS
ok  	theworld/internal/render	0.044s

Sixty-four camera positions, every one of them drawn twice and compared: all sixteen offsets within a cell on each axis, and both far corners of the map walked sixteen pixels inward. With the old division in place the test fails the moment d reaches 1, at camera (449, 96), and writes the broken frame into testdata/ to be looked at. The test does not know what culling is. It knows that two ways of drawing must agree, and it asks in the places where a rounding decision changes hands.