Seeded Randomness

// internal/vec/random.go — create
package vec

import (
	"math"
	"math/rand/v2"
)

// Source is one random number generator, seeded once and passed by hand
// to everything that draws from it, so that the same seed gives the same
// numbers in the same order however many things share it. It counts its
// draws, and it keeps the spare half of a Box–Muller pair.
type Source struct {
	rng      *rand.Rand
	Draws    int     // uniform numbers taken from the generator so far
	spare    float64 // the second normal of the last pair, if unused
	hasSpare bool
}

// NewSource seeds a PCG generator, the same kind Pong serves and Snake
// places food with.
func NewSource(seed uint64) *Source {
	return &Source{rng: rand.New(rand.NewPCG(seed, 0))}
}

// Float is one draw: a number in [0, 1), counted.
func (s *Source) Float() float64 {
	s.Draws++
	return s.rng.Float64()
}

// Uniform is a number spread evenly across [lo, hi): one draw, lerped.
func (s *Source) Uniform(lo, hi float64) float64 {
	return Lerp(lo, hi, s.Float())
}

// Weighted is a table of outcomes with weights, summed once, so that a
// pick is one draw scaled by the total and one walk down the table.
type Weighted struct {
	weights []float64
	total   float64
}

// NewWeighted takes the weights in outcome order; a weight is any
// non-negative number, and the chance of an outcome is its weight over
// the total.
func NewWeighted(weights ...float64) Weighted {
	w := Weighted{weights: append([]float64(nil), weights...)}
	for _, x := range weights {
		w.total += x
	}
	return w
}

// Pick returns the index of one outcome: a draw scaled to the total falls
// somewhere along the weights laid end to end, and the weight it falls in
// is the answer.
func (w Weighted) Pick(s *Source) int {
	r := s.Float() * w.total
	for i, x := range w.weights {
		if r < x {
			return i
		}
		r -= x
	}
	return len(w.weights) - 1
}

// Normal is a number bunched round mean with a spread of sd, by
// Box–Muller: two uniform draws make two independent normals, a radius
// from the first and an angle from the second; one is returned and the
// other is kept for the next call, so that a sample costs one draw on
// average.
func (s *Source) Normal(mean, sd float64) float64 {
	if s.hasSpare {
		s.hasSpare = false
		return mean + sd*s.spare
	}
	u1, u2 := s.Float(), s.Float()
	r := math.Sqrt(-2 * math.Log(1-u1)) // 1 − u1 is never 0, so the log is finite
	th := 2 * math.Pi * u2
	s.spare, s.hasSpare = r*math.Sin(th), true
	return mean + sd*r*math.Cos(th)
}

// MeanSpread is the mean of a sample and its standard deviation: the
// square root of the mean squared distance from the mean.
func MeanSpread(xs []float64) (mean, sd float64) {
	if len(xs) == 0 {
		return 0, 0
	}
	for _, x := range xs {
		mean += x
	}
	mean /= float64(len(xs))
	for _, x := range xs {
		sd += (x - mean) * (x - mean)
	}
	return mean, math.Sqrt(sd / float64(len(xs)))
}

go vet ./...

Source is a pointer type because a generator has state. Every draw advances it. Copying the generator would copy its place in the sequence and risk drawing the same values twice.

Pass *Source by hand. A function signature that takes one shows that the function draws random values and shows which sequence it uses. Draws counts the flat draws so the lab can check its total.

Weighted stores its total when it is built. A pick then costs one draw, one multiplication and one walk through the table. The last return gives an answer even if rounding carries the draw to the end.

// cmd/motion/dots.go — create
package main

import (
	"fmt"

	"github.com/hajimehoshi/ebiten/v2"
	"github.com/hajimehoshi/ebiten/v2/vector"

	"gez/internal/vec"
)

// The dots lab bursts three hundred samples from each of three
// distributions into three panels, all from one seeded source: positions
// spread flat across a panel, a pick from four weighted outcomes shown as
// four bars, and positions bunched round the panel's middle. R bursts
// again from the same seed; Right and Left burst from the next seed and
// the last.
const (
	dotsN     = 300  // samples a panel
	panelW    = 96.0 // a panel's width and height in pixels
	panelH    = 120.0
	panelTop  = 28.0
	panelStep = 104.0 // from one panel's left edge to the next
)

// dotsWeights are the four outcomes' weights: the fourth is four times as
// likely as the first.
var dotsWeights = vec.NewWeighted(1, 2, 3, 4)

// dotsLab keeps the seed it last burst from, what the burst produced, and
// the keys of the last tick, so that a held arrow bursts once.
type dotsLab struct {
	seed    uint64
	uniform []vec.Vec2
	counts  [4]int
	normal  []vec.Vec2
	draws   int
	was     keys
}

