← Writing · EndWise

Project: EndWise

Rush Hour, except you're standing on the board.

  1. Level Design
  2. Assets from Code
  3. Lighting

Level Design

Rooms are small; exhaustive BFS is cheap. The solver audits every room: solvable, optimal depth, which mechanics the solution needs, forcedness. CI checks each stored certificate against its level and replays the solution in Godot. The level atlas animates those certificates.

Caught cheese. Clustered near-duplicates.

Why BFS is enough

Rush Hour (generalized n×n) is PSPACE-complete (Flake & Baum 2002; later results push hardness down to 1×1 cars + walls). Solutions can be exponentially long in the worst case. At play scale, Fogleman (2018) enumerated ~1.5M interesting 6×6 configs in ~3 hours of C++; hardest standard position: 51 moves.

EndWise rooms: median 133 unique states, worst 75,856, branching ~5. Full 69-level audit (baseline + four mechanic-off passes, 241 solves) 1.8 s batched on a GPU vs 224 s in the old Python solver. Still plain BFS; every claim is a proof.

Move model

State = full placement of every piece + per-piece status (tipped/flat, pinned/free). The solver derives the player reachable region; it does not store it.

Heavy — endwise only; end-stance aware (where you can stand to push/pull). Pull required in much of the campaign.

Free — casters/dolly; four directions.

Pivot — pin on a corner lattice vertex; piece steps fully around it; sampled sweep includes the player on the swing.

Tip — 2×3 mattress → door-tall 1×3, one lane past the tip edge.

Pin, unpin, swing, tip, untip = one move each. Exit through a matching one-wide door. Solved when the door-in cell is reachable for everything that must leave.

FIG. 01

The move model

Four panels showing heavy, free, pivot, and tip furniture movement classes on a grid
Four verbs, one occupancy grid. Heavy slides endwise from end stances; free slides any direction; pivot pins a lattice vertex and steps fully around it; tip lands a door-tall slab one lane past the edge.

State key

One configuration index per piece (cells, axis, pin, tip) + the player cell. Rooms are at most 8×7, so occupancy and the walkable region are 64-bit bitboards; seen states are a sorted int64 key tensor — no Zobrist. Player cell canonicalized to the region: same walkable region ⇒ same node. Bitwise flood fill each expansion; store the lowest cell of the region.

Pivot sweep: 45 samples / 90° (~2°), footprint + ride-along capsule vs grid. The worst room explores ~76k states; past 250k the solver refuses the room.

Depth and mechanic columns

Optimal depths: 1–22 (level 1 is 2; the 22 is level 60; the finale is 18). Four extra runs per level: push-only, no-pivot, no-tip, all-heavy.

FIG. 03

Reading a mechanics row

Solver audit table row for cart-and-couch with push-only, no-pivot, no-tip, and all-heavy columns annotated
Each column turns a mechanic off. Unsolvable without pulling means the level teaches pull; same depth without tip means tip was never required.

no-pivot solvable at same depth → couch corner unused. push-only unsolvable → level teaches pull. Pull strictly required in 32 of 69.

Cheese: “don’t corner yourself” solved in one unanticipated pull.

Forcedness

How much of the optimal path admits alternatives vs forced march. Hand tier labels correlate poorly with depth. Generated levels are curated on an interaction metric instead; hand tiers are checked against player attempts (abandon rate, moves over par).

Duplicates

Cluster by solver signature (depth + required mechanics + solution structure) → near-duplicate groups, same puzzle in different furniture. Knock-over is not a move; a dead state means restart.


Refs: Flake & Baum, TCS 270 (2002) · Hearn & Demaine, TCS 343 (2005) · Brunner et al., FUN 2021 · Fogleman 2018 · Gardner, Sixth Book of Mathematical Diversions.

Assets from Code

Every furniture mesh compiles from the same grid JSON the level design solver reads. Authors write levels; they do not model furniture. The street outside is 26 imported .glb models.

Meshes

A mattress is exactly 2×3 cells — that size is a gameplay rule. Hand-modeled assets drifted from occupancy and lied about fit. Meshes forged in code from the footprint can’t: tip (2×3 → door-tall 1×3) is the same mesh stood on its side, same dimensions the solver uses.

FIG. 01

Geometry from the grid

Pipeline from grid level defs through generated primitives and triplanar materials to lookdev as JSON
Meshes from the grid. Materials are JSON entries; furniture meshes are forged from the same footprints the solver reads. Triplanar projection is opt-in for UV-less primitives.

