一邊聽一邊做的，由于英語不好可能有缺漏錯(cuò)。

請注意這個(gè)視頻是2021年2月的

P0 Structures and LCG (結(jié)構(gòu)與線性同余發(fā)生器)

種子查找的定義：在所有種子種找到滿足特定條件的種子。

與種子破解不同（相應(yīng)工具可用KaptainWutax的SeedCracker(https://github.com/KaptainWutax/SeedCracker)）

一、種子查找有什么用？

• 獲取特定生物群系（Biome）
• 獲取特定結(jié)構(gòu)（Structure）（四聯(lián)/三聯(lián)/二連）
• 獲取特定裝飾（Feature）
• 獲取特定地形（Terrain）
• 獲取結(jié)構(gòu)中的特定戰(zhàn)利品（Loot）（如附魔金蘋果）或?qū)嶓w（Entity）

二、如何查找種子？

• 打開世界：需要幾分鐘才能生成整個(gè)世界，很不好
• 使用amidst/chunkbase/MineMap等工具：好一點(diǎn)，但仍然不是很好，因?yàn)橹簧缮锶合岛徒Y(jié)構(gòu)。
• 使用特定的工具。如Zodsmar的SeedSearcherStandaloneTool(https://github.com/Zodsmar/SeedSearcherStandaloneTool)或Scicraft或Quad witch hut或seedhut.net等。
• 調(diào)用特定的庫。如minecraft Code, cubiomes(C/C++/Rust), Kaptainwutax的庫(https://kaptainwutax.seedfinding.com)。有Python、Rust、Scala的庫。

三、初步構(gòu)建一個(gè)種子查找的項(xiàng)目（以KaptainWutax的庫為例）

1. 初始化git倉庫
2. 初始化gradle骨架，視頻中選擇應(yīng)用(application)模塊，Java語言，Groovy語言，JUnit Jupiter測試框架。
3. 按照Kaptainwutax的README修改build.gradle。視頻中展示的master分支的build.gradle僅有6個(gè)庫，2022年1月8日北京時(shí)間21：04分查看的時(shí)候有9個(gè)庫。

四、世界生成的過程

以下過程是簡化過的

1. 生物群系
2. 結(jié)構(gòu)（如沙漠神殿、海底神殿等）
3. 噪聲（地形）
4. 雕刻（洞穴）
5. 特征

本P主要關(guān)注前兩步。

五、偽隨機(jī)數(shù)發(fā)生器（PRNG）

偽隨機(jī)數(shù)發(fā)生器運(yùn)用于許多游戲，因?yàn)槠淙菀资褂?，但不一定安全（可以參考各類RNG附魔）

5.1 Java Random

Minecraft中許多有關(guān)隨機(jī)數(shù)的部分使用了Java的Random類。其隨機(jī)數(shù)具有48位，因此只有2^48種可能的種子。其使用一線性同余發(fā)生器（LCG）。其運(yùn)算過程可以簡單表示為nextseed=(seed*a+b) mod m。

在結(jié)構(gòu)生成部分，其使用Java的Random類

5.2 QLCG

在生物群系生成部分，其使用另一LCG，采用的是Knuth MMIX上的實(shí)現(xiàn)，種子為64位。在生物群系生成中，會使用該LCG兩次，從而產(chǎn)生一個(gè)二次函數(shù)，類比LCG記為QCG。

由上述分析，我們在查找種子的時(shí)候應(yīng)當(dāng)優(yōu)先利用結(jié)構(gòu)，再利用生物群系，因?yàn)檫@樣遍歷的種子更少。

六、結(jié)構(gòu)生成的方法

區(qū)域(Region)是一個(gè)32*32區(qū)塊大小的單位。結(jié)構(gòu)在一個(gè)區(qū)域里最多生成一次，并且只能生成在24*24區(qū)塊范圍內(nèi)。（對于不同的結(jié)構(gòu)其范圍可能會變化，例如林地府邸就是80*80和60*60，但對于大部分結(jié)構(gòu)，例如沙漠神殿，范圍是32*32個(gè)區(qū)塊和24*24個(gè)區(qū)塊）

舉例：四聯(lián)女巫只能位于一個(gè)固定的相對區(qū)域的位置。

確定生成位置后，再進(jìn)行生物群系的判斷。也就是說我們上述的四聯(lián)女巫的位置必須是沼澤。這點(diǎn)一定要注意，例如如果我們需要村莊和海底神殿十分接近，海底神殿需要的海就可能會覆蓋村莊的位置。

七、展示ChunkRand中的一些方法和結(jié)構(gòu)查找的編寫

本P主要關(guān)注setRegionSeed，因?yàn)槠渑c結(jié)構(gòu)生成相關(guān)。

利用相應(yīng)庫查找目標(biāo)結(jié)構(gòu)的位置，然后判斷是否滿足生成要求。

現(xiàn)在我們把種子分為了16和48兩部分，如果我們能切得更多，那么所需時(shí)間又會下降。如果不需要獲取高度，不要使用噪聲進(jìn)行查找。

P1 生物群系與剪枝

