Help us understand the problem. What is going on with this article?

Minecraft 1.12.2 村の座標決定部分のアルゴリズム

More than 1 year has passed since last update.

Minecraftの村がどういう座標に出現するのかを調査した。

バァージョン

  • 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;
}

全体的な挙動を意訳するとこんな感じ。

  1. distanceを決定する。これはデフォルトで32とし、ワールドの設定で変更されうる。
  2. 世界を1辺がdistanceチャンクの正方形の地域で区切る。
  3. 地域ごとに村が出現するチャンクを決定する。
  4. そのチャンクの中心座標が適切なバイオームであれば村が生成される。(本文書ではバイオームについては取り扱わない。)

もっと意訳すると次のようになる。

distance x distanceチャンク毎、地図の左上端から(distance - 8)x(distance - 8)チャンクのどこかに、特定のバイオームのとき、村が出現する。

それを「あるチャンクについて、そこに村があるか否か」という形で表現するとこのメソッドのようになる。

  1. まず(1)で生成先の座標を確保しておく。
  2. (2)で地域座標(xRegion,zRegion)を計算する。(その過程で負の座標の取り扱いで少し変数を使う。)
  3. (3)で地域座標から村が生成されるべき位置を計算する。
  4. 生成先と村が生成されるべき位置が同じだった場合、そこに村が出現できる。(ただしバイオームが正しい場合。)

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を使うことは難しく、計算にそこそこ時間がかかってしまう。村の配置からシードの候補をもとの65536*2^48個から65536*1000個くらいまで絞った後で65535*1に絞り込むのに使うのが良いだろう。村の形状によるシードの絞り込みはそこまで絞り込む能力があるようだ。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした