Chapter 20 — A Physics Sandbox

Physics stages

This chapter combines the motion, curves, random source and collision tests in one sandbox. The sandbox drops one hundred balls into a court and prints the state of ball 0 every second.

Each tick runs three stages in order. Kinematics moves every ball. Collisions push overlapping pairs apart and exchange their speeds. The border puts back any ball outside the court. The picture is drawn after the last stage, so the last stage decides what the player never sees.

Resolving a collision

∑ Math Interlude — half the depth each, and an impulse along the normal

Two balls of radius 4, one at (100, 100) moving right at 60 pixels a second and one at (107, 100) moving left at 60. Their centres are 7 apart and their radii reach 8, so the circle test reports a depth of 1 and a normal pointing from the second ball to the first, (−1, 0). Two things fix the overlap. The first is a push: each ball moves half the depth along the normal, the first to 99.5 and the second to 107.5, so that they touch and no longer overlap, and neither ball was moved further than the other. The second is a bounce, and it needs one more number: the approach speed, the difference of the two velocities dotted with the normal, (60 − (−60)) × (−1) = −120. Negative means the balls are closing; a pair that overlaps but is already separating is pushed and not bounced, or the bounce would pull them back together.

A bounce that keeps every bit of speed would send each ball away at 60; a perfectly dead one would stop them both. The restitution, 0.8, is the fraction of the approach speed kept, and the impulse that gives it is −(1 + 0.8) × (−120) / 2 = 108 along the normal, so (−108, 0). The first ball's velocity gains it, 60 − 108 = −48; the second's loses it, −60 + 108 = 48. They part at 48 each, 0.8 of 60, and the two changes are equal and opposite, so what one ball gained the other lost and the pair's total momentum is what it was. The border does the same with a wall that cannot move: the ball is put back on the edge and the part of its velocity across the edge is reversed and scaled by the same 0.8.

depth, nchapter 17's Hit for the pair: 1 and (−1, 0) for centres 7 apart with radii 4

pusheach ball moves depth/2 along n, one forward and one back: 99.5 and 107.5

approach(v₁ − v₂) · n: −120; negative is closing, and a separating pair is not bounced

ethe restitution, the fraction of the approach speed kept: 0.8; 1 loses nothing, 0 stops the pair dead

impulsen · (−(1 + e) · approach / 2) = (−108, 0); added to v₁ and taken from v₂: −48 and 48

stageskinematics, collisions in index order, border: k, c, b; the picture is drawn after b

Figure 20.1 — the interlude's bounce: the overlap and the normal before the collision stage, the push and the parting speeds after it.

Building the sandbox

Extend cmd/motion with the sandbox lab. The lab places one hundred balls from one Source seeded by -seed. Each ball starts on a cubic, gets a normal nudge, gets a random velocity and chooses a small or large radius from a weighted pick.

Every tick runs kinematics, collisions and the border. Every sixtieth tick for ten seconds, the lab prints ball 0, the number of resolved pairs and the deepest any ball ended below the floor. Ball 0 is blue. Big balls are gold.

▣ Build · stage 1 — the sandbox, and its name in newLab

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

import (
	"fmt"
	"math"

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

	"gez/internal/vec"
)

// The sandbox: a hundred circles of two radii, dropped from a seeded start
// along a curve, under gravity and drag, bouncing off the court's border
// and off each other. Every tick runs three stages in one order:
// kinematics, then every pair's collision in index order, then the border.
// The lab prints ball 0 every sixty ticks for ten seconds.
const (
	sandN           = 100
	sandSmall       = 4.0 // the two radii, in pixels
	sandBig         = 6.0
	sandGravity     = 600.0 // pixels a second a second
	sandDrag        = 0.99  // the velocity keeps this much of itself a tick
	sandRestitution = 0.8   // the fraction of the approach speed kept after a bounce
	sandTop         = 14.0  // the border: the picture between the two lines
	sandBottom      = screenH - 14.0
	sandEvery       = 60  // ticks between printed lines
	sandUntil       = 600 // the last tick printed
)

// sandCurve is the curve the balls are dropped along: a cubic across the
// upper part of the picture.
var sandCurve = [4]vec.Vec2{{X: 20, Y: 60}, {X: 100, Y: 30}, {X: 220, Y: 90}, {X: 300, Y: 40}}

// sandRadii is the weighted choice of a ball's radius: three small balls
// to every big one.
var sandRadii = vec.NewWeighted(3, 1)

