Minecraft(我的世界)中文论坛

 找回密码
 注册(register)
查看: 1875|回复: 23

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

[复制链接]
发表于 2018-8-24 16:13:28 | 显示全部楼层 |阅读模式

您尚未登录,立即登录享受更好的浏览体验!

您需要 登录 才可以下载或查看,没有帐号?注册(register)

x
本帖最后由 microwaver 于 2018-8-24 16:16 编辑

前置研究:地图种子的逆向研究(2)——结构与群系分布
感谢@Vinogradov 提供的思路

由于本文内容疑似涉及作弊,在此我不会给出与实际计算地图种子相关的代码,仅解释技术原理

前人成就回顾:
  • 2^64的搜索空间对一般民用计算设备太大了。
  • 由于村庄坐标只与世界种子的前48位相关,我们可以搜索2^48的范围使搜索时间落入合理区间.
  • 村庄坐标计算规则:以下代码源自\net\minecraft\world\gen\structure\MapGenVillage.java
  1. protected boolean canSpawnStructureAtCoords(int chunkX, int chunkZ)
  2.     {
  3.         int i = chunkX;
  4.         int j = chunkZ;

  5.         if (chunkX < 0)
  6.         {
  7.             chunkX -= this.distance - 1;                                                 <font color="#ff0000">//this.distance在主世界(Overworld)而且不是超平坦的情况下是32</font>
  8.         }

  9.         if (chunkZ < 0)
  10.         {
  11.             chunkZ -= this.distance - 1;
  12.         }

  13.         int k = chunkX / this.distance;
  14.         int l = chunkZ / this.distance;
  15.         Random random = this.world.setRandomSeed(k, l, 10387312);//LINE_1
  16.         k = k * this.distance;
  17.         l = l * this.distance;
  18.         k = k + random.nextInt(this.distance - 8);
  19.         l = l + random.nextInt(this.distance - 8);

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

  23.             if (flag)
  24.             {
  25.                 return true;
  26.             }
  27.         }

  28.         return false;
  29.     }
复制代码



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

进入正题

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

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


二、随机数生成器的研究

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

  1.     protected int next(int bits) {
  2. long oldseed, nextseed;
  3. AtomicLong seed = this.seed;
  4. do {
  5. oldseed = seed.get();
  6. nextseed = (oldseed * multiplier + addend) & mask;          <font color="#ff0000">//mask=0xFFFFFFFFFFFFL</font>
  7. } while (!seed.compareAndSet(oldseed, nextseed));
  8. return (int)(nextseed >>> (48 - bits));
  9. }
  10. ...
  11. ...
  12. ...
  13. public int nextInt(int bound) {
  14.     if (bound <= 0)
  15.         throw new IllegalArgumentException(BadBound);

  16.     int r = next(31);
  17.     int m = bound - 1;
  18.     if ((bound & m) == 0)  // i.e., bound is a power of 2
  19.         r = (int)((bound * (long)r) >> 31);
  20.     else {
  21.         for (int u = r;
  22.              u - (r = u % bound) + m < 0;                                 <font color="#ff0000">//实际只会执行一次</font>
  23.              u = next(31))
  24.             ;
  25.     }
  26.     return r;
  27. }
复制代码

    分析上述代码可知,生成一个新的随机数时,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位相关.
  1. import java.util.Random;

  2. public class Test {
  3.     public static void main(String[] args){
  4.         int fullseed = 0x11de784a;
  5.         int shortseed = 0xe784a;
  6.         Random rand = new Random(fullseed);
  7.         Random rand2 = new Random(shortseed);
  8.         for(int i=0;i<10;i++){
  9.             System.out.println("rand: "+String.valueOf(rand.nextInt(24)%8));
  10.             System.out.println("rand2: "+String.valueOf(rand2.nextInt(24)%8));
  11.         }
  12.     }
  13. }
复制代码

以上代码的输出为:
  1. rand: 4
  2. rand2: 4
  3. rand: 7
  4. rand2: 7
  5. rand: 2
  6. rand2: 2
  7. rand: 2
  8. rand2: 2
  9. rand: 4
  10. rand2: 4
  11. rand: 7
  12. rand2: 7
  13. rand: 0
  14. rand2: 0
  15. rand: 7
  16. rand2: 7
  17. rand: 2
  18. rand2: 2
  19. rand: 4
  20. rand2: 4
复制代码

结论:通过利用java.util.Random类的缺陷,我们可以将首次搜索的范围降低到低20位,这几乎相当于立即完成了.通过使用@Vinogradov 提出的方法进行第二次搜索,我们可以很快地获取地图种子.

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

其实我原来只想做一个实现来着的...然后不会写GPU计算就开始找简易算法233

