GPBPF

really fast minecraft bedrock pattern finder

Comment

introduction

Minecraft's bedrock layer may seem random, but it has a clear pattern. Whether a block is bedrock depends solely on the world seed and the block's coordinates. This means that if you spot a patch of bedrock in a screenshot or video, you can compute its coordinates. On large anarchy servers where players hide bases, knowing these coordinates is valuable.

There was already a Java tool for this, based on an older bedrock generator I found on Reddit. It operated well, but it ran on a single thread and processed about 27.6 million columns per second. To cover a significant search area, you had to let it run for hours. The problem lies in the fact that each column operates independently. There's no shared state or communication, just constant repetition of around 20 random number generator draws on different inputs. This is exactly the type of problem a GPU can solve, yet no one had applied one to it.

What it does

GPBPF searches a rectangular area of a Minecraft world (1.18–1.21) for a bedrock pattern and prints every matching column. On an RTX 3070, it processes 400 billion columns in just 14 seconds in an ar donutSMP world. There’s also an OpenMP CPU build that performs better for searches under about 100 million columns because the overhead of CUDA’s context initialization becomes more than the search itself at that size.

It includes a web GUI because typing 25 command-line arguments for a 5×5 pattern can be tedious. You can draw the pattern on a grid, using one tab for each Y layer. Before you start, the page samples the real search to display a measured match count with an interval. This way, a pattern that would produce 12 GB of text informs you up front. If a pattern can never match, it lets you know as well.

It scans for patterns in different orientations and includes a bedrock viewer. This allows you to explore the generated bedrock and see the matches highlighted rather than relying on coordinates alone. Long searches provide progress updates, can be canceled, and can be halted with Ctrl, ensuring that the joined sections are byte-identical to the uninterrupted run.

How I built it

I used C for the host, CUDA for the kernel, maintaining a clear division in the project. The generator must match Minecraft; everything else is up to us. The hash, the xoroshiro128++ stream, and the per-layer probabilities belong to the game. The order of arguments and output quirks from the Java tool are not specifications, and once the port was successful, I stopped treating them as such.

This separation is enforced mechanically. I recorded 24 vectors that lock the generator by match count and SHA-256 digest, running these on every build. They only need the binary and Python 3, with no JDK or network connection required. The fp_proof checks all possible inputs for the float comparison, performing 386 million comparisons in about 0.3 seconds. The generator specifies that comparison method, and such precision deserves proof rather than mere claims.

The speed improvements came from four factors: moving a double-precision divide outside the main loop, resolving pattern blocks with fixed outcomes at load time, sorting the pattern for optimal access, and rewriting the output path to use LSD radix sort along with custom integer formatting. The GPU operates on adaptively sized tiles instead of one large batch. The web server relies solely on the Python 3 standard library and calls the same binary, ensuring that the GUI cannot interfere with the generator.

Challenges I ran into

A double-precision divide performed 6.6 billion times to produce one of four values. The probability for each layer depends solely on a block's Y, with no influence from X or Z. However, the interpolation that calculated this relied on an FP64 divide. As there’s no hardware FP64 divider, nvcc creates a sequence based on reciprocal plus Newton-Raphson. Consumer Ampere GPUs process FP64 at a 1:64 rate, which led to FP64 operations taking up 67% of kernel time. By moving it to the host, I achieved bit-exact results with no FP64 instructions. Kernel time dropped from 622.8 ms to 51.4 ms.

I encountered a bug that passed through the entire testing process. The nextFloat() returns multiples of 2⁻²⁴, and two of the four probabilities—0.8 and 0.6—are exact multiples of 2⁻²⁴ as well. This means a draw can land precisely on a probability threshold. Seed 12345 caused this at one column within the test range. Before I identified and fixed it, manipulating that operator passed all my tests.

