feat(hexmap): random walk generator (L6) - #131

Summary

Implements Walker::generate(width, height, steps, seed) in origami_hexmap (lot L6): start on a seed-selected interior tile, then steps moves in a loop. Each move draws one of the 6 directions, moves if the target is interior (stays otherwise) and opens the tile. steps == 0 returns only the start tile.

Gas (17x14): 4.8k-5.3k per step, under the 6k target.

For reference, origami_map's walker test (18x14, 500 steps) reports 29.9M.

Design (details in GAS.md, section L6)

• Random source: one pool division by 216 per three moves, with the digits read from a 216-arm table that is called, not inlined. The pool is refilled by a counter every 12 draws, so there is no per-draw pool < 2^32 test.
• Move: doubled column c = 2x + (y & 1), row, and one-hot position 2^i, all felts. Bound tests are felt equalities with no parity branch. The state carries the NorthEast factor for both row parities and swaps them on vertical moves, so a move is one field product.
• Grid: the positions of three moves are summed. Only the first and third positions can coincide, so one equality check is enough. The sum is ORed into a u256 once, and converted to a felt once at the end.
• Loop: 18 moves per iteration, plus a short tail loop.

The losing variants required by the brief are kept test-only in bench_walker.cairo, with their numbers in GAS.md:

• random source: next_below, 3-bit digits with rejection, pair table
• move: (x, y) with a parity bool, index plus mask test, one-hot plus AND
• grid accumulation: OR each step, test-then-add, low-limb OR
• loop shape: 3, 6, 12 and 36 moves per iteration, table inlined or not

Tests

• Exact grids on fixed seeds for 17x14, 7x7, 19x13 and 3x3.
• Equality with a scalar reference (neighbor plus bit test and set, on the same draws):
  • 11 sizes, from 3x3 to 83x3 and 3x83;
  • every step count from 0 to 79;
  • 20 seeds.
• Border ring closed, determinism, and panics on invalid dimensions.

🤖 Generated with Claude Code