func newDotsLab(seed uint64) *dotsLab {
	l := &dotsLab{seed: seed}
	l.burst()
	return l
}

// burst draws every dot again from a fresh source seeded with the lab's
// seed, and prints what the three panels hold.
func (l *dotsLab) burst() {
	s := vec.NewSource(l.seed)
	l.uniform, l.normal, l.counts = l.uniform[:0], l.normal[:0], [4]int{}
	for i := 0; i < dotsN; i++ {
		l.uniform = append(l.uniform, vec.Vec2{X: s.Uniform(0, panelW), Y: s.Uniform(0, panelH)})
	}
	for i := 0; i < dotsN; i++ {
		l.counts[dotsWeights.Pick(s)]++
	}
	for i := 0; i < dotsN; i++ {
		l.normal = append(l.normal, vec.Vec2{X: s.Normal(48, 12), Y: s.Normal(60, 15)})
	}
	l.draws = s.Draws
	um, us, nm, ns := l.stats()
	fmt.Printf("seed %d: uniform x mean %.4f spread %.4f (48 and 27.7128 for a flat 0..96); weighted 1:2:3:4 counts %v (30, 60, 90 and 120 expected); normal x mean %.4f spread %.4f (48 and 12 asked for); %d draws\n",
		l.seed, um, us, l.counts, nm, ns, l.draws)
}

// stats reads the three panels: the mean and spread of the flat panel's
// x, and of the bunched panel's x.
func (l *dotsLab) stats() (um, us, nm, ns float64) {
	xs := make([]float64, dotsN)
	for i, p := range l.uniform {
		xs[i] = p.X
	}
	um, us = vec.MeanSpread(xs)
	for i, p := range l.normal {
		xs[i] = p.X
	}
	nm, ns = vec.MeanSpread(xs)
	return um, us, nm, ns
}

// step bursts on R, and on the tick Right or Left goes down.
func (l *dotsLab) step(k keys) {
	switch {
	case k.r:
		l.burst()
	case k.right && !l.was.right:
		l.seed++
		l.burst()
	case k.left && !l.was.left && l.seed > 0:
		l.seed--
		l.burst()
	}
	l.was = k
}

func (l *dotsLab) draw(screen *ebiten.Image, h *hud) {
	for i, name := range []string{"uniform", "weighted 1:2:3:4", "normal"} {
		x0 := 8 + float64(i)*panelStep
		vector.StrokeRect(screen, float32(x0), panelTop, panelW, panelH, 1, dimColor, false)
		h.text(screen, name, x0, panelTop+panelH+2)
	}
	for _, p := range l.uniform {
		vector.FillRect(screen, float32(8+p.X), float32(panelTop+p.Y), 1, 1, lineColor, false)
	}
	for i, c := range l.counts {
		hgt := float32(c)
		vector.FillRect(screen, float32(8+panelStep+float64(i)*24+4), float32(panelTop+panelH)-hgt, 16, hgt, yColor, false)
	}
	for _, p := range l.normal {
		vector.FillRect(screen, float32(8+2*panelStep+p.X), float32(panelTop+p.Y), 1, 1, lineColor, false)
	}
}

func (l *dotsLab) lines() (top, bottom string) {
	um, us, nm, ns := l.stats()
	return fmt.Sprintf("seed %d  draws %d  counts %v", l.seed, l.draws, l.counts),
		fmt.Sprintf("uniform x %.4f +- %.4f  normal x %.4f +- %.4f", um, us, nm, ns)
}

// cmd/motion/main.go — extend
var (
	labFlag  = flag.String("lab", "circle", "the lab to open")
	seedFlag = flag.Uint64("seed", 1, "the seed a lab that draws random numbers starts from")
)

// newLab builds the lab named, from the seed: the one place a name
// becomes a lab. Labs that draw no random numbers ignore the seed.
func newLab(name string, seed uint64) (lab, error) {
	switch name {
	case "circle":
		return newCircleLab(), nil
	case "arrows":
		return newArrowsLab(), nil
	case "ship":
		return newShipLab(), nil
	case "ball":
		return newBallLab(), nil
	case "ease":
		return newEaseLab(), nil
	case "dots":
		return newDotsLab(seed), nil
	}
	return nil, fmt.Errorf("no lab called %q", name)
}

func main() {
	flag.Parse()
	l, err := newLab(*labFlag, *seedFlag)
	if err != nil {
		log.Fatal(err)
	}
	h, err := newHUD()
	if err != nil {
		log.Fatal(err)
	}
	ebiten.SetWindowSize(960, 540)
	ebiten.SetWindowTitle("Motion: " + *labFlag)
	ebiten.SetTPS(60)
	if err := ebiten.RunGame(&Game{lab: l, hud: h}); err != nil {
		log.Fatal(err)
	}
}

