前幾天摸魚刷B站，無意間刷到一篇專欄，MINECRAFT末地生成的規(guī)律性。這篇專欄展示了有關(guān)末地生物群系分布的一些性質(zhì)。隨便一搜，發(fā)現(xiàn)幾個月前也有人發(fā)現(xiàn)這一點，但并未找到相關(guān)解釋。那這篇專欄就來解釋這種現(xiàn)象的發(fā)生。

現(xiàn)象

先簡單介紹一下這個特殊現(xiàn)象吧：從一個點向東和北（即+X-Z方向）各走4096格，兩點的生物群系分布會非常相似。確切的說，是島的位置一致，但大小有一點區(qū)別。

如果使用工具獲得更大范圍尺度下的視角的話，可以很明顯看到這樣的條紋狀結(jié)構(gòu)，也證明了這種周期性的普遍存在。

而且，這種現(xiàn)象和種子沒有關(guān)系。任何一個種子都會生成這樣的周期結(jié)構(gòu)。

解釋

末地的生物群系生成的基礎(chǔ)是噪聲——更準確地說，是二維單形噪聲。而主世界和下界使用的噪聲則是更為有名的柏林噪聲。二者都是基于晶格的梯度噪聲，也就是說二者都需要在每一個晶格點上生成一個隨機向量。不同的是兩者劃分的晶格不同：柏林噪聲按正交平行六面體（二維情況下是正方形）劃分，而單形噪聲按單形（二維情況下取正三角形）劃分。

可以看出，柏林噪聲的劃分很明顯是比單形噪聲要簡單的。那為什么我們還會使用單形噪聲呢？主要的原因是單形噪聲在高維空間中的時間復(fù)雜度遠低于柏林噪聲。圖上我們可以看到，二維情形下，柏林噪聲要計算4個向量，而單形噪聲需要3個，差別不大。但隨著維數(shù)增長，柏林噪聲的時間復(fù)雜度呈指數(shù)級上升（2^n個向量），而單形噪聲則是線性增長（n+1個向量）。這就有所區(qū)別了。

歪斜的坐標系相較于垂直的，處理難度有一定上升。不過，從直角坐標變換到單形坐標的方法卻非常簡單：只需要將直角坐標系下坐標的所有分量求和，乘上一個因子，再與原本各分量分別相加，即可得到單形坐標系下的結(jié)果。

利用這個公式，我們就可以獲得點在單形坐標系中的坐標，進而獲得其所在單形的頂點的坐標。接下來就是生成頂點的梯度了。這個方式有很多，MC使用的是置換表法。算法的關(guān)鍵細節(jié)如下：

1. 利用世界種子初始化隨機數(shù)發(fā)生器

2. 利用洗牌算法將一個從0-255的數(shù)字列表打亂，獲得一個置換表。將該表視為循環(huán)列表

3. 對于一個單形頂點(x,z)，取置換表中z位置的數(shù)

4. 將該數(shù)加上x，再取一次

5. 取上述結(jié)果，從一個梯度列表中獲取梯度。

6. 利用取得的梯度計算噪聲值。

7. 若噪聲值小于-0.9，則該地有島嶼。

可以看到，結(jié)果的隨機性是依賴于置換表的隨機性的。然而，這個置換表相較于MC世界來說稍微有一些小，大范圍上容易出現(xiàn)周期性。而末地又沒有對這個結(jié)果作處理，結(jié)果就導(dǎo)致了周期性：

由上述變換公式，我們可以知道直角坐標系下的(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的循環(huán)列表，這兩個坐標獲得的結(jié)果是完全一致的。而末地生物群系是以區(qū)塊為單位進行計算的，區(qū)塊邊長為16。16*256剛好就是4096，即為重復(fù)單元的邊長。

更完美的周期性

上面已經(jīng)解釋了島位置為什么會出現(xiàn)周期性，然而，島的大小不是周期重復(fù)的終歸讓人看著有些不順眼。但其實在更大范圍上，島的大小也是有周期性的。這來源于另一個因子f=[(|x|*3439+|z|*147) mod 13]+9，這個因子越大，島越小。很容易看出，如果在保證xz不變號的情況下按上述周期平移13次，即向東和向北各平移53248格，這個公式里的模13就會給出完全一致的結(jié)果，我們可以打開驗證一下。

主世界和下界使用了柏林噪聲，并且也是使用置換表獲取梯度。那為什么它們沒有這樣明顯的周期性呢？

這里給一個原因。主世界和下界使用的所有噪聲都是用兩組柏林噪聲疊加起來的。每一組中的柏林噪聲互相之間的周期是2倍的關(guān)系，但兩個組之間沒有簡單的整比關(guān)系，因此沒有很明顯的周期性。

至于上述原因是不是唯一原因，我就不知道了。

結(jié)尾吐個槽，盡管和本文沒關(guān)系，但末地這一塊的隱式轉(zhuǎn)換太讓人頭痛了。你能想象上面那個取13模的運算，變量全是整數(shù)，但全程在用浮點數(shù)算嗎？