The wall between two positions

The rule

For a move from v1 to v2 on one axis, the height is the bit length of v1 XOR v2 (section 4.4). The move is covered by one aligned region of that height: it starts at (v1 >> h) << h and holds 2^h positions (section 4.5). The two positions sit in different halves of that region, and the seam between the halves is the wall (section 6.3). A hop proves the move by computing the Cantor root of the whole region, all 2^h leaves.

Worked moves

From 4 to 5: 100 XOR 101 = 001, bit length 1, so h = 1. The region is [4, 5], two leaves, and the wall between them is the shortest there is.

From 7 to 8: 0111 XOR 1000 = 1111, bit length 4, so h = 4. The move is also one Gibson, but the region is [0 .. 15], sixteen leaves, because 8 is the start of a block of eight and 7 is the end of the block before it. The wall between them is height 4.

From 0 to 5 is height 3 over [0 .. 7]; from 4 to 7 is height 2 over [4 .. 7]. The scene's buttons load each of these.

The skyline

The wall between p - 1 and p is one more than the number of trailing zero bits of p. Every other wall is height 1 and the rest are at least 2; every fourth is at least 3, every eighth at least 4, and a wall of height k or more comes once every 2^k-1 positions. So the axis is mostly low fences, with taller walls at every power-of-two boundary, and the tallest wall of all at the axis midpoint. Where you stand decides which walls are near you: position 8 has a height-4 wall at its left side and a height-1 wall at its right.

There is no way around

A long move cannot be made cheap by cutting it into short ones. Walking from v1 to v2 one Gibson at a time, the tallest wall met on the way is always exactly the height of the direct move, because every path between them crosses the highest bit where they differ (section 4.8). The scene computes both numbers for every move you set, and the test suite checks all 4,096 moves in a 64-position window.

At full scale

The ruler here has 32 positions; a real axis has 2⁸⁵. The rule does not change. Stepping from 2³³ - 1 to 2³³ is height 34; stepping from 2³⁴ - 1 to 2³⁴ is height 35. A Cantor root over 85-bit leaves is exactly 85 × 2^h bits, so the root behind that first step is 182.5 GB and the second is 365.1 GB per axis, and the values below the root must be held while it is built (section 6.1). One Gibson, the width of a hydrogen atom on Earth's scale, can be the most expensive step in a region.

Why walls are the point

The protocol wants distance to cost something, and walls are where the cost lives. They are not placed by anyone: they fall out of binary alignment, which is also what lets two strangers agree on the same region without talking (section 4.5). Above a certain height the Cantor root is too large to hold, and the wall cannot be hopped at all. The sidestep is the way across those, and the next scene puts the two proofs side by side.