Minecraftの村がどういう座標に出現するのかを調査した。
- 村 - Minecraft Wiki https://minecraft-ja.gamepedia.com/%E6%9D%91
バァージョン
- Minecraft 1.12.2
- forgeSrc-1.12.2-14.23.4.2705
出典
クラス名はForge MCPの逆難読化済みのもの
-
net.minecraft.world.gen.ChunkGeneratorOverworld- 村生成を呼び出しているコンテキスト
-
net.minecraft.world.gen.structure.MapGenVillage- 村の生成クラス
解説
座標決定の中心となるのはMapGenVillage#canSpawnStructureAtCoords(int chunkX, int chunkZ)メソッド。これはチャンク座標X,Zを与えるとそこに構造物が出現できるか否かを返している。このメソッドの定義の時点でほぼ決定的なのは、村は1チャンクに最大で1個までしか生成されないということだ。
限りなくJavaに近い疑似コードで見てみる。
int distance = 32;
boolean canSpawnStructureAtCoords(int chunkX, int chunkZ)
{
// 生成先座標の確定 (1)
int x1 = chunkX;
int z1 = chunkZ;
// 地域の計算 (2)
int x3 = chunkX;
int z3 = chunkZ;
if (x3 < 0) x3 -= distance - 1;
if (z3 < 0) z3 -= distance - 1;
int regionX = x3 / distance;
int regionZ = z3 / distance;
Random random = getRandom(regionX, regionZ, 10387312);
// 想定座標の確定 (3)
int x2 = regionX * distance + random.nextInt(distance - 8);
int z2 = regionZ * distance + random.nextInt(distance - 8);
if (x1 == x2 && z1 == z2) {
if (村生成可能なバイオームである(x1 * 16 + 8, z1 * 16 + 8)) {
return true;
}
}
return false;
}
全体的な挙動を意訳するとこんな感じ。
-
distanceを決定する。これはデフォルトで32とし、ワールドの設定で変更されうる。 - 世界を1辺が
distanceチャンクの正方形の地域で区切る。 - 地域ごとに村が出現するチャンクを決定する。
- そのチャンクの中心座標が適切なバイオームであれば村が生成される。（本文書ではバイオームについては取り扱わない。）
もっと意訳すると次のようになる。
distance x distanceチャンク毎、地図の左上端から(distance - 8)x(distance - 8)チャンクのどこかに、特定のバイオームのとき、村が出現する。
それを「あるチャンクについて、そこに村があるか否か」という形で表現するとこのメソッドのようになる。
- まず(1)で生成先の座標を確保しておく。
- (2)で地域座標（xRegion,zRegion）を計算する。（その過程で負の座標の取り扱いで少し変数を使う。）
- (3)で地域座標から村が生成されるべき位置を計算する。
- 生成先と村が生成されるべき位置が同じだった場合、そこに村が出現できる。（ただしバイオームが正しい場合。）
getRandom
ここでgetRandom(int regionX, int regionY, int s)についての説明。
このメソッドは実際にはnet.minecraft.world.World#setRandomSeed(int, int, int)であり、ワールドに乱数生成器のシードを設定してその乱数生成器を返すものであるが、ここでは単に引数に従って乱数生成器を返すものとして考える。
long seed;
Random getRandom(int regionX, int regionY, int s)
{
return new Random((long) regionX * 341873128712L + (long) regionY * 132897987541L + seed + (long) s);
}
new Random(long)はシードを与えて乱数生成器を生成する構文である。3個の引数に対して値を乗算して和を取った物を乱数生成器のシードとしている。ここでseedは__そのワールドのシード値__である。村の生成座標はこの段階でシードのみに依存するものとなる。
チャンク内の位置
実はすべての村はチャンク内での生成位置が固定であり、(2,2)に井戸の端っこが来る。それはnet.minecraft.world.gen.structure.MapGenVillage.Start#new(World worldIn, Random rand, int x, int z, int size)に書いてある。canSpawnStructureAtCoordsを改造してすべてのチャンクで村を生成させるようにすると、ちゃんと井戸が規則正しく並ぶことが確認できる（めっちゃ重い）。
地域座標から生成チャンクへの変換
ここまでくると、ワールドの特定の地域の周辺に出現する村の座標というものが分かるようになる。それは次のようなコードである。
long seed;
int distance = 32;
Point getVillageCoord(int regionX, int regionZ)
{
Random random = new Random(regionX * 341873128712L + regionZ * 132897987541L + seed + 10387312L);
int chunkX = regionX * distance + random.nextInt(distance - 8);
int chunkZ = regionZ * distance + random.nextInt(distance - 8);
return new Point(chunkX * 16 + 2, chunkZ * 16 + 2);
}
ここでrandom.nextInt(distance - 8)という部分に注目してほしい。村は地域のどの位置にも生成可能なわけではなく、地域の+X方向と+Z方向の8チャンクには生成できないことになる。これは恐らく村が重ならないための措置であろう。村の生成座標からワールドのシード逆算を行う場合、デフォルトのdistanceならば村1個あたり24^2の絞り込み性能になることになる。シード値がintの範囲内ならばだいたい村4個分で特定可能である。
実際には村の配置だけからシードの候補を絞りこむのは結構難しい。たくさんの村を発見することは容易ではないし、複数のシードが何かの要因で同じ配置に収束することがあるっぽいからだ。
同一の村の生成
村の生成において、ワールドのシードはRandomの仕様により、実質二つの部分に分かれて解釈される。
- 上位16ビット 無視される
- 下位48ビット 村の生成に影響する
seed & 0xFFFFFFFFFFFFLしたものが同じであれば、バイオームがあっていれば同じ形状の村が出現する。すなわち、シードに2^48の倍数を加減算しても村の形状は変わらない。これを利用すると村の形状（構成する建物の種類と個数）からシードを65536パターンまで絞ることができる。ただし計算がそう簡単ではないことからGPGPUを使うことは難しく、計算にそこそこ時間がかかってしまう。村の配置からシードの候補をもとの655362^48個から655361000個くらいまで絞った後で65535*1に絞り込むのに使うのが良いだろう。村の形状によるシードの絞り込みはそこまで絞り込む能力があるようだ。