地图种子逆向工程技巧:分区暴力搜索

前人成就回顾:

2^64的搜索空间对一般民用计算设备太大了。
由于村庄坐标只与世界种子的前48位相关,我们可以搜索2^48的范围使搜索时间落入合理区间.
村庄坐标计算规则:以下代码源自\net\minecraft\world\gen\structure\MapGenVillage.java

protected boolean canSpawnStructureAtCoords(int chunkX, int chunkZ)
    {
        int i = chunkX;
        int j = chunkZ;

        if (chunkX < 0)
        {
            chunkX -= this.distance - 1;                                                 //this.distance在主世界(Overworld)而且不是超平坦的情况下是32
        }

        if (chunkZ < 0)
        {
            chunkZ -= this.distance - 1;
        }

        int k = chunkX / this.distance;
        int l = chunkZ / this.distance;
        Random random = this.world.setRandomSeed(k, l, 10387312);//LINE_1
        k = k * this.distance;
        l = l * this.distance;
        k = k + random.nextInt(this.distance - 8);
        l = l + random.nextInt(this.distance - 8);

        if (i == k && j == l)
        {
            boolean flag = this.world.getBiomeProvider().areBiomesViable(i * 16 + 8, j * 16 + 8, 0, VILLAGE_SPAWN_BIOMES);//LINE_2

            if (flag)
            {
                return true;
            }
        }

        return false;
    }

如果我们可以进一步缩小搜索空间,那么计算种子的速度将会很乐观.

进入正题

一、区块生成算法的研究

通过研究村庄生成的代码,我们可以发现,如果把地图分为32区块*32区块的片段,每个片段之内执行村庄生成检查时计算得到的k和l都相等.这一对k和l就表示该片段内的一个区块,这个区块就是@Vinogradov 所说的拟村庄区块.

而取得随机数的范围是[0,24),因此所有拟村庄区块都在24区块*24区块的黄框内.

二、随机数生成器的研究

我们研究java.util.Ramdom类,发现以下代码:

    protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;          //mask=0xFFFFFFFFFFFFL
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
...
...
...
public int nextInt(int bound) {
    if (bound <= 0)
        throw new IllegalArgumentException(BadBound);

    int r = next(31);
    int m = bound - 1;
    if ((bound & m) == 0)  // i.e., bound is a power of 2
        r = (int)((bound * (long)r) >> 31);
    else {
        for (int u = r;
             u - (r = u % bound) + m < 0;                                 //实际只会执行一次
             u = next(31))
            ;
    }
    return r;
}

分析上述代码可知,生成一个新的随机数时,Java会把当前种子乘以一个常数multiplier,再加上一个常数addend,得到的结果取低48位.这样得到一个新的种子.取这个新种子较高的31bit,然后返回这个数据除以bound得到的余数.由于当两个数相乘时,较高位的乘数不会影响较低位的积,只要我们知道种子的低48位,我们就可以确定得出的随机数.反之,只要我们遍历2^48范围,我们就能通过随机数计算种子的低48位.
但是遍历48位太长了,能不能再给力点?

如果能让新的的随机数只依赖于这31bit当中的较低几个bit,那么我们就能只考虑这较低的几个bit+后面的17个bit.我们已知生成的随机数是新种子较高的31bit除以bound(值为24)的余数,而我们想要的是31bit中较低的几个bit,也就是31bit数除以2的整数次幂所得的余数.那么已知一个数除以24得到的余数,能够计算这个数除以多少得到的余数呢?答案就是24的因数: 2,3,4,6,8,12.因此,我们计算生成的随机数除以8的余数,并根据它遍历2^(3+17)的范围.

太长不看版:一个简单的示例可以用来说明,使用Random.nextInt(24)获取随机数时,取得的随机数仅与随机数种子的低20位相关.

import java.util.Random;

public class Test {
    public static void main(String[] args){
        int fullseed = 0x11de784a;
        int shortseed = 0xe784a;
        Random rand = new Random(fullseed);
        Random rand2 = new Random(shortseed);
        for(int i=0;i<10;i++){
            System.out.println("rand: "+String.valueOf(rand.nextInt(24)%8));
            System.out.println("rand2: "+String.valueOf(rand2.nextInt(24)%8));
        }
    }
}

以上代码的输出为:

rand: 4
rand2: 4
rand: 7
rand2: 7
rand: 2
rand2: 2
rand: 2
rand2: 2
rand: 4
rand2: 4
rand: 7
rand2: 7
rand: 0
rand2: 0
rand: 7
rand2: 7
rand: 2
rand2: 2
rand: 4
rand2: 4
预防和修复:这个方法的预防仍然需要修改村庄生成的源码或随机数生成器,比如把random.nextInt(this.distance - 8)改成random.nextInt(this.distance - 7)就不能用了
收藏 (0) 打赏

感谢您的支持,我会继续努力的!

打开微信/支付宝扫一扫,即可进行扫码打赏哦,分享从这里开始,精彩与您同在
点赞 (0)

MC百科 Minecraft 地图种子逆向工程技巧:分区暴力搜索 https://www.mcbke.com/3947.html

科技迷、外设控、Minecraft爱好者,科技改变生活!

常见问题

相关文章

评论
暂无评论
地图种子逆向工程技巧:分区暴力搜索-海报

分享本文封面