生物群系是MC生成的基礎(chǔ)，其生成是一層一層調(diào)用的，構(gòu)成一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)。因此我們?nèi)绻覀兛梢栽诒容^早的時(shí)候就確定生物群系的種類，那么一個(gè)很大范圍內(nèi)的生物群系種類也就被確定，搜索速度可以上一個(gè)臺階。

這P只關(guān)注主世界生物群系，因?yàn)橄陆绾湍┑厣锶合凳褂脝涡卧肼?SimplexNoise)生成，只使用了48位種子。而主世界，正如我們之前說的，是64位種子。

第一步生成大陸和海洋，然后分為兩條支線，一邊生成河流，另一邊生成各種生物群系，將該二者合并，最后與海洋支線合并。由于海洋使用單形噪聲（？我看代碼看到的是ImproveNoise，不是SimplexNoise）生成，因此海洋生物群系只有2^48個(gè)種子。最后把4格的生物群系分布插值成1格的生物群系分布。

（詳細(xì)的生成過程可以看我的視頻對照）

二、剪枝

不同層如果鹽值不同，即使世界種子相同，種子也不同。

由于QCG取值時(shí)取高40位，我們可以計(jì)算每一層的種子，從而反推出世界種子，而不用遍歷64位種子。

三、展示生物群系查找的編寫

以沙漠為例，我們可以把其分解成幾步：

1. 當(dāng)前位置是陸地
2. 當(dāng)前溫度是干燥（id=1）
3. 不是特殊地形（惡地）
4. 抽中沙漠

然后遍歷，可以優(yōu)化結(jié)果。

如果要進(jìn)一步優(yōu)化，可以考慮將周圍群系的溫度納入考慮。

P2 地形與噪聲(Noise)

一、什么是噪聲？

（作者的話：我試圖去找到定義，但沒找到。我猜想應(yīng)該是看上去沒有規(guī)律的一定范圍內(nèi)的隨機(jī)值）

生成一幅圖像，其每一個(gè)點(diǎn)的顏色均勻隨機(jī)為白色或黑色。這樣形成的一幅圖像就是噪聲，就像黑白屏電視一樣。這種噪聲被稱為白噪聲。其在頻域上均勻分布。

然而，Minecraft中的地形噪聲不能像上述那樣簡單生成，對于一個(gè)位置，其需要保證各點(diǎn)之間盡量連續(xù)。這里使用了柏林噪聲(Perlin Noise)。還有其他種類的噪聲，比如Worely Noise和Value Noise，不過我們不繼續(xù)深入。單形噪聲(Simplex Noise)在Minecraft中是有使用的。

噪聲可以視為不同頻率正弦曲線的疊加。每次疊加頻率加倍，強(qiáng)度減半。如果我們增大初始頻率，我們會生成范圍更大的噪聲。如果我們對部分頻率下的曲線進(jìn)行平移，我們可以形成變化更加多樣的地形。通過調(diào)整分布函數(shù)，我們可以調(diào)整山谷和山峰的比例。

二、柏林噪聲(與單形噪聲)

考慮獲取一條隨機(jī)連續(xù)函數(shù)，我們可以先隨機(jī)在幾個(gè)點(diǎn)上生成值，再在這幾個(gè)點(diǎn)插值，最簡單的就是用直線相連，不過這樣轉(zhuǎn)折太大（連一階導(dǎo)都不連續(xù)）。

柏林噪聲使用的是另一種方式，其在每一個(gè)格點(diǎn)上生成一個(gè)斜率，然后按照斜率生成曲線，通過調(diào)整插值函數(shù)我們就可以獲得一條更加平滑的曲線。

拓展到更高維上，方法是類似的，只需要把斜率改為梯度向量，把數(shù)的相乘改為向量點(diǎn)乘。

單形噪聲可以看作是柏林噪聲優(yōu)化后的結(jié)果，其相對于柏林噪聲速度更快。設(shè)噪聲維數(shù)為n，柏林噪聲取值是取一個(gè)超立方體，需要取2^n個(gè)點(diǎn)；而單形噪聲取確定一個(gè)維的最少點(diǎn)，例如二維取正三角形（3個(gè)點(diǎn)），三維取正四面體（4個(gè)點(diǎn)），需要取n+1個(gè)點(diǎn)，取點(diǎn)數(shù)減少了。

三、Minecraft中噪聲的實(shí)現(xiàn)。

Minecraft中的噪聲取決于生物群系。在每一個(gè)單元內(nèi)的噪聲值是不同的。例如破碎的熱帶草原會使用不同的噪聲生成器。

我們會生成一個(gè)0~255的變換表（采用洗牌算法），用來獲得一個(gè)隨機(jī)的梯度向量。

Minecraft的噪聲使用的隨機(jī)數(shù)均是Java Random。

對于末地，我們是使用單形噪聲生成其生物群系。而對于下界，我們使用柏林噪聲生成其生物群系。由第一章的論述，我們知道下界和末地只有2^48種可能。主世界地形也是由柏林噪聲生成。

地形的生成過程是先生成一個(gè)只含石頭、水和空氣的骨架，然后再把表面替換成泥土或其他方塊。

隨后視頻作者在1.12下直觀展示了調(diào)整噪聲參數(shù)的影響，以及如果使用其他噪聲生成的地形。