type sandbox struct {
	tick     int
	seed     uint64
	balls    []vec.Body
	radii    []float64
	resolved int     // pairs resolved since the last printed line
	deepest  float64 // the most any ball has ended a tick below the floor since then
}

// newSandbox works one head-on bounce by hand and prints it, then places
// the balls from the seed.
func newSandbox(seed uint64) *sandbox {
	i, j := bodyAt(100, 100, 60, 0), bodyAt(107, 100, -60, 0)
	h, _ := vec.OverlapCircles(vec.Circle{Centre: i.Pos, R: sandSmall}, vec.Circle{Centre: j.Pos, R: sandSmall})
	approach := i.Vel.Sub(j.Vel).Dot(h.Normal)
	impulse := h.Normal.Scale(-(1 + sandRestitution) * approach / 2)
	fmt.Printf("two balls of radius %.0f, centres 7 apart, closing at 60 each: depth %.4f, normal %v\n", sandSmall, h.Depth, h.Normal)
	fmt.Printf("  each moved %.4f along the normal; approach speed %.4f; impulse %v\n", h.Depth/2, approach, impulse)
	fmt.Printf("  velocities after: %v and %v, %.4f of the approach speed kept\n", i.Vel.Add(impulse), j.Vel.Sub(impulse), sandRestitution)
	s := &sandbox{seed: seed}
	s.start()
	return s
}

// bodyAt is a body at a position with a velocity.
func bodyAt(x, y, vx, vy float64) vec.Body {
	return vec.Body{Pos: vec.Vec2{X: x, Y: y}, Vel: vec.Vec2{X: vx, Y: vy}}
}

// start places the balls from the seed: ball i sits on the curve at
// t = i/99, nudged by a normal of spread four, with a small uniform
// velocity, and is small or big by the weighted pick. One Source, in
// this order, so that the same seed gives the same start.
func (s *sandbox) start() {
	src := vec.NewSource(s.seed)
	s.balls, s.radii = s.balls[:0], s.radii[:0]
	for i := 0; i < sandN; i++ {
		t := float64(i) / float64(sandN-1)
		p := vec.Cubic(sandCurve[0], sandCurve[1], sandCurve[2], sandCurve[3], t)
		p = p.Add(vec.Vec2{X: src.Normal(0, 4), Y: src.Normal(0, 4)})
		v := vec.Vec2{X: src.Uniform(-60, 60), Y: src.Uniform(-60, 60)}
		r := sandSmall
		if sandRadii.Pick(src) == 1 {
			r = sandBig
		}
		s.balls = append(s.balls, vec.Body{Pos: p, Vel: v})
		s.radii = append(s.radii, r)
	}
	s.tick, s.resolved, s.deepest = 0, 0, 0
}

// step runs the tick's stages; R starts again from the seed. Every sixty
// ticks, up to six hundred, the lab prints ball 0 and what the stages did.
func (s *sandbox) step(k keys) {
	if k.r {
		s.start()
	}
	s.tick++
	s.stages()
	for i, b := range s.balls {
		s.deepest = math.Max(s.deepest, b.Pos.Y+s.radii[i]-sandBottom)
	}
	if s.tick%sandEvery == 0 && s.tick <= sandUntil {
		b := s.balls[0]
		fmt.Printf("tick %d  ball 0 pos %v vel %v  %d pairs resolved  deepest below the floor %.4f\n", s.tick, b.Pos, b.Vel, s.resolved, s.deepest)
		s.resolved, s.deepest = 0, 0
	}
}

// stages runs the three stages in the chapter's order: kinematics, then
// the collisions, then the border.
func (s *sandbox) stages() {
	s.kinematics()
	s.collisions()
	s.border()
}

// kinematics: gravity into every acceleration, then one semi-implicit
// Euler step for each ball.
func (s *sandbox) kinematics() {
	for i := range s.balls {
		s.balls[i].Acc = vec.Vec2{Y: sandGravity}
		s.balls[i] = s.balls[i].Step(sandDrag)
	}
}