Estimates turned out to be off by a factor of 47. The GUI’s instant match-count estimate multiplies the per-layer probabilities, assuming each block's draw is independent. This holds true within one Y layer but greatly differs across layers. Two probes at the same column but at different Y layers share a driver, and their hashes differ only in a few low bits, leading to bedrock stacking vertically more often than random chance would suggest. The discrepancies always inflate match counts, contrary to the purpose of warning users about output size. The solution was to stop modeling and start measuring: I sampled the actual search. I discovered that the match rate wasn’t spatially uniform either. The spread across tiles was 7.8 times what Poisson noise predicts, closely related to how hash multiplies z by a constant while x wraps in 32 bits. Therefore, the sample slice had to cover every Z, and the reported interval needed a spatial term.

Silent truncation became an issue at scale. A single kernel launch hits three limits: the display driver can kill a kernel that runs too long, the match buffer is fixed for each launch, and the match counter is a 32-bit integer. The previous code reported 16,777,216 matches—indicating the buffer was full—and suggested searching a smaller area. Using tiling fixed the issue, yielding 24,001,022 matches that matched the CPU path exactly. However, the tile ceiling isn’t adjustable: a wider tile than UINT_MAX makes an overflowing launch appear small. This is the exact failure that the buffer check is designed to catch.

I also needed a resume feature that truly worked. OpenMP's dynamic scheduling allows a fast thread to finish columns beyond the stopping point. Keeping these results accounted for produced 1,370 duplicate matches when the resume point was discarded before printing. Discarding completed work is the easier mistake.

Accomplishments that I'm proud of

The end-to-end performance: the Java version takes about four hours to perform the 400 billion column search at its rate. GPBPF completes the same task in just 14 seconds. That’s roughly a 1,000 times improvement. Both results align closely with theoretical expectations, within 0.17%.

More importantly, the validation process is a highlight, more so than the speed. My tests require no additional setup and catch the bugs that matter here. You can’t determine if an answer is wrong just by looking, so a generator that quietly drifts might produce coordinates that don't exist in any world.

I'm also pleased with the honesty in the numbers. The README specifies that CUDA processes columns. It states that the selectivity sort gives the CPU a 3.0 times improvement while the GPU only achieves 1.5 times. It explains why (a warp costs the maximum for its 32 threads, not the average, so early exit only pays off if the entire warp exits together) rather than mislabeling it as "GPU" in the title. It mentions two optimizations that seemed promising but didn’t yield measurable gains. The Nether roof results are marked as unverified because actual verification requires comparison against the game, not just the Java tool that agrees with my findings.

*What I learned *

The bottleneck often hides in unanticipated places. Once I realized the text generated—178 MB—cost more to process than the actual search that created it, everything shifted. When I looked closely at the kernel, the real efficiency gains came not from the expected integer hash optimizations (which only improved by 6%) but required changes in the loop structure itself.

Understanding GPU performance also needed a grasp of the execution model. The differences between per-column early exit and per-warp early exit are significant, and profiling alone won’t clarify this if you don’t know to watch for it.

When the input space is small enough to enumerate—2²⁴ floats taking about a third of a second—you should enumerate. Sampling could suggest the narrowing was acceptable, but thorough checking confirmed it wasn’t.

Finally, I learned that measuring always trumps modeling whenever the model falls short. The assumption of independence appeared reasonable but proved to be off by a factor of 47.

What's next for GPBPF

  • Streaming output. Matches are buffered in RAM before printing, so with about 8 bytes each, a billion matches would take up 8 GB. This, rather than the GPU, now represents the limiting factor on a very large scan.

  • Verifying the Nether roof. The roof band runs in an opposite direction to the floor and narrows as you go up. It’s not clear whether this matches the game or is a bug inherited from the original version. It needs confirmation from the actual game.

  • Fixing the last inherited issue. A missing pattern directory results in an empty pattern, which matches every column.

  • multi-gpu load distribution for hardcore sweaty anarchy base hunters

Built With

Share this project:

Updates