评分

参与人数 13人气 +28 金粒 +210 贡献 +5 收起 理由
cang_33 + 1 + 15 神乎其技,不服不行!
45gfg9 + 2 神乎其技,不服不行!
Zevn + 2 + 30 MCBBS有你更精彩~
langyo_v3 + 2 MCBBS有你更精彩~
ROF + 2 MCBBS有你更精彩~
bm2.5 + 10 dalao
bo_bo2001 + 2 NB
SPGoding + 2 + 10 MCBBS有你更精彩~
ItIsEnderman + 2 diao
乙烯_中国 + 5 + 60 + 5 精华
gooding300 + 3 + 25 MCBBS有你更精彩~
玄素 + 4 + 40 MCBBS有你更精彩~
Vinogradov + 1 + 20 非常棒!

查看全部评分

回复

使用道具 举报

发表于 2018-8-24 17:15:32 | 显示全部楼层
这操作太真实了
神乎其技,不服不行。
回复

使用道具 举报

发表于 2018-8-24 21:08:24 | 显示全部楼层
本帖最后由 Vinogradov 于 2018-8-24 21:30 编辑

这个思路太棒了!我完全没想到用2的幂次继续简化的事情。
以下是我的理解,如果有错请不吝赐教:
我想你得到的结论是,把每个拟村庄区块对应的k和l模8以后,得到的结果只和种子的低20位有关对吧?
这样确实变得快很多,但是你获得的信息也从48位减少到了20位。
或许可以用你的方法过滤一遍获得低20位以后,再用我原来的那个粗的办法再穷举低第21位-低第48位,这样还是能获得低48位。(或许你就是这个意思我没理解?)。这种组合的办法比我帖子里那个要好很多了。

至于高16位就很简单,不提了。
回复

使用道具 举报

发表于 2018-8-29 18:39:12 | 显示全部楼层
毫无疑问,精华。
回复

使用道具 举报

发表于 2018-8-29 22:52:32 | 显示全部楼层
哇楼主真厉害啊

评分

参与人数 1人气 -1 金粒 -10 收起 理由
Zero_Exact -1 -10 无意义

查看全部评分

回复

使用道具 举报

发表于 2018-8-30 09:12:39 | 显示全部楼层
就只有我每个字都认识 拼到一起就听不懂了吗

评分

参与人数 1人气 +1 收起 理由
殇凌·残胤 + 1 你不是一个人!

查看全部评分

回复

使用道具 举报

发表于 2018-8-30 13:12:24 | 显示全部楼层
楼主好厉害啊,根本学不会

评分

参与人数 1人气 -1 金粒 -10 收起 理由
Zero_Exact -1 -10 无意义

查看全部评分

回复

使用道具 举报

发表于 2018-8-30 14:27:11 | 显示全部楼层
神乎其技,不服不行!

评分

参与人数 1人气 -1 金粒 -10 收起 理由
玄素 -1 -10 无意义

查看全部评分

回复

使用道具 举报

发表于 2018-8-31 09:31:33 | 显示全部楼层
哇!楼主真NB

评分

参与人数 1人气 -1 金粒 -10 收起 理由
Zero_Exact -1 -10 无意义

查看全部评分

回复

使用道具 举报

发表于 2018-8-31 14:47:41 | 显示全部楼层
哇,挺厉害的
回复

使用道具 举报

发表于 2018-8-31 15:05:09 | 显示全部楼层
我要顶帖..............

评分

参与人数 1人气 -1 金粒 -10 收起 理由
玄素 -1 -10 无意义

查看全部评分

回复

使用道具 举报

发表于 2018-8-31 18:45:10 | 显示全部楼层
所以我们需要一个修改世界产卵器的插件
回复

使用道具 举报

发表于 2018-9-1 00:03:14 | 显示全部楼层
不会写GPU计算……

同求GPU的操作接口文档
回复

使用道具 举报

发表于 2018-9-1 14:29:52 | 显示全部楼层
厉害啦
回复

使用道具 举报

发表于 2018-9-3 06:06:46 | 显示全部楼层
给楼主大大的赞,很棒
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册(register)

本版积分规则

Archiver|小黑屋|Mcbbs.net ( 京ICP备15023768号-1 ) | 手机版本

GMT+8, 2018-9-21 00:19 , Processed in 0.084531 second(s), 10 queries , Memcache On.

"Minecraft"以及"我的世界"为Mojang Synergies AB的商标。本站与Mojang以及微软公司没有从属关系。

© 2010-2017 我的世界中文论坛 版权所有。本站原创图文内容版权属于原创作者,未经许可不得转载。

快速回复 返回顶部 返回列表