零、承上啟下

之前賣了個關(guān)子,關(guān)于48bit篩種和四聯(lián)結(jié)構(gòu)的原理和使用方法沒有講，這里補充一下。在此之前，讓我們先從Minecraft中種子的原理說起。

一、什么是種子？

Minecraft中世界的生成是是依賴一個被稱作柏林噪聲的算法生成隨機數(shù)，它決定了世界的生成。它本質(zhì)上是一個種子隨機發(fā)生器。它需要一個整數(shù)作為參數(shù)，然后根據(jù)這個參數(shù)返回一個隨機數(shù)。如果你兩次都傳同一個參數(shù)進(jìn)來，它就會產(chǎn)生兩次相同的數(shù)（因此柏林噪聲實際上是偽隨機）。而世界種子，就是柏林噪聲的初始參數(shù)。如果我們輸入相同的世界種子，正常情況下生成的世界也是相同的。

當(dāng)世界生成算法更新（例如加入刪除生物群系，或者像1.7 1.18這樣的大改）后，相同的種子就不會生成相同的地形。這也是某些不同的游戲版本中，相同的種子（可能）無法產(chǎn)生相同的地形的原因。

二、種子的Top 16 bits和Lower 48 bits分別是什么，有什么用？

在Java版中種子一共2^64個，也就是一個64位的整數(shù)類型可以表示的最多數(shù)量（或者你也可以理解成任意一個種子都可以儲存在一個64位的整數(shù)類型中）。一個64位的整數(shù)類型也就是由64個“0”和“1”組成的數(shù)。舉個例子：

十進(jìn)制 -> -1041999999999999999

二進(jìn)制 -> 1111000110001010000100101000010101010000000010110000000000000001

種子的Top 16 bits和Lower 48 bits（高16二進(jìn)制位和低48二進(jìn)制位）實際上分別指的就是種子二進(jìn)制64位的前16位和后48位，一般來說為了方便使用十六進(jìn)制，此時前4位即為Top 16 bits后12位則為Lower 48 bits。再舉個例子舉個例子：

十六進(jìn)制 -> F18A 1285500B0001

二進(jìn)制 -> 1111000110001010 000100101000010101010000000010110000000000000001

三、姐妹種，結(jié)構(gòu)種是什么，低48位篩種又是怎么一回事？

在Minecraft使用種子生成世界中有個比較特別的現(xiàn)象：

主世界所有結(jié)構(gòu)（要塞除外）可能生成的位置和地獄大部分東西的生成只由這個種子的低48二進(jìn)制位決定。部分結(jié)構(gòu)例如女巫小屋的可能生成的位置更加簡單，只由種子的低20二進(jìn)制位決定。剩下種子的高16二進(jìn)制位與主世界的群系生成有關(guān)，也就確定了低48二進(jìn)制位得到的可能生成的位置實際上能否生成指定的結(jié)構(gòu)。事實上種子的低48二進(jìn)制位還和結(jié)構(gòu)箱子生成等雜七雜八的東西有關(guān)。

所謂結(jié)構(gòu)種(Structure Seed)，就是決定主世界結(jié)構(gòu)可能生成的位置的低48位所代表的種子。

例如，以下種子都擁有相同的結(jié)構(gòu)種，即0x29F20C01670A：

?

同時，這些具有相同的結(jié)構(gòu)種的種子，互為姐妹種（Sister Seed）。

姐妹種通俗來說就是低48二進(jìn)制位相同的種子。這些種子具有以下性質(zhì)：

?

看起來，這些種子只是一些共享了一點隨機數(shù)的生成，但是事實上這對于我們篩種來說，有很大的便利，它們的主世界結(jié)構(gòu)（群系相同的情況下）和下界末地是幾乎完全一樣的。主世界的結(jié)構(gòu)生成其實“曾經(jīng)”是一樣的，在種子生成時會先給出每個種子可能會生成的位置。我們以在cubiomes-viewer的圖層->結(jié)構(gòu)潛在生成位置處開啟查看。對于每個低48二進(jìn)制位相同的種子它們潛在生成位置相同。

