bedrock_filer.c
/*
* bedrock_finder.c — locate a Minecraft chunk from a bedrock pattern.
*
* Uses the seed-independent bedrock generation algorithm of pre-1.18 Java
* Edition (Overworld Y=4 / Nether floor / Nether roof top layer): the
* 1-in-5 bedrock distribution depends only on chunk (x, z) — not on the
* world seed — so a sufficiently distinctive pattern uniquely identifies
* a chunk.
*
* Algorithm adapted from ChromeCrusher / DaPorkchop_'s bedrock.c.
*
* --- HOW TO FILL IN THE PATTERN ---
* Edit the PATTERN[] array below. Each row is a C string of equal length.
* Characters:
* 'X' = bedrock present at that block
* '_' = no bedrock (any other block)
* '?' = unknown (wildcard — will match either)
* Width and height are inferred automatically. Max width/height = 16
* (one chunk). Smaller patterns work too but produce more false positives;
* ~8x8 of certain cells is usually enough to be unique.
*
* Orientation: rows go top-to-bottom = North-to-South in-game,
* cols go left-to-right = West-to-East.
* If you don't know which direction is north, the search tries all
* 4 rotations and their reflections (8 variants total).
*
* --- COMPILE & RUN ---
* gcc -O3 -o bedrock_finder bedrock_finder.c
* ./bedrock_finder # default search radius (10000 chunks)
* ./bedrock_finder 50000 # custom radius in chunks
* ./bedrock_finder 50000 2 # custom radius + allow N mismatches
*/
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* ============================================================== */
/* ===================== EDIT YOUR PATTERN HERE ================= */
/* ============================================================== */
static const char *PATTERN[] = {
"??_X_?X_",
"__X___X_",
"________",
"X_______",
"_X_X____",
"_______X",
"_X_X_X__",
"X_X_____",
"X_____X_",
"X_______",
"__X_____",
"_X______",
"________",
};
/* ============================================================== */
#define WILDCARD 2
#define BEDROCK 1
#define EMPTY 0
#define MAX_DIM 16
/* dihedral group: 4 rotations x 2 reflections */
#define NUM_VARIANTS 8
static int variants[NUM_VARIANTS][MAX_DIM * MAX_DIM];
static int var_rows[NUM_VARIANTS], var_cols[NUM_VARIANTS];
static int pat_rows, pat_cols;
static int base_pattern[MAX_DIM * MAX_DIM];
/* ---- pattern transforms ---- */
static void rotate90(const int *in, int in_r, int in_c,
int *out, int *out_r, int *out_c) {
*out_r = in_c;
*out_c = in_r;
for (int i = 0; i < in_r; i++)
for (int j = 0; j < in_c; j++)
out[j * in_r + (in_r - 1 - i)] = in[i * in_c + j];
}
static void flip_h(const int *in, int rows, int cols, int *out) {
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
out[i * cols + (cols - 1 - j)] = in[i * cols + j];
}
/* ---- parse PATTERN[] into base_pattern[] ---- */
static int load_pattern(void) {
pat_rows = sizeof(PATTERN) / sizeof(PATTERN[0]);
if (pat_rows == 0 || pat_rows > MAX_DIM) {
fprintf(stderr, "Pattern row count %d out of range [1, %d]\n", pat_rows, MAX_DIM);
return -1;
}
pat_cols = (int) strlen(PATTERN[0]);
if (pat_cols == 0 || pat_cols > MAX_DIM) {
fprintf(stderr, "Pattern col count %d out of range [1, %d]\n", pat_cols, MAX_DIM);
return -1;
}
for (int i = 0; i < pat_rows; i++) {
if ((int) strlen(PATTERN[i]) != pat_cols) {
fprintf(stderr, "Row %d width mismatch (got %zu, expected %d)\n",
i, strlen(PATTERN[i]), pat_cols);
return -1;
}
for (int j = 0; j < pat_cols; j++) {
char c = PATTERN[i][j];
int v;
if (c == 'X' || c == 'x') v = BEDROCK;
else if (c == '_' || c == '.') v = EMPTY;
else if (c == '?') v = WILDCARD;
else {
fprintf(stderr, "Bad char '%c' at (%d,%d)\n", c, i, j);
return -1;
}
base_pattern[i * pat_cols + j] = v;
}
}
return 0;
}
static void build_variants(void) {
/* variants 0..3 = rotations of original */
memcpy(variants[0], base_pattern, sizeof(int) * pat_rows * pat_cols);
var_rows[0] = pat_rows;
var_cols[0] = pat_cols;
for (int r = 1; r < 4; r++) {
rotate90(variants[r - 1], var_rows[r - 1], var_cols[r - 1],
variants[r], &var_rows[r], &var_cols[r]);
}
/* variants 4..7 = rotations of horizontally flipped original */
int flipped[MAX_DIM * MAX_DIM];
flip_h(base_pattern, pat_rows, pat_cols, flipped);
memcpy(variants[4], flipped, sizeof(int) * pat_rows * pat_cols);
var_rows[4] = pat_rows;
var_cols[4] = pat_cols;
for (int r = 5; r < 8; r++) {
rotate90(variants[r - 1], var_rows[r - 1], var_cols[r - 1],
variants[r], &var_rows[r], &var_cols[r]);
}
/* deduplicate identical variants (e.g. symmetric patterns) */
for (int i = 0; i < NUM_VARIANTS; i++) {
for (int j = 0; j < i; j++) {
if (var_rows[i] == var_rows[j] && var_cols[i] == var_cols[j] &&
memcmp(variants[i], variants[j], sizeof(int) * var_rows[i] * var_cols[i]) == 0) {
var_rows[i] = 0; /* mark as duplicate */
break;
}
}
}
}
/* ---- generate top-layer bedrock pattern for one chunk ---- */
static int chunk_buf[16 * 16];
static void gen_chunk(int64_t x, int64_t z) {
int64_t seed = (x * 341873128712LL + z * 132897987541LL) ^ 0x5DEECE66DLL;
for (int a = 0; a < 16; a++) {
for (int b = 0; b < 16; b++) {
seed = seed * 709490313259657689LL + 1748772144486964054LL;
seed = seed & ((1LL << 48) - 1);
chunk_buf[a * 16 + b] = (4 <= ((seed >> 17) % 5)) ? 1 : 0;
seed = seed * 5985058416696778513LL + -8542997297661424380LL;
}
}
}
/* ---- try one variant at one (oy, ox) offset within current chunk ---- */
static int try_offset(const int *pat, int rows, int cols,
int oy, int ox, int max_mismatch) {
int mism = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int pv = pat[i * cols + j];
if (pv == WILDCARD) continue;
if (pv != chunk_buf[(oy + i) * 16 + (ox + j)]) {
if (++mism > max_mismatch) return -1;
}
}
}
return mism;
}
int main(int argc, char **argv) {
int radius = (argc > 1) ? atoi(argv[1]) : 10000;
int max_mismatch = (argc > 2) ? atoi(argv[2]) : 0;
if (load_pattern() != 0) return 1;
build_variants();
fprintf(stderr, "Pattern: %d rows x %d cols\n", pat_rows, pat_cols);
fprintf(stderr, "Search: chunk x,z in [-%d, %d]\n", radius, radius);
fprintf(stderr, "Allowed mismatches per match: %d\n\n", max_mismatch);
clock_t t0 = clock();
long total_found = 0;
for (int64_t cz = -radius; cz <= radius; cz++) {
for (int64_t cx = -radius; cx <= radius; cx++) {
gen_chunk(cx, cz);
for (int v = 0; v < NUM_VARIANTS; v++) {
int prows = var_rows[v], pcols = var_cols[v];
if (prows == 0) continue; /* deduped */
for (int oy = 0; oy <= 16 - prows; oy++) {
for (int ox = 0; ox <= 16 - pcols; ox++) {
int m = try_offset(variants[v], prows, pcols, oy, ox, max_mismatch);
if (m >= 0) {
int64_t bx = cx * 16 + ox;
int64_t bz = cz * 16 + oy;
printf("MATCH chunk=(%lld, %lld) variant=%d "
"offset=(row=%d, col=%d) block_nw=(%lld, %lld) mismatches=%d\n",
(long long) cx, (long long) cz, v, oy, ox,
(long long) bx, (long long) bz, m);
fflush(stdout);
total_found++;
}
}
}
}
}
if ((cz & 0xff) == 0) {
double dt = (double) (clock() - t0) / CLOCKS_PER_SEC;
fprintf(stderr, " z=%lld found=%ld t=%.1fs\n",
(long long) cz, total_found, dt);
}
}
double dt = (double) (clock() - t0) / CLOCKS_PER_SEC;
fprintf(stderr, "\nDone. Total matches: %ld (%.1fs)\n", total_found, dt);
return total_found > 0 ? 0 : 2;
}