Spielwerk 27: Sandkasten

A box of shapes: click and a crate, a triangle, a hexagon, an octagon or a plank drops in; hold and one drops every frame. The box takes shapes as long as your device keeps 60 frames a second, and the panel shows what that costs. This step gives the toolbox a physics world that owns its bodies, PhysicsWorld, with the collision rule as a switch and a grid that finds the pairs, measured against comparing every pair.

Play it · Source: collection-spielwerk/27-sandkasten · Toolbox 5.7.0 or later

The game

There is nothing to win and nothing ends. The box starts with a small heap, two ramps and a bump; you add to it until your device says "Voll".

• Mouse or touch: click in the box for one shape, hold for one a frame. Near the pointer they fill in where there is room, so a held press makes a heap, not a tower.
• The switches: the rule, aabb, aabb_sweep or sat_sweep; the pair search, "Gitter" or "Alle Paare"; and "Leeren", which empties the box.
• Keyboard: 1, 2 and 3 pick the rule, G switches the grid, L empties the box, S mutes.

The panel shows the frames per second over the last half second, the shapes, the pair tests of the last physics step and its milliseconds. The limit is your device, not a number. The target is 60 FPS on every screen. Below 50 the box is "Voll" and takes no more; below 40 the oldest shapes fade out until it's back over 50. Two thresholds each, so nothing flickers. The record is the most shapes the box carried at 60 FPS, per rule, with the grid and without. Switch the grid off and on and its gain is a number.

New in the toolbox: a world that owns its bodies

The problem. In step 26 the game owned its parcels: it moved them with sat_move, pushed pairs apart with sat_overlap and elastic_impact, and tested every parcel against every other one. That's fine for ten. A game with thousands of bodies (the zombie shooter in step 29) shouldn't have to write that again, and can't afford every pair.

The idea. The world keeps the bodies and steps them at a fixed rate. Each step, every moving body moves against the still ones through a collision rule, and then overlapping moving bodies are pushed apart by mass. The rule is a callback: the world doesn't care whether a shape is a box or a polygon. A grid over the bodies' boxes hands out only the pairs that share a cell. Contacts go out as events after the step, so a listener may remove a body.

const world = new PhysicsWorld<Shape>({
    rule: SAT_SWEEP,                          // or AABB, AABB_SWEEP, or your own CollisionRule
    gravity: { x: 0, y: 900 },
    restitution: 0.2,                         // only for contacts closing faster than bounce_speed (60)
    friction: 0.1,
    broad_phase: { kind: "grid", cell_size: 32 },   // or { kind: "none" }
});
const crate = world.add({ shape: SHAPES.crate, position: { x: 300, y: 40 }, data: { kind: "crate" } });
world.add({ shape: floor, position: { x: 0, y: 0 }, is_static: true });
world.events.attach(ContactEvent, (event) => thuds++);   // a, b, normal, speed
world.update(delta_seconds);                  // the fixed steps that are due, at most 4
world.remove(crate);
world.stats;                                  // bodies, pairs_tested, contacts, step_ms, steps

The three rules wrap what was there: AABB moves first and pushes out after with aabb_resolve (step 11), AABB_SWEEP uses aabb_move, SAT_SWEEP uses sat_move and sat_overlap (step 26). Layers and masks skip pairs nobody cares about: bullets don't hit bullets. Bodies still never turn.

What the switches show. Under the two aabb rules every shape is its rectangle, and the page draws the rectangles: triangles stack like crates, and a shape rests on the empty corner of a ramp's box. sat_sweep sees the real shapes, and the triangles slide off each other. aabb without the sweep lets a fast shape jump a thin ramp.

Measured. Milliseconds for one physics step, a heap of the five shapes in an open box, settled first, averaged over 60 steps (5 to 15 for every pair at 3,000 and more). Intel i7-11700F, Node 22, and headless Chromium 156 through Playwright, on Linux.

The grid wins from 100 shapes on, unlike step 22's quad tree, which lost to a plain loop: it's typed arrays sorted by cell, built anew each step, and nothing to balance. Its gain grows with the shapes: three times at 1,000, six to eight at 3,000, ten to twenty at 10,000 for the box rules. Under sat_sweep it stays at two and a half to four, because there the narrow test, not the search, is the cost. A step at 60 FPS has 16.7 ms for physics and painting together.

