前几天摸鱼刷B站，无意间刷到一篇专栏，MINECRAFT末地生成的规律性。这篇专栏展示了有关末地生物群系分布的一些性质。随便一搜，发现几个月前也有人发现这一点，但并未找到相关解释。那这篇专栏就来解释这种现象的发生。
现象
先简单介绍一下这个特殊现象吧：从一个点向东和北（即+X-Z方向）各走4096格，两点的生物群系分布会非常相似。确切的说，是岛的位置一致，但大小有一点区别。
不要看岛的大小，只看位置这两张图是一样的
如果使用工具获得更大范围尺度下的视角的话，可以很明显看到这样的条纹状结构，也证明了这种周期性的普遍存在。
而且，这种现象和种子没有关系。任何一个种子都会生成这样的周期结构。
解释
末地的生物群系生成的基础是噪声——更准确地说，是二维单形噪声。而主世界和下界使用的噪声则是更为有名的柏林噪声。二者都是基于晶格的梯度噪声，也就是说二者都需要在每一个晶格点上生成一个随机向量。不同的是两者划分的晶格不同：柏林噪声按正交平行六面体（二维情况下是正方形）划分，而单形噪声按单形（二维情况下取正三角形）划分。
绘图有误差，单形噪声晶格的图应该是沿z=x对称的
可以看出，柏林噪声的划分很明显是比单形噪声要简单的。那为什么我们还会使用单形噪声呢？主要的原因是单形噪声在高维空间中的时间复杂度远低于柏林噪声。图上我们可以看到，二维情形下，柏林噪声要计算4个向量，而单形噪声需要3个，差别不大。但随着维数增长，柏林噪声的时间复杂度呈指数级上升（2^n个向量），而单形噪声则是线性增长（n+1个向量）。这就有所区别了。
歪斜的坐标系相较于垂直的，处理难度有一定上升。不过，从直角坐标变换到单形坐标的方法却非常简单：只需要将直角坐标系下坐标的所有分量求和，乘上一个因子，再与原本各分量分别相加，即可得到单形坐标系下的结果。
利用这个公式，我们就可以获得点在单形坐标系中的坐标，进而获得其所在单形的顶点的坐标。接下来就是生成顶点的梯度了。这个方式有很多，MC使用的是置换表法。算法的关键细节如下：
利用世界种子初始化随机数发生器
利用洗牌算法将一个从0-255的数字列表打乱，获得一个置换表。将该表视为循环列表
对于一个单形顶点(x,z)，取置换表中z位置的数
将该数加上x，再取一次
取上述结果，从一个梯度列表中获取梯度。
利用取得的梯度计算噪声值。
若噪声值小于-0.9，则该地有岛屿。
可以看到，结果的随机性是依赖于置换表的随机性的。然而，这个置换表相较于MC世界来说稍微有一些小，大范围上容易出现周期性。而末地又没有对这个结果作处理，结果就导致了周期性：
由上述变换公式，我们可以知道直角坐标系下的(x,z)，变换到单形坐标系中就变成[(1+F)x+Fz,Fx+(1+F)z]。再考虑一个直角坐标系下的新坐标(x+256,z-256)。计算后可以得到[(1+F)x+Fz+256,Fx+(1+F)z-256]。而由于置换表是一个长度为256的循环列表，这两个坐标获得的结果是完全一致的。而末地生物群系是以区块为单位进行计算的，区块边长为16。16*256刚好就是4096，即为重复单元的边长。
更完美的周期性
上面已经解释了岛位置为什么会出现周期性，然而，岛的大小不是周期重复的终归让人看着有些不顺眼。但其实在更大范围上，岛的大小也是有周期性的。这来源于另一个因子f=[(|x|*3439+|z|*147) mod 13]+9，这个因子越大，岛越小。很容易看出，如果在保证xz不变号的情况下按上述周期平移13次，即向东和向北各平移53248格，这个公式里的模13就会给出完全一致的结果，我们可以打开验证一下。
完全一致！
主世界和下界使用了柏林噪声，并且也是使用置换表获取梯度。那为什么它们没有这样明显的周期性呢？
这里给一个原因。主世界和下界使用的所有噪声都是用两组柏林噪声叠加起来的。每一组中的柏林噪声互相之间的周期是2倍的关系，但两个组之间没有简单的整比关系，因此没有很明显的周期性。
至于上述原因是不是唯一原因，我就不知道了。
结尾吐个槽，尽管和本文没关系，但末地这一块的隐式转换太让人头痛了。你能想象上面那个取13模的运算，变量全是整数，但全程在用浮点数算吗？