Materials

No artist UVs on generated primitives, so most materials skip textures: all 31 in data/art/materials.json are flat albedo + roughness. Triplanar projection (world axes, blend by normal) is opt-in per entry for a texture that tiles.

Convention: one named entry in materials.json. The material library builds each entry it lists; no folder scan, no scene wiring to add a material.

Lookdev

data/art/lighting.json and data/art/materials.json, hot-reloaded on a keypress — AgX, low-elevation sun, SDFGI off.

Lighting

Hard-edged light shafts through windows and doorways. Furniture carves them as you drag — occluders are the same AABBs the level design solver maintains, including tip. Doorways use the same shaft treatment as windows.

FIG. 02

Occlusion from gameplay AABBs

Furniture carves the beam. Solver AABBs stream into the shader as occluders; mid-drag, the carved tunnel updates and the floor behind the piece lights up.
FIG. 02

Carved tunnels & the tip

Height is the other axis of the carve. The couch is two stacked AABBs (seat + backrest) that shadow each other; tip rotates the mattress a true 90° and lands it one lane past the edge.
FIG. 03

The carve, from eye level

What the player sees. One-point perspective of the same AABB carve: the shadow tunnel is a volume, and the beam still reads in front of the couch.

Froxel fog

Godot’s volumetric fog is a froxel grid: camera-aligned volume texture, sun shadow maps per cell, temporally smoothed. Soft edges only — a hard silhouette would sit between froxels and get smeared by the temporal filter.

Shafts are a separate system. Froxels stay at low resolution for ambient gloom.

Beams

Each beam is a parallelepiped — aperture rectangle sheared along the sun direction. A non-orthonormal shear basis maps world space to a unit cube in beam-local space; inside-test is three axis comparisons. No shadow map, no raymarch for the beam — ALU only; runs on Compatibility / web too. The lit pool on the floor is the sun’s ordinary shadow map; the analytic surface patch has been off since November.

# CPU: aperture right × up × sun-scaled depth → unit cube under xf
var shear := Basis(wall_tangent * w, Vector3.UP * h, sun_dir * depth)
var xf := Transform3D(shear, center + sun_dir * (depth * 0.5))
var inv := xf.affine_inverse()  # columns + origin uploaded as uniforms
// GPU: world → beam-local, then three comparisons against the unit cube
vec3 local = beam_cx[b] * p.x + beam_cy[b] * p.y + beam_cz[b] * p.z + beam_org[b];
if (all(lessThan(abs(local), vec3(0.5)))) {
    // fragment is inside this beam
}
FIG. 01

The shear basis

World-space window beam parallelepiped transforming into a unit cube in beam-local space for a slab test
Slanted volume, axis-aligned test. Non-orthonormal basis (u, v, w) turns “is this fragment lit?” into three comparisons — pure ALU, no shadow map.

Solver AABBs upload as occluders at full size (the 4 cm shrink came out in November, so the carve in the air matches the mesh). Shadow tunnels update mid-drag. Godot has no max-blend; overlapping additive beams double-brighten, so one union-AABB cover mesh shades each fragment once — max across ≤10 beams / ≤32 occluders in the shader.

Current path: one cover mesh over the union of the beam prisms. Per fragment, slab-test each prism, then take the exact view-ray interval inside each occluder’s shadow volume — analytic, no march.

Bugs that shaped the path

Vanishing beam. Standard back-face culling: step inside a beam, look at the window — shafts disappear. Inside a convex hull every visible face is a back-face. Fix: cull front faces, shade back faces, march the segment between.

FIG. 03

The vanishing beam

Top-down comparison of back-face culling rejecting all visible hull faces from inside the beam versus front-face culling keeping far faces for raymarching
Inside a convex hull, every visible face is a back-face. Cull front faces instead, then march camera → hull exit. Sequel: depth_draw_never does not disable depth tests.

Missing chunks. Tipped mattress → wedges of beam behind it gone. depth_draw_never only suppresses depth writes, not tests — hull fragments behind furniture die in the z-buffer before the shader runs. Fix: depth_test_disabled + manual clamp against scene depth in the shader.

Flooded doorway. Haze volume at 2× room depth flooded the door opening. Fix: fit the fog volume to the room.

Sun + shadows

Window mullion shapes on furniture come from the ordinary sun + shadow map. Soft penumbras against hard shafts look wrong, so the sun uses zero angular distance. Shadow filtering stays at the project default (soft, quality 3); only web / low-power drops it.