The record, in practice. The element itself in headless Chromium at 60 FPS, a held press swept across the box: under sat_sweep the box was "Voll" at 943 shapes with the grid and at 446 with every pair. Under the two aabb rules the box filled up first, at about 1,000, with a step under 2 ms with the grid and about 4 without: there the record measures the box, and the panel's milliseconds show the gain. A phone will tell a different story; that's what the record is for.

What using it turned up.

• A heap sank into itself. Pushing a pair apart half each way, a crate at the bottom of a pile was pushed down into the floor by the ones above it, every step, and the pile passed its weight down as speed. The world now sorts the moving bodies lowest first along gravity, and a body that rests on something still is a floor to the one on top of it: the upper one takes the whole push. A pile of 200 crates rests with no overlap over 1.
• Bounces stacked up. A little restitution at every contact in a column added up until the top crate flew. Contacts closing slower than bounce_speed (60 units a second) now don't bounce at all.
• The hits had to say which wall. aabb_move and sat_move returned hits without the wall, so the world couldn't tell which body to send a contact for. Both now give WallHit with the wall's index; nothing else changed.
• Small triangles wedge. Side by side on the floor, the push along a triangle's slanted side goes half into the floor, and the floor pushes it back. Two passes a step leave them 1.6 units into each other; the game runs four.
• No static friction. Friction only takes speed, so a shape on the bump's steep side slides, and the push goes through a whole row of shapes on the floor. A fresh heap settles within a few seconds and then creeps a few tenths of a unit for a while.
• The frame rate needs the real frame. The shell hands update() a delta capped at 0.1 s, so a slow device looked like 10 FPS at worst. properties.frame_seconds is now the frame's real length.

A test worth copying. The grid must not change what happens, only how fast:

it("finds the same contacts with the grid as with no broad phase, on a seeded scene", () => {
    const runs = [];
    for (const broad_phase of [{ kind: "none" }, { kind: "grid", cell_size: 64 }, { kind: "grid", cell_size: 17 }]) {
        const world = boxed_world({ broad_phase });
        const random = new SeededRandom(11);
        for (let index = 0; index < 150; index++) {
            world.add({ shape: index % 3 === 0 ? triangle(14) : crate(18, 12), position: ..., velocity: ..., data: index });
        }
        const events = [];
        world.events.attach(ContactEvent, (event) => events.push(`${event.a.data} ${event.b.data ?? "wall"} ${event.speed.toFixed(6)}`));
        run(world, 2);
        runs.push({ events, positions: world.bodies.map((body) => `${body.position.x.toFixed(6)},${body.position.y.toFixed(6)}`).join(" ") });
    }
    expect(runs[0].events.length).toBeGreaterThan(100);
    for (const other of runs.slice(1)) {
        expect(other.events).toEqual(runs[0].events);
        expect(other.positions).toEqual(runs[0].positions);
    }
});

Path: src/physics/world/. PhysicsWorld, PhysicsBody, CollisionRule with AABB, AABB_SWEEP and SAT_SWEEP, ContactEvent, and the broad phases GridBroadPhase and NoBroadPhase.

From earlier steps

• aabb_resolve, aabb_move and aabb_sweep from step 11, sat_overlap and sat_move from step 26: the three rules.
• elastic_impact from step 16: two shapes that meet.
• FixedStepClock from step 16 and step 17: the world's even steps. The world stops at 4 steps an update and drops the rest, so a slow frame never makes the next one slower.
• EventSocket from step 25: the contacts, and the thud, at most one every 0.12 s however many shapes land.
• UiPage, place(), is_selected and button classes from step 20: the switches.
• New in the shell: polygon() and trace_polygon(). Step 22 and step 26 each traced polygons by hand; here thousands of shapes go into one path per kind, one fill and one outline each.

The scaffold, start screen, intro and scaling are explained once in Spielwerk 00: The workbench.

Embed it

<script src="https://www.game-object.de/tce-elements/tobidot/dll-tce-assets"></script>
<script src="https://www.game-object.de/tce-elements/tobidot/tce-sandkasten"></script>
<tce-sandkasten init-seed="4711"></tce-sandkasten>

Next

Previous: Spielwerk 26: Paketrutsche · All steps · Where the series is heading: Civilization