Minecraft(我的世界)中文论坛

 找回密码
 注册(register)
查看: 31482|回复: 554
打印 上一主题 下一主题

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

    [复制链接]
microwaver 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
753
钻石
性别
保密
注册时间
2017-2-5
查看详细资料
跳转到指定楼层
楼主
发表于 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 所说的拟村庄区块.

    而取得随机数的范围是[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

评分

参与人数 29人气 +48 金粒 +320 贡献 +6 收起 理由
719823597 + 4 + 50 + 1 Ssssssssssssssssssss
ZMY_666233 + 1 膜拜大佬
core.exe + 1 神乎其技,不服不行!
ColorsWind + 2 + 8 MCBBS有你更精彩~
黄河 + 1 神乎其技,不服不行!
苦末尸 + 1 MCBBS有你更精彩~
bian_feng + 1 神乎其技,不服不行!
会跑的房子 + 1 MCBBS有你更精彩~
jiangyoudi2022 + 1 神乎其技,不服不行!
lengzu + 2 + 22 神乎其技,不服不行!
2912584425hhh + 10 神乎其技,不服不行!
团子是只猪 + 1 MCBBS有你更精彩~
mmmmmmmm丶浅瞳 + 1 神乎其技,不服不行!
非常你我 + 1 + 10 向算法大佬致敬
迷之老叶 + 1 + 10 神乎其技,不服不行!
2845984686 + 1 神乎其技,不服不行!
cang_33 + 1 + 15 神乎其技,不服不行!
45gfg9 + 2 神乎其技,不服不行!
Zevn + 2 + 30 MCBBS有你更精彩~
langyo_v3 + 2 MCBBS有你更精彩~

查看全部评分

帖子永久链接: 

Minecraft中文论坛 - 论坛版权1、本主题所有言论和图片纯属会员个人意见,与本论坛立场无关
2、本站所有主题由该帖子作者发表,该帖子作者享有帖子相关版权
3、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者的同意
4、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任
5、本帖若有内容转载自其它媒体,不代表本站赞同其观点和对其真实性负责
6、若本帖涉及任何版权问题,请立即告知本站,本站将及时予以删除并致以最深的歉意
7、Minecraft(我的世界)中文论坛管理员和版主有权不事先通知发贴者而删除本文

NoName德里奇 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
6752
钻石
性别
保密
注册时间
2018-8-2
查看详细资料
沙发
发表于 2018-8-24 17:15:32 | 只看该作者
这操作太真实了
神乎其技,不服不行。
回复

使用道具 举报

丢人素学姐 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
1950
钻石
性别
保密
注册时间
2017-3-6
查看详细资料
板凳
发表于 2018-8-24 21:08:24 | 只看该作者
本帖最后由 Vinogradov 于 2018-8-24 21:30 编辑

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

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

使用道具 举报

乙烯_中国 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
22103
钻石
性别
保密
注册时间
2014-12-16
查看详细资料
地板
发表于 2018-8-29 18:39:12 | 只看该作者
毫无疑问,精华。
回复

使用道具 举报

anjiayi123 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
32
钻石
性别
保密
注册时间
2017-3-14
查看详细资料
5#
发表于 2018-8-29 22:52:32 | 只看该作者
哇楼主真厉害啊

评分

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

查看全部评分

回复

使用道具 举报

Robert_Liang 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
34
钻石
性别
保密
注册时间
2018-8-29
查看详细资料
6#
发表于 2018-8-30 09:12:39 | 只看该作者
就只有我每个字都认识 拼到一起就听不懂了吗

评分

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

查看全部评分

回复

使用道具 举报

夕颜初夏 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
663
钻石
性别
保密
注册时间
2018-8-21
查看详细资料
7#
发表于 2018-8-30 13:12:24 | 只看该作者
楼主好厉害啊,根本学不会

评分

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

查看全部评分

回复

使用道具 举报

逸之夏 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
57
钻石
性别
保密
注册时间
2018-2-26
查看详细资料
8#
发表于 2018-8-30 14:27:11 | 只看该作者
神乎其技,不服不行!

评分

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

查看全部评分

回复

使用道具 举报

淡然,流逝 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
19
钻石
性别
保密
注册时间
2018-8-23
查看详细资料
9#
发表于 2018-8-31 09:31:33 | 只看该作者
哇!楼主真NB

评分

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

查看全部评分

回复

使用道具 举报

沫雨丶 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
137
钻石
性别
保密
注册时间
2017-8-16
查看详细资料
受到警告 10#
发表于 2018-8-31 14:47:41 | 只看该作者
哇,挺厉害的

评分

参与人数 1人气 -1 金粒 -10 收起 理由
ruhuasiyu -1 -10 万用回复

查看全部评分

回复

使用道具 举报

Alyxiao 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
45
钻石
性别
保密
注册时间
2015-3-12
查看详细资料
11#
发表于 2018-8-31 15:05:09 | 只看该作者
我要顶帖..............

评分

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

查看全部评分

回复

使用道具 举报

风扇滑翔翼 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
4168
钻石
性别
保密
注册时间
2016-7-26
查看详细资料
12#
发表于 2018-8-31 18:45:10 | 只看该作者
所以我们需要一个修改世界产卵器的插件
回复

使用道具 举报

langyo_v3 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
5525
钻石
性别
保密
注册时间
2017-4-5
查看详细资料
13#
发表于 2018-9-1 00:03:14 | 只看该作者
不会写GPU计算……

同求GPU的操作接口文档

评分

参与人数 1金粒 +10 收起 理由
SmallFatCYW + 10 CUDA???

查看全部评分

回复

使用道具 举报

Sakur9 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
1352
钻石
性别
保密
注册时间
2018-9-1
查看详细资料
受到警告 14#
发表于 2018-9-1 14:29:52 | 只看该作者
厉害啦

评分

参与人数 1人气 -1 金粒 -10 收起 理由
ruhuasiyu -1 -10 万用回复

查看全部评分

回复

使用道具 举报

Nu_ta 当前离线
帖子
主题
精华
贡献
最后登录
1970-1-1
爱心
积分
956
钻石
性别
保密
注册时间
2018-7-16
查看详细资料
受到警告 15#
发表于 2018-9-3 06:06:46 | 只看该作者
给楼主大大的赞,很棒

评分

参与人数 1人气 -1 金粒 -10 收起 理由
ruhuasiyu -1 -10 万用回复

查看全部评分

回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2019-10-23 18:59 , Processed in 0.064740 second(s), Total 22, Slave 21 queries , Gzip On, MemCached On.

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

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

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