地图种子的逆向研究 结构与群系分布

　　下面小编为大家带来我的世界结构与群系分布研究报告，这是一位游戏大神做的深度研究报告，里面深度研究了结构与群系分布，各位老铁不要错过下面的内容！

　　约定：

　　在本文中我们仅考虑了村庄的分布，事实上有一些其他结构的分布也是可以考虑的。

　　本系列文章中的Minecraft指的都是Minecraft Java Edition, 1.12.2。

　　本系列文章中引用的代码都来自 forge-1.12.2-14.23.2.2611-mdk。

　　当我们说”区块(x,z)“时，我们指的是chunk coordinate为(x,z)的区块。

　　我们将村庄中心所在的区块（也就是村里那口井所在的区块）称之为村庄区块。

　　猴子都知道的常识1：2^64的搜索空间对一般民用计算设备太大了。

　　猴子都知道的常识2：群系生成非常复杂。

　　分析：

　　让我们先看Village的生成判定：以下代码源自netminecraftworldgenstructureMapGenVillage.javaprotected boolean canSpawnStructureAtCoords(int chunkX, int chunkZ)

　　{

　　int i = chunkX;

　　int j = chunkZ;

　　if (chunkX < 0)

　　{

　　chunkX -= this.distance - 1;

　　}

　　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;

　　}

　　复制代码其中LINE_1处的this.world.setRandomSeed是一个与世界种子和当前区块位置相关的函数。如果将LINE_2注释掉，那么村庄生成就与群系无关，我们将这样修改过后会生成村庄的区块称之为拟村庄区块。则我们有显然的结论：村庄区块必然是拟村庄区块，但反之不对。

　　为什么我们要考虑拟村庄区块呢？这是因为拟村庄区块的判定直接取决于种子和区块位置（虽然群系分布也依赖于种子，但是我们这里的意思就是拟村庄区块不受群系影响），且它依赖的随机数生成器Java.util.random类不够安全（为什么不直接考虑村庄区块？那是因为生成群系时MC部分使用了自写的随机数生成器）。

　　通过对java.util.random的代码分析可知，给定种子s后，它生成的随机数列只与s的低48bit有关，虽然s在64bit的整数范围内取值（这里忽略技术细节）。结合上面摘录的代码，我们易知：如果a≡b (mod 2^48)，那么世界种子a和b所对应的拟村庄区块完全相同。

　　这个结论说明了两个问题：一，仅通过村庄位置是无法完全确定世界种子的；二、我们可以将首次爆破的搜索空间减少到2^48。三、上文中我们提到群系生成使用了MC自写的随机数生存器，它使用了世界种子的全部64bit，使得村庄区块相对于拟村庄区块所需搜索空间暴涨了2^16倍，也就是说直接通过村庄区块精确匹配的话，我们需要搜索整个int64范围，更不用说复杂的群系生成方**使单个搜索分支变慢多少了。

　　具体地说，我们首先通过跑图获得若干村庄区块（从而是拟村庄区块）的区块坐标(x_1,z_1),...,(x_n,...z_n) （这个n取多少读者自行决定，太多就会拖慢搜索速度，太少则会使通过的种子太多）。然后在0~2^48-1范围内搜索在(x_1,z_1),...,(x_n,...z_n) 这些位置是拟村庄区块的种子，得到若干备选项s_1,s_2,...,s_k（可能不止一个）。然后获得世界内某些位置的群系（当然，这种群系越稀少越好），再对每个n，计算以s_n+2^48*r（ 1<=r<=2^16）为种子的地图内这些位置的群系是否与给定的群系吻合。通过这样两轮筛选，我们就能获得世界的种子了。

　　实现与测试（概率）

　　第一部分爆破拟村庄区块的代码可以直接参考MC代码改写C++代码，第二部分群系判定比较复杂，可以参考某些已有的代码。

　　在我们的测试中，第一部分使用CUDA技术（自行编写），在GT920M显卡上（满负载），跑完整个2^48范围大约需要41小时（把家里唯一一台电脑的显卡搞坏的话大概会被打死，所以作者并没有真的跑完41小时，而是把任务分成了1024组，通过前几十组的用时估算出了总用时）。第二部分我们没有进行完全的测试（虽然代码已经写好且经过验证是可行的），相信应该非常快。

　　预防：

　　几乎不可预防，除非把MC使用的伪随机数生成器给换掉或者改变村庄算法。