Crossing

Frogger. Five lanes of traffic one way, five lanes of river the other, and five bays to fill at the top. Three lives, thirty seconds a crossing.

Open index.html. No build step, no dependencies, no images — the field is drawn.

crossing/
  index.html      markup, and the d-pad
  style.css       the frame around the canvas
  js/lanes.js     the traffic, the river, the search and the arithmetic
                  - no pixels, no engine, no DOM
  js/crossing.js  the playable layer
  test-lanes.js   node test-lanes.js

The claim on the card

If a crossing cannot be made without luck, the pattern does not ship.

Patterns are generated, so that is a promise about code rather than about a level designer's judgement. patternFor rolls a pattern, searches it for a route, walks the route again more finely to confirm it, and throws the pattern away if either step fails. Each rejection widens the road gaps and narrows the river gaps a little, so retrying converges rather than wandering, and there is a hard-coded floor underneath in case it ever does not.

Keeping that promise at run time, on a phone, needed two decisions.

A lane is a formula, not a list

Bodies of equal length sit at equal spacing on an endless line that slides at a constant speed. What covers a point is then one modulo:

covered(x, t)  <=>  mod(x - phase - dir * speed * t, period) < length

Nothing is spawned and nothing is culled. The lane at t = 900 costs exactly what the lane at t = 0 costs, and — because it is a closed form — a search can ask about any moment without simulating its way there.

The same expression answers both halves of the game. On a road, covered means a lorry and the frog is dead. On the river, covered means a log and the frog is alive. One function, opposite answers, which is the whole shape of Frogger.

One modulo is also exactly the kind of expression that is either right or subtly wrong about a sign and looks identical either way, so the test walks the actual bodies — the slow, obvious, unarguable way — and demands the two agree at 24,000 points, at negative times included.

The search steps an eighth of a second and is still exact

The obvious worry about a coarse search is a fast car slipping between two steps and being missed. It cannot happen here, and not because the step is small:

every speed is a whole number of cells per second, capped at 8
the step is 1/8 s, so nothing moves more than one cell per step
every body is at least two cells long

A body therefore always overlaps itself between one step and the next. Anything that passes over a point is on that point at one end of the step or the other, so checking the ends checks everything. The search is not a sampling of the game — it is the game, played to one rule tighter (see below).

That also makes the drift exact rather than rounded. Drift is cells per second and a step is an eighth of a second, so a ride shifts the frog by speed/8 cells — which in eighths is exactly speed, a whole number. Nothing ever lands between two representable positions.

The test does not take that argument on trust. It sweeps 288,000 samples between steps looking for something that slipped past, finds none, and then builds a body a quarter of a cell long and shows that one does slip through. The length rule is doing the work, and the test says so out loud.

$ node test-lanes.js
54 passed, 0 failed

The search is stricter than the game

The first version of this was exact and still wrong, which took some finding.

Routes the search approved and verify confirmed killed the frog anyway once the game replayed them — and replaying at 1/60 s failed more often than replaying at 1/8 s, which is the wrong way round for anything caused by a coarse step. Driving the game along approved routes and printing where the frog actually died gave the answer at once: it was landing exactly on a log's leading edge, or exactly on a car's back bumper, or exactly on the lip of a bay.

On a boundary, u < length is decided by the last bit of a double. The search reaches a moment as an exact eighth and gets one answer; the game reaches the same moment by adding up frames, arrives at 0.749999999999998, and gets the other. The frog drowns on solid timber.

More precision would have been the wrong fix, because the arithmetic was not really the problem. A route that needs the frog to balance on a boundary was never a fair route to promise. So the search now plays to a stricter rule than the game: Lanes.MARGIN, a sixty-fourth of a cell, demanded at every boundary a route can be planned onto.

boundary	the game allows	the search demands
ends of a body	on the log at all	a 64th inside it
gap between cars	not touching one	a 64th clear of both
edge of the field	on the field	a 64th inside it
a bay's catch	the lip counts	a 64th inside the opening

The direction is the point: the search is never the looser of the two, so anything it approves still stands when the game rules on it. Driving the game along approved routes now gets home 560 times out of 560, across six sub-step sizes including deliberately awkward ones.

That check lives in the suite rather than only in a browser. replay works out which hops a route implies and performs them, carrying one position across the whole crossing the way the game carries one. Reading each landing back out of the route instead would reset the arithmetic every step and hide the very drift it exists to find — which is what the first version did, and a mutant caught it.

What the tests are worth

Nine mutants were run against the suite. Eight broke something real; the ninth changed nothing on purpose, as a control that the harness does not simply fail on any edit at all.

mutation	result
`coversAt` drifts the wrong way	caught (6 assertions)
`verify` always agrees	caught (4)
the generator emits gapless roads	caught (4)
`safeAt` ignores the margin	caught (2)
the ride is asked about the wrong moment	caught (2)
`patternFor` stops checking crossability	caught (1)
`bayAt` ignores the margin	caught (1)
`scoreFor` pays for part seconds	caught (1)
`crossable` wrapped, behaviour unchanged	passes, as it should

A hop is instant

The frog's row and column change on the press. The little arc between the two squares is decoration played out afterwards, and HOP_LOCK is the same eighth of a second the search steps by.

That is not a shortcut, it is a requirement. The search assumes hops are instant, so a hop that took real time to land would make its proof a proof about a different game.

Playing it

Arrows or WASD on a keyboard. On a touch screen, a d-pad — the same three-by-three layout as Stow's, so anyone who has met that game already knows where the buttons are. Tapping the field also hops towards the tap, which is the one that reads as obvious on a phone held one-handed. Escape or P pauses; R starts over.

Landing on the wall between two bays kills you, and so does a bay that is already taken. Both are the original's rules and both are why the top row is not a formality.

Still to do

[ ] turtles that submerge. They stay a closed form in t, so the search can keep up with them, but only if a full dive cannot fit inside one of its steps — which is a constraint worth writing down before the feature rather than after it.