// collisions: every pair once, in index order. An overlapping pair is
// pushed apart by half the depth each along the normal, and, if the two
// are approaching, given equal and opposite impulses along it that keep
// a fraction of the approach speed, the restitution.
func (s *sandbox) collisions() {
	for i := range s.balls {
		for j := i + 1; j < len(s.balls); j++ {
			a, b := vec.Circle{Centre: s.balls[i].Pos, R: s.radii[i]}, vec.Circle{Centre: s.balls[j].Pos, R: s.radii[j]}
			h, ok := vec.OverlapCircles(a, b)
			if !ok {
				continue
			}
			s.resolved++
			push := h.Normal.Scale(h.Depth / 2)
			s.balls[i].Pos = s.balls[i].Pos.Add(push)
			s.balls[j].Pos = s.balls[j].Pos.Sub(push)
			approach := s.balls[i].Vel.Sub(s.balls[j].Vel).Dot(h.Normal)
			if approach >= 0 {
				continue // already separating
			}
			impulse := h.Normal.Scale(-(1 + sandRestitution) * approach / 2)
			s.balls[i].Vel = s.balls[i].Vel.Add(impulse)
			s.balls[j].Vel = s.balls[j].Vel.Sub(impulse)
		}
	}
}

// border: a ball past an edge is put back on it and its velocity across
// the edge is reversed and scaled by the restitution.
func (s *sandbox) border() {
	for i := range s.balls {
		b, r := &s.balls[i], s.radii[i]
		if b.Pos.X < r {
			b.Pos.X, b.Vel.X = r, -b.Vel.X*sandRestitution
		}
		if b.Pos.X > screenW-r {
			b.Pos.X, b.Vel.X = screenW-r, -b.Vel.X*sandRestitution
		}
		if b.Pos.Y < sandTop+r {
			b.Pos.Y, b.Vel.Y = sandTop+r, -b.Vel.Y*sandRestitution
		}
		if b.Pos.Y > sandBottom-r {
			b.Pos.Y, b.Vel.Y = sandBottom-r, -b.Vel.Y*sandRestitution
		}
	}
}

func (s *sandbox) draw(screen *ebiten.Image, h *hud) {
	vector.StrokeRect(screen, 0.5, sandTop+0.5, screenW-1, sandBottom-sandTop-1, 1, dimColor, false)
	for i, b := range s.balls {
		c := lineColor
		if i == 0 {
			c = xColor
		} else if s.radii[i] == sandBig {
			c = yColor
		}
		vector.StrokeCircle(screen, float32(b.Pos.X), float32(b.Pos.Y), float32(s.radii[i]), 1, c, false)
	}
}

func (s *sandbox) lines() (top, bottom string) {
	b := s.balls[0]
	return fmt.Sprintf("tick %d  seed %d", s.tick, s.seed),
		fmt.Sprintf("ball 0 pos %v  vel %v", b.Pos, b.Vel)
}

// cmd/motion/main.go — extend
// 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
	case "shapes":
		return newShapesLab(), nil
	case "grid":
		return newGridLab(), nil
	case "curves":
		return newCurvesLab(), nil
	case "sandbox":
		return newSandbox(seed), nil
	}
	return nil, fmt.Errorf("no lab called %q", name)
}

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

A dim rectangle filling the picture between the two text lines, and a hundred small outlined circles, most white and a quarter of them gold and a little larger, scattered along a gentle curve across the upper part of the court, one of them blue at the far left. The top line reads tick 0 seed 1 and the bottom ball 0 pos (17.0478, 59.9829) vel (-54.0001, -1.2644).

The window when the lab opens: a hundred balls along the cubic, each nudged off it by its two normals, three in four small and white, one in four big and gold, and ball 0 blue.

$ go run ./cmd/motion -lab sandbox
two balls of radius 4, centres 7 apart, closing at 60 each: depth 1.0000, normal (-1.0000, 0.0000)
  each moved 0.5000 along the normal; approach speed -120.0000; impulse (-108.0000, 0.0000)
  velocities after: (-48.0000, 0.0000) and (48.0000, 0.0000), 0.8000 of the approach speed kept