例如0x5FFC0B2E8000這個結(jié)構(gòu)種，它在這個位置可能會生成兩個沙漠神殿：

?

但在實際生成中，由于每個種子的高16二進(jìn)制位不同，每個種子自然群系生成不同，當(dāng)然沙漠神殿必須在沙漠這類群系才能生成，因此在實際生成中，可能不是每次都會兩個都生成：

?

對于每個群系都會生成的結(jié)構(gòu)，例如廢棄傳送門，在所有姐妹種生成位置都是一樣的。

Cubiomes-viewer根據(jù)這個原理可以進(jìn)行低48二進(jìn)制位的篩種，也就是篩結(jié)構(gòu)種，先篩選低48二進(jìn)制位，后篩選高16二進(jìn)制位。

遞增搜索和低48二進(jìn)制位篩種因此具有完全不同優(yōu)勢：

遞增搜索按數(shù)字順序依次檢查種子，這種類型的搜索最適合于非窮舉搜索空間，并且具有很強的生物群落依賴性。

低48二進(jìn)制位搜索，搜索首先尋找合適的結(jié)構(gòu)種，當(dāng)找到后再依次找相同結(jié)構(gòu)種的每一個姐妹種是否有滿足條件的種子，這種搜索類型最適合于窮舉搜索和那些結(jié)構(gòu)要求非常嚴(yán)格的搜索。

篩種具體情況下使用正確的方式篩種，可以事半功倍。

四、四聯(lián)結(jié)構(gòu)又是怎么來的？

女巫小屋和海底神殿基于512*512格的mca（當(dāng)成區(qū)塊超級加倍版即可）來生成，每個mca只生成一個，對于女巫小屋和海底神殿四聯(lián)Cubiomes-viewer會利用已有的四聯(lián)結(jié)構(gòu)種種子集篩選四聯(lián)結(jié)構(gòu)（事實上女巫小屋都不需要低48二進(jìn)制位，它的生成僅由低20二進(jìn)制位決定）

四聯(lián)條件分為六種，前四個是四聯(lián)女巫小屋：

理想型四聯(lián)女巫小屋是最佳的四聯(lián)條件。

經(jīng)典型四聯(lián)女巫小屋（貌似是最早找出來的一批種子集）

普通型四聯(lián)女巫小屋是較好的四聯(lián)條件。

勉強型四聯(lián)女巫小屋較差。

四者之比約為2:3:8:20。

它們的區(qū)別主要用在生電上：理想型掛機半徑最佳，大概120格，經(jīng)典型次之。一般型掛機半徑不大于126格，它們都可以保證玩家掛機半徑內(nèi)有足夠的高度摔死女巫。勉強型則不太行。

四聯(lián)海底神殿的兩個條件分別代表四聯(lián)海底神殿大于95%和大于90%的面積（事實上四個海底神殿所有的刷怪面積都位于掛機范圍內(nèi)是不可能的）落在玩家的掛機半徑內(nèi)。二者之比約為2:15。

四聯(lián)結(jié)構(gòu)篩種中，坐標(biāo)會乘512（轉(zhuǎn)為mac坐標(biāo)）。

值得注意的是，因為mca的生成限制，四聯(lián)結(jié)構(gòu)總是生成在四個mca的角落上，cubiomes-viewer一般以四聯(lián)結(jié)構(gòu)左上角那個結(jié)構(gòu)所在的mca代表這個四聯(lián)結(jié)構(gòu)所在的位置，因此四聯(lián)的中心在cubiomes-viewer四聯(lián)結(jié)構(gòu)的x-1,x-1 mac。

選擇完四聯(lián)結(jié)構(gòu)這一個條件條件，實際會生成兩個條件：

第一個條件實際上就是我們之前說過的“螺旋迭代器1:512”，不過使用了低48位種子集，我們在篩選其他條件時也可以使用低48位種子集：

?

當(dāng)然我們只要把x4改成x3或者x2就能篩選三聯(lián)和二聯(lián)結(jié)構(gòu)。