Project: EndWise
Rush Hour, except you're standing on the board.
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.
The move model
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.
Reading a mechanics row
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.
Geometry from the grid
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.
Occlusion from gameplay AABBs
Carved tunnels & the tip
The carve, from eye level
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
}
The shear 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.
The vanishing beam
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.