tick 60  ball 0 pos (24.5253, 140.8854) vel (59.8972, 23.8741)  1468 pairs resolved  deepest below the floor 0.0000
tick 120  ball 0 pos (21.4561, 152.4286) vel (-12.0904, 1.7009)  5895 pairs resolved  deepest below the floor 0.0000
tick 180  ball 0 pos (20.4773, 151.9856) vel (-5.3717, 14.5422)  9959 pairs resolved  deepest below the floor 0.0000
tick 240  ball 0 pos (20.7731, 151.9512) vel (-2.7535, 17.5399)  9979 pairs resolved  deepest below the floor 0.0000
tick 300  ball 0 pos (20.8395, 152.1032) vel (-0.0882, 5.0525)  9901 pairs resolved  deepest below the floor 0.0000
tick 360  ball 0 pos (20.7230, 152.0591) vel (0.7636, 5.4143)  9894 pairs resolved  deepest below the floor 0.0000
tick 420  ball 0 pos (20.6966, 152.1977) vel (1.9966, -6.3094)  9931 pairs resolved  deepest below the floor 0.0000
tick 480  ball 0 pos (20.7041, 152.1981) vel (0.4780, -6.7767)  9935 pairs resolved  deepest below the floor 0.0000
tick 540  ball 0 pos (20.7601, 152.2711) vel (0.3307, 0.7415)  9916 pairs resolved  deepest below the floor 0.0000
tick 600  ball 0 pos (20.6425, 152.0338) vel (-0.0020, 6.1044)  9917 pairs resolved  deepest below the floor 0.0000

The court with all hundred balls in a pile two and three deep along the floor, white and gold mixed, one gold ball a little above the rest, and the blue ball at the far left of the bottom row. The top line reads tick 300 seed 1, the bottom ball 0 pos (20.8395, 152.1032) vel (-0.0882, 5.0525), and the tick count reads 300.

Five seconds in: the pile, with every ball on or above the floor and ball 0 at the bottom left, in the second row.

The same pile at tick 600, the balls in almost the same places, the blue ball still at the bottom left. The bottom line reads ball 0 pos (20.6425, 152.0338) vel (-0.0020, 6.1044).

Ten seconds in: the pile has settled into the arrangement it will keep, still resolving nearly ten thousand pairs a second as the balls press on one another.

The first three lines are the interlude's collision, printed by the same arithmetic the pile uses. The ten lines after that are the run.

Ball 0 falls to the floor by the second printed line and settles near the corner. The resolved pairs climb from 1,468 in the first second to about 9,900 a second once the pile has formed. The last column stays 0.0000 because the border runs after collisions.

collisions walks each pair once, with j starting at i+1. It resolves each pair as it finds it. A ball pushed by one neighbour is already in its new position when the next pair tests it.

A separating pair is pushed apart but not bounced. The approach >= 0 test prevents a resting pile from gaining speed every tick. The start draws from one Source in one fixed order, so seed 1 builds the same hundred balls every run.

⚙ Tool — a hundred strokes a frame, and no broad phase

Ebitengine draws the hundred outlines with vector.StrokeCircle. The arithmetic that places them belongs to the sandbox.

The collision stage tests all 4,950 pairs every tick and doesn't skip distant pairs. One hundred balls can afford that. Ten thousand balls would test almost fifty million pairs a tick and would need a grid that tests nearby balls only.

Changing stage order

Add a flag that runs the same stages in different orders. The default order is kcb: kinematics, collisions, border. The failure uses another order.

▣ Build · stage 2 — the stage order on a flag, extend cmd/motion/sandbox.go

// cmd/motion/sandbox.go — extend
import (
	"flag"
	"fmt"
	"log"
	"math"

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

	"gez/internal/vec"
)

// stages runs the three stages in the order the flag names, read left to
// right: k for kinematics, c for the collisions, b for the border. The
// default is kcb; the other five are kept so they can be run.
func (s *sandbox) stages() {
	for _, stage := range *stageOrder {
		switch stage {
		case 'k':
			s.kinematics()
		case 'c':
			s.collisions()
		case 'b':
			s.border()
		default:
			log.Fatalf("stages %q: want three of k, c and b", *stageOrder)
		}
	}
}

var stageOrder = flag.String("stages", "kcb", "the order the sandbox runs its stages in: k kinematics, c collisions, b border; kcb is the right one, and the others are kept so they can be run")

go vet ./...
go run ./cmd/motion -lab sandbox
go run ./cmd/motion -lab sandbox -stages bkc

With the default, the run is unchanged. bkc prints the same positions and velocities for ball 0 because the extra border at the front does nothing while balls are inside the court.

The last column changes. bkc ends each tick after collisions, so the picture can show balls that a collision push left below the floor. Where the tick ends is where the picture is taken.

⚠ Worked failure — the border first, the kinematics last, and balls through the floor

Put the border first and the kinematics last, -stages bck, which is the order that suggests itself when the border is thought of as "make everything legal, then move":