go vet ./...
go run ./cmd/motion -lab dots

The window when the lab opens, seed 1: a flat square, four bars in the ratio the weights asked for, give or take, and a cloud with its middle where the mean was put.

Press R, then Right, then Left:

$ go run ./cmd/motion -lab dots
seed 1: uniform x mean 46.8191 spread 28.6623 (48 and 27.7128 for a flat 0..96); weighted 1:2:3:4 counts [19 66 98 117] (30, 60, 90 and 120 expected); normal x mean 48.1587 spread 11.4405 (48 and 12 asked for); 1500 draws
seed 1: uniform x mean 46.8191 spread 28.6623 (48 and 27.7128 for a flat 0..96); weighted 1:2:3:4 counts [19 66 98 117] (30, 60, 90 and 120 expected); normal x mean 48.1587 spread 11.4405 (48 and 12 asked for); 1500 draws
seed 2: uniform x mean 47.3415 spread 28.7626 (48 and 27.7128 for a flat 0..96); weighted 1:2:3:4 counts [32 66 82 120] (30, 60, 90 and 120 expected); normal x mean 48.1740 spread 12.0402 (48 and 12 asked for); 1500 draws
seed 1: uniform x mean 46.8191 spread 28.6623 (48 and 27.7128 for a flat 0..96); weighted 1:2:3:4 counts [19 66 98 117] (30, 60, 90 and 120 expected); normal x mean 48.1587 spread 11.4405 (48 and 12 asked for); 1500 draws

Seed 2, after Right: a new list of fifteen hundred draws, and the numbers move by about what three hundred samples' worth of scatter allows.

The first and second lines match, and the first and fourth match. R repeats seed 1. Left after Right returns to seed 1. Both make a fresh Source and draw the same fifteen hundred numbers in the same order.

The count is fifteen hundred, not eighteen hundred, because Normal keeps a spare value. The lab uses six hundred draws for the flat positions, three hundred for the weighted picks and six hundred for the normal positions.

The printed numbers sit beside the expected values, and they don't equal them. The flat panel's mean is 46.82 against 48. Its spread is 28.66 against 27.71. The weighted counts are 19, 66, 98 and 117 against 30, 60, 90 and 120.

Those gaps are normal for three hundred samples. Seed 2 gives counts of 32, 66, 82 and 120. It is not a better seed; its gaps landed elsewhere.

The panels draw from stored dots and counts, not from the generator. Ebitengine may call Draw more or fewer times than Update. Drawing from the generator would change the picture between ticks.

Right and Left burst only on the tick the key goes down. A held arrow would otherwise burst once per tick and skip past the seed the player meant to choose.

// cmd/motion/dots.go — extend
import (
	"flag"
	"fmt"
	"math/rand/v2"

	"github.com/hajimehoshi/ebiten/v2"
	"github.com/hajimehoshi/ebiten/v2/vector"

	"gez/internal/vec"
)

// burst draws every dot again from a fresh source seeded with the lab's
// seed, and prints what the three panels hold. Under -global the source
// is seeded from the package's own generator, which nobody seeded, so the
// seed is whatever the machine had: the mistake this chapter shows, kept
// so it can be seen.
func (l *dotsLab) burst() {
	seed := l.seed
	if *global {
		seed = rand.Uint64()
	}
	s := vec.NewSource(seed)
	l.uniform, l.normal, l.counts = l.uniform[:0], l.normal[:0], [4]int{}
	for i := 0; i < dotsN; i++ {
		l.uniform = append(l.uniform, vec.Vec2{X: s.Uniform(0, panelW), Y: s.Uniform(0, panelH)})
	}
	for i := 0; i < dotsN; i++ {
		l.counts[dotsWeights.Pick(s)]++
	}
	for i := 0; i < dotsN; i++ {
		l.normal = append(l.normal, vec.Vec2{X: s.Normal(48, 12), Y: s.Normal(60, 15)})
	}
	l.draws = s.Draws
	um, us, nm, ns := l.stats()
	fmt.Printf("seed %d: uniform x mean %.4f spread %.4f (48 and 27.7128 for a flat 0..96); weighted 1:2:3:4 counts %v (30, 60, 90 and 120 expected); normal x mean %.4f spread %.4f (48 and 12 asked for); %d draws\n",
		l.seed, um, us, l.counts, nm, ns, l.draws)
}

var global = flag.Bool("global", false, "seed each burst from the package's own unseeded generator instead of the lab's seed: the mistake, kept so it can be seen")

go vet ./...
go run ./cmd/motion -lab dots

Without the flag, the lab still prints the same lines for the same keys. Under the flag, one line changes: seed = rand.Uint64(). The program hands that untyped seed to NewSource.

The printed line still says seed 1 because it prints the lab's field. That is part of the bug: the program reports a seed it didn't use.