【生肉】Seedfinding tutorial MC种子查找教程 by ...
一边听一边做的，由于英语不好可能有缺漏错。
请注意这个视频是2021年2月的
P0 Structures and LCG (结构与线性同余发生器)
种子查找的定义：在所有种子种找到满足特定条件的种子。
与种子破解不同（相应工具可用KaptainWutax的SeedCracker(https://github.com/KaptainWutax/SeedCracker)）
一、种子查找有什么用？
- 获取特定生物群系（Biome）
- 获取特定结构（Structure）（四联/三联/二连）
- 获取特定装饰（Feature）
- 获取特定地形（Terrain）
- 获取结构中的特定战利品（Loot）（如附魔金苹果）或实体（Entity）
二、如何查找种子？
- 打开世界：需要几分钟才能生成整个世界，很不好
- 使用amidst/chunkbase/MineMap等工具：好一点，但仍然不是很好，因为只生成生物群系和结构。
- 使用特定的工具。如Zodsmar的SeedSearcherStandaloneTool(https://github.com/Zodsmar/SeedSearcherStandaloneTool)或Scicraft或Quad witch hut或seedhut.net等。
- 调用特定的库。如minecraft Code, cubiomes(C/C++/Rust), Kaptainwutax的库(https://kaptainwutax.seedfinding.com)。有Python、Rust、Scala的库。
三、初步构建一个种子查找的项目（以KaptainWutax的库为例）
- 初始化git仓库
- 初始化gradle骨架，视频中选择应用(application)模块，Java语言，Groovy语言，JUnit Jupiter测试框架。
- 按照Kaptainwutax的README修改build.gradle。视频中展示的master分支的build.gradle仅有6个库，2022年1月8日北京时间21：04分查看的时候有9个库。
四、世界生成的过程
以下过程是简化过的
- 生物群系
- 结构（如沙漠神殿、海底神殿等）
- 噪声（地形）
- 雕刻（洞穴）
- 特征
本P主要关注前两步。
五、伪随机数发生器（PRNG）
伪随机数发生器运用于许多游戏，因为其容易使用，但不一定安全（可以参考各类RNG附魔）
5.1 Java Random
Minecraft中许多有关随机数的部分使用了Java的Random类。其随机数具有48位，因此只有2^48种可能的种子。其使用一线性同余发生器（LCG）。其运算过程可以简单表示为nextseed=(seed*a+b) mod m。
在结构生成部分，其使用Java的Random类
5.2 QLCG
在生物群系生成部分，其使用另一LCG，采用的是Knuth MMIX上的实现，种子为64位。在生物群系生成中，会使用该LCG两次，从而产生一个二次函数，类比LCG记为QCG。
由上述分析，我们在查找种子的时候应当优先利用结构，再利用生物群系，因为这样遍历的种子更少。
六、结构生成的方法
区域(Region)是一个32*32区块大小的单位。结构在一个区域里最多生成一次，并且只能生成在24*24区块范围内。（对于不同的结构其范围可能会变化，例如林地府邸就是80*80和60*60，但对于大部分结构，例如沙漠神殿，范围是32*32个区块和24*24个区块）
举例：四联女巫只能位于一个固定的相对区域的位置。
确定生成位置后，再进行生物群系的判断。也就是说我们上述的四联女巫的位置必须是沼泽。这点一定要注意，例如如果我们需要村庄和海底神殿十分接近，海底神殿需要的海就可能会覆盖村庄的位置。
七、展示ChunkRand中的一些方法和结构查找的编写
本P主要关注setRegionSeed，因为其与结构生成相关。
利用相应库查找目标结构的位置，然后判断是否满足生成要求。
现在我们把种子分为了16和48两部分，如果我们能切得更多，那么所需时间又会下降。如果不需要获取高度，不要使用噪声进行查找。
P1 生物群系与剪枝
生物群系是MC生成的基础，其生成是一层一层调用的，构成一个栈的数据结构。因此我们如果我们可以在比较早的时候就确定生物群系的种类，那么一个很大范围内的生物群系种类也就被确定，搜索速度可以上一个台阶。
这P只关注主世界生物群系，因为下界和末地生物群系使用单形噪声(SimplexNoise)生成，只使用了48位种子。而主世界，正如我们之前说的，是64位种子。
第一步生成大陆和海洋，然后分为两条支线，一边生成河流，另一边生成各种生物群系，将该二者合并，最后与海洋支线合并。由于海洋使用单形噪声（？我看代码看到的是ImproveNoise，不是SimplexNoise）生成，因此海洋生物群系只有2^48个种子。最后把4格的生物群系分布插值成1格的生物群系分布。
（详细的生成过程可以看我的视频对照）
二、剪枝
不同层如果盐值不同，即使世界种子相同，种子也不同。
由于QCG取值时取高40位，我们可以计算每一层的种子，从而反推出世界种子，而不用遍历64位种子。
三、展示生物群系查找的编写
以沙漠为例，我们可以把其分解成几步：
- 当前位置是陆地
- 当前温度是干燥（id=1）
- 不是特殊地形（恶地）
- 抽中沙漠
然后遍历，可以优化结果。
如果要进一步优化，可以考虑将周围群系的温度纳入考虑。
P2 地形与噪声(Noise)
一、什么是噪声？
（作者的话：我试图去找到定义，但没找到。我猜想应该是看上去没有规律的一定范围内的随机值）
生成一幅图像，其每一个点的颜色均匀随机为白色或黑色。这样形成的一幅图像就是噪声，就像黑白屏电视一样。这种噪声被称为白噪声。其在频域上均匀分布。
然而，Minecraft中的地形噪声不能像上述那样简单生成，对于一个位置，其需要保证各点之间尽量连续。这里使用了柏林噪声(Perlin Noise)。还有其他种类的噪声，比如Worely Noise和Value Noise，不过我们不继续深入。单形噪声(Simplex Noise)在Minecraft中是有使用的。
噪声可以视为不同频率正弦曲线的叠加。每次叠加频率加倍，强度减半。如果我们增大初始频率，我们会生成范围更大的噪声。如果我们对部分频率下的曲线进行平移，我们可以形成变化更加多样的地形。通过调整分布函数，我们可以调整山谷和山峰的比例。
二、柏林噪声(与单形噪声)
考虑获取一条随机连续函数，我们可以先随机在几个点上生成值，再在这几个点插值，最简单的就是用直线相连，不过这样转折太大（连一阶导都不连续）。
柏林噪声使用的是另一种方式，其在每一个格点上生成一个斜率，然后按照斜率生成曲线，通过调整插值函数我们就可以获得一条更加平滑的曲线。
拓展到更高维上，方法是类似的，只需要把斜率改为梯度向量，把数的相乘改为向量点乘。
单形噪声可以看作是柏林噪声优化后的结果，其相对于柏林噪声速度更快。设噪声维数为n，柏林噪声取值是取一个超立方体，需要取2^n个点；而单形噪声取确定一个维的最少点，例如二维取正三角形（3个点），三维取正四面体（4个点），需要取n+1个点，取点数减少了。
三、Minecraft中噪声的实现。
Minecraft中的噪声取决于生物群系。在每一个单元内的噪声值是不同的。例如破碎的热带草原会使用不同的噪声生成器。
我们会生成一个0~255的变换表（采用洗牌算法），用来获得一个随机的梯度向量。
Minecraft的噪声使用的随机数均是Java Random。
对于末地，我们是使用单形噪声生成其生物群系。而对于下界，我们使用柏林噪声生成其生物群系。由第一章的论述，我们知道下界和末地只有2^48种可能。主世界地形也是由柏林噪声生成。
地形的生成过程是先生成一个只含石头、水和空气的骨架，然后再把表面替换成泥土或其他方块。
随后视频作者在1.12下直观展示了调整噪声参数的影响，以及如果使用其他噪声生成的地形。