$ go run ./cmd/motion -lab sandbox -stages bck
tick 60  ball 0 pos (12.4661, 149.4104) vel (36.1874, 23.0224)  1396 pairs resolved  deepest below the floor 7.7158
tick 120  ball 0 pos (12.9104, 152.4867) vel (-2.6894, 13.4531)  5044 pairs resolved  deepest below the floor 5.3944
tick 180  ball 0 pos (13.8638, 146.8484) vel (0.2158, 15.6339)  8516 pairs resolved  deepest below the floor 1.5213
tick 240  ball 0 pos (16.9400, 146.5753) vel (-3.5727, 13.0475)  8465 pairs resolved  deepest below the floor 1.2266

The court a second in, balls still falling from the curve, with the lowest row of balls cut off by the floor line: several white and gold outlines have their lower halves below the border. The top line reads tick 60 seed 1 and the bottom ball 0 pos (12.4661, 149.4104) vel (36.1874, 23.0224); the tick count reads 60.

The lab under -stages bck at tick 60: the bottom row of balls drawn through the floor, the deepest 7.7 pixels down, which is a whole ball's diameter below where the border would have put it.

The last column is 7.7158 in the first second, and the picture shows the bottom row cut by the floor. The border ran first, before the balls moved, so it had nothing to fix. Then collisions ran. Then kinematics moved each ball, and the tick ended below the floor.

The next tick's border puts the balls back, so they don't escape. But the frame has already shown the wrong state. Put the order back to kcb: move, resolve overlaps, fix the border, then draw.

Ordering physics stages

Each stage reads the state left by the stage before it. Kinematics creates overlaps. Collisions fix overlaps and may push balls into the border. The border fixes the court boundary. Put a stage after the state it needs and before the state that needs it.

The sandbox doesn't read the wall clock or an unseeded generator. It walks pairs in one order. Those choices make seed 1 produce the same ten seconds of motion each time. A larger physics engine adds more body types and a broad phase, but it still needs fixed inputs and a clear stage order.

Checkpoint

✓ Checkpoint — what you can now do

Resolve one head-on collision by hand: half the depth each along the normal, then an impulse of −(1 + e) times the approach speed over two, to −48 and 48.
Say why a separating pair is pushed and not bounced, and what a pile does without that test.
Place a hundred balls from one seed in one order so that seed 1 is the same hundred every run.
Read 9,901 pairs a second off a resting pile and say what it means about a pile that is not asleep.
Explain why bkc prints the same ball 0 as kcb and a different last column, from where the tick ends.
Take a picture of balls through the floor back to the stage that ran last, and say what the fix is.

⚡ Exercises — try first, then reveal

Exercise 1 — a dead pile. Set the restitution to 0 and then to 1, and read the pairs-resolved column and the last line's velocity for each.

At 0 every bounce stops the pair's approach dead, the pile lands and goes quiet, and the pairs resolved a second fall to the hundreds, the pushes of balls resting on one another; ball 0's velocity on the last line is under a pixel a second. At 1 nothing is lost in a bounce, the balls never settle, and the pile keeps hopping for as long as the lab runs, with ball 0's velocity in the tens. The 0.8 the lab ships with is a choice between the two, made for a pile that lands in a few seconds and still looks like it has weight.

Exercise 2 — a heavier ball. Give the big balls twice the mass, so that a big ball hitting a small one keeps more of its speed.

With masses m_i and m_j, the impulse's magnitude is −(1 + e) × approach / (1/m_i + 1/m_j), applied to each velocity divided by that ball's mass, and the push is split in the same proportion. For equal masses that is the lab's formula; for 2 against 1 the small ball takes two thirds of the separation and the big ball keeps two thirds of its speed. Watch a gold ball plough through white ones.

Exercise 3 — a fourth stage. Add a sleep stage after the border: a ball whose speed has been under two pixels a second for a whole second is marked asleep, drawn dim, and skipped by the integrator until something hits it. How many pairs does a sleeping pile resolve?

A counter per ball, incremented while its speed is under the threshold and reset otherwise; at sixty the ball sleeps, and a collision impulse wakes it and clears the counter. Sleeping balls skip kinematics and are still tested in collisions, so the pile holds its shape and the pairs resolved fall to the few that awake balls cause. The stage goes after the border, because it reads speeds the border has changed; put it before the border and a ball can fall asleep in the floor.