Ocean Monument Cluster Finder

ある Minecraft (Java 1.18+) ワールドのシードに対し、 半径 128 マス以内・かつ半径 24 マス以外 の球殻 (hollow shell) 内に占める 海底神殿の体積が最大になる座標 (cx, cy, cz) を求めるツールです。

アルゴリズム

1. Phase 1a — 候補列挙 (fast scan): 探索範囲内のすべてのリージョン (32 chunk = 512 block) について、 getLargeStructurePos で海底神殿候補チャンクを決定論的に算出し、cubiomes の高速近似モード (4 隅のみのバイオーム検査) でバイオーム判定を行う。
2. Phase 1b — 厳密検証 (オプション, --exact): 全候補について cubiomes の完全な 29 ブロック半径バイオーム検査を行い、false-positive を排除する。
3. Phase 2 — 球殻 prefix sum: 257³ の球殻 (24 ≤ r ≤ 128) prefix-sum 配列を構築。 任意の 3D 軸並行 BB と球殻の交差体積を O(1) で取得できる。
4. Phase 3 — クラスタリング: 互いに距離 346 ブロック以内の神殿群を union-find で 連結成分にまとめる。
5. Phase 4 — クラスタ探索: 各クラスタについて、構成神殿の BB 和集合と球殻の交差体積を 最大化する (cx, cy, cz) を粗→密の 2 段探索で求める。包含-排除原理で union を計算。
6. Phase 5 — トップ結果の厳密検証: Phase 1a の近似 false-positive を弾くため、 上位 N 件の寄与神殿だけを cubiomes の厳密検査で再検証し、必要なら再探索。

cubiomes (https://github.com/Cubitect/cubiomes) を C FFI 経由で利用しており、 バイオーム生成と構造体配置の精度は cubiomes 準拠です。

ビルド

cargo build --release

要件: Rust 1.70+, MSVC ビルドツール (Windows) または gcc/clang。 cubiomes 本体は cubiomes/ にサブモジュール的に置かれており、build.rs が自動でビルドします。

使い方

target\release\monument_finder.exe <seed> [options]

よく使うオプション

オプション	デフォルト	説明
--range <blocks>	30000000	探索半径 (ブロック)
--top <n>	20	上位 N 件を出力
--threads <n>	(auto)	ワーカースレッド数
--mc <v>	25 (1.20)	cubiomes MCVersion 列挙値 (22=1.18, 24=1.19, 25=1.20)
--exact	OFF	Phase 1b 厳密検証を全候補で実行 (非常に時間がかかる)
--verify-top <n>	200	Phase 5 で上位 N 件を厳密検証する
--with-isolated	OFF	サイズ 1 クラスタ (単体神殿) も探索対象に含める
--wb	OFF	ワールド境界 (|x|<37.5M, |z|<37.5M) を除外

例

# 推奨デフォルト: ±30M ブロック範囲、上位 20 件
target\release\monument_finder.exe 1234

# 動作確認用に小範囲・トップ 5
target\release\monument_finder.exe 1234 --range 1000000 --top 5

# 厳密モード (Phase 1b ON、数倍遅い)
target\release\monument_finder.exe 1234 --range 1000000 --exact

出力例

--- Top 20 highest 3D hollow sphere coverage (inner_r=24, outer_r=128) ---

#1  center=(-758024, 40, -120368)  volume=154744  density=1.7736%  monuments=2
    monument origin=(-758000, 39, -120464)  bb=[...]  dist=86.0
    monument origin=(-758048, 39, -120304)  bb=[...]  dist=93.7
...

• center = 球殻中心 (cx, cy, cz)
• volume = 球殻と神殿 BB 群の交差体積 (lattice point 数)
• density = volume / shell_volume
• monuments = 寄与する神殿の数
• dist = 各神殿中心と球殻中心の距離

精度に関する注意

• 海底神殿の BB は固定サイズ 58×23×58 (Java 1.18+) で扱っており、内部の各 piece までは 展開していません (実体積 ~75% に対し BB は 100%)。クラスタ間の相対比較では問題ありません。
• デフォルト (fast) モードでは Phase 1a に約 0.13% の false-positive 率がありますが、 Phase 5 で top-N の寄与神殿は厳密検証されるため、出力結果の精度は 100% です。

ライセンス

cubiomes は MIT ライセンス。本ツール本体も同じく MIT で配布します。