Repository navigation
feat(hexmap): bit-sliced hex cave generator (L4) - #127
Merged
Merged
Conversation
Caver::generate runs a synchronous B4/S2 cellular automaton on the whole board at once: 6 neighbour planes as field shifts, a carry-save count with the bitwise builtin called directly (AND, XOR and OR in one application), and a u128 single-limb path for boards of at most 128 bits. Caver::keep_component keeps the floor connected to a position. 17x14: 35.7k gas per generation, generate(17, 14, 3) 146.7k. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Lot L4 of
origami_hexmap: the hex cave generator.Caver::generate(width, height, order, seed): ~50 % random fill of the interior (one Poseidon permutation), thenordersynchronous generations of a 6-neighbour automaton, rule B4/S2, computed on the whole bitmap at once.order == 0returns the initial fill.u128single-limb path for boards of at most 128 bits.Caver::keep_component(grid, width, height, from): flood fill byLayout::expand. It stays separate fromgeneratebecause it costs about 2xgenerate(17, 14, 3).Gas (sierra gas, snforge)
generate(17, 14, 3, seed)keep_componenton a 17x14 caveorigami_mapCaver::generate(18, 14, 2)(for the record)All the required variants are measured in
bench_caver.cairoand listed inGAS.md(L4 section). They cover rules B4/S2, B4/S3 and B3/S3, fills of 25/50/75 %, the design's AND-only adder network (+46 %), corelibu256operators (+30 %), planes from shared sub-terms (+11 %), design parity-split planes (+1 %), and the u256 path against the u128 path on 7x7 (-60 %). Every variant is checked against a scalar reference automaton.Note for review
caver.cairodeclaresextern fn bitwise(u128, u128) -> (u128, u128, u128). This is the same libfunc that the corelib keeps private. If it gets promoted tohelpers/bits.cairo, other lots can use it too.🤖 Generated with Claude Code