鏈上程序化生成

原文：On-chain Procedural Generation

原作者：0xPARC

翻譯：JZ@Gametaverse

關於0xPARC：

0xPARC Foundation是支持以太坊上的應用級創新的研究組織。他們的工作重點有三個主要領域：

1. 研究與開發：0xPARC Foundation支持通過新穎的密碼學基元（例如零知識密碼學）啟用的實驗性應用。 0xPARC的項目旨在推動加密應用的技術可能性的邊界，包括鏈上和鏈下。
2. 開源工具和基礎設施：新的應用設計模式需要新的工具和基礎設施。 0xPARC Foundation鼓勵按照開放生態系統的價值觀進行這些工具的開發。
3. 教育和生態系統發展：0xPARC Foundation的目標是通過教育項目和其他社區倡議，將更多的開發人員、技術人員、作家和思考者帶到去中心化應用開發的前沿。

Gametaverse：在參加由ETH Global舉辦的自治世界黑客馬拉鬆時，我們的開發人員在實現鏈上的“戰爭迷霧”功能時遇到了一些問題，這篇文章給了我們很好的啟示。我們發現這篇文章還沒有中文版本，因此我們特別為開發人員參考而翻譯出來。值得一提的是，這篇文章是由0xPARC在2022年6月發布的。

程序化生成允許我們使用表達力強大且經濟實惠的算法在區塊鏈上以編程方式創建豐富的世界（如風景、地下城、城堡、雲等）。程序化生成算法通常試圖模擬自然界的形成過程，通過偽隨機輸出嵌入多樣性和真實感。

程序化生成算法可以基於特定規則和參數生成各種不同的環境元素。例如，在生成地形時，算法可以模擬地質作用、水流和風蝕等自然過程，以生成具有各種地貌特徵的地形。對於生成建築物或城市，算法可以考慮建築規則、道路網絡、人口分佈等因素，以生成具有多樣性和逼真性的城市佈局。

通過程序化生成，我們可以獲得大量的環境變化，因為算法可以通過微調參數或引入隨機性來生成不同的輸出。這使得遊戲開發人員、藝術家和創作者能夠以經濟高效的方式創建複雜的世界，而不必手工繪製每個細節。

將程序化生成與區塊鏈結合使用，可以實現內容的可驗證性、不可篡改性和去中心化性質。每個生成的環境或元素都可以追溯到其生成算法和相關參數，確保生成過程的透明性和公平性。

總的來說，程序化生成通過使用算法模擬自然過程和引入隨機性，為我們提供了一種高效、多樣且逼真的方式來創建豐富的世界。結合區塊鏈技術，可以實現內容的透明性和去中心化，為遊戲、藝術和其他領域的創作者帶來更多創作的可能性

我們為什麼使用程序化生成（procgen - Procedural Generation）？

我們在鏈上游戲中使用程序化生成的原因有以下幾點：

1. 存儲效率：鏈上存儲成本較高，因此存儲大量靜態遊戲內容（如地圖或遊戲世界）將是不切實際的。程序化生成使我們能夠按需生成內容，僅在玩家與特定坐標進行交互時存儲相應的坐標或屬性。這有助於優化存儲並降低成本。
2. 動態和無限的世界：程序化生成可以創建動態和無限的遊戲世界。與手動設計遊戲世界的方式不同，程序化算法可以生成多樣化的地形、地貌或結構，為玩家提供獨特且不斷變化的體驗。這允許玩家隨時間的推移進行探索和發現，使遊戲更具沉浸感和吸引力。
3. 探索和揭示：通過程序化生成，玩家可以逐步揭示和探索遊戲世界。而不是一次性展示整個世界，玩家可以在遊戲過程中發現新的區域、遭遇或挑戰。這增加了一種發現的感覺，為遊戲增添了冒險性和可重複性。
4. 資源利用效率：程序化生成算法可以在計算上高效，以盡可能少的計算資源生成複雜的內容。在鏈上游戲的環境中，計算資源有限，這一點尤為重要。

程序化生成在遊戲開發中並不是一個特定於鏈上游戲的新概念！幾乎所有你最喜歡的像素風遊戲都以某種方式使用程序化生成，包括《Minecraft》（用於地形生成）、《無人深空》（用於星球生成）和《Dwarf Fortress》（用於生物、宗教等）等等。

對於世界構建而言，程序化生成技術最早在20世紀90年代（甚至更早）的RAM為16kb、處理器為1MHz的個人電腦上得到發展。有趣的是，90年代資源受限的個人電腦與今天資源受限的以太坊虛擬機之間有許多相似之處。在許多方面，我們正處於加密原生遊戲的90年代，而當前在鏈上構建世界的過程是在權衡受限創意、善於利用資源和在鏈上計算所能實現的創造力之間尋找平衡的過程。

隨機生成的資產

最簡單的策略是對每個方格、星球、遊戲資產等進行“擲骰子”（運行一個偽隨機函數）。根據擲骰子的結果，你可以選擇為所討論的遊戲對象分配不同的屬性值——例如，如果一個生物的哈希ID以0結尾，將其著色為藍色；否則，著色為紅色。這是將游戲世界提升到簡單的白色畫布之外的最簡單方法。

在早期版本的《暗黑森林》中，每個坐標都有1/16384的機會“生成”一個星球，並且每個星球將隨機分配顏色、等級和各種統計數據。這種多樣性為玩家提供了隱含的目標——發現最稀有的星球類型，征服最高級的星球等。

在像CryptoKitties這樣的遊戲中，通過隨機生成特徵，可以創造出各種獨特且有收藏價值的數字資產。通過使用相對簡單的算法，開發者可以生成大量的組合，使每隻數字貓都具有與眾不同的特點。這種方法不僅為玩家提供了稀缺性和獨特性的感覺，還增加了資產的收藏性。

CryptoKitties的成功以及類似項目的後續擴散，展示了在區塊鏈遊戲領域中隨機生成的吸引力。它允許創造稀缺且獨特的數字資產，這些資產具有價值並可以在區塊鏈上進行交易。然而，需要注意的是，雖然最初的一波投機性NFT項目可能引發了炒作週期，但這類項目的長期價值和可持續性將取決於遊戲機制、實用性和社區參與等因素。

純隨機生成雖然比沒有生成要好，但是完全沒有更深層次的連貫性的隨機生成的世界和遊戲資產往往會相對迅速地變得乏味。如果沒有任何關於位置或進展的概念，遊戲玩法很快就會變成拉動老虎機的手柄。在一個完全由隨機生成的資產構成的宇宙中，一切都開始變得像白噪聲一樣。

從隨機性中提取架構

確實，在遊戲設計中，簡單的隨機生成並不能完全滿足玩家的需求。為了提供更有深度和吸引力的遊戲體驗，需要更高級的生成技術和設計原則。

其中一種方法是引入結構化的隨機生成，使生成的內容具有一定的連貫性和內在的規律。例如，通過引入特定的規則、約束和算法，可以生成具有地理連貫性、關聯性或主題一致性的世界。這樣的生成方法可以在保持一定的隨機性和變化性的同時，確保遊戲世界或資產之間有一定的一致性和連貫性。

此外，遊戲設計中的進展和發展是至關重要的。通過引入遊戲內的目標、任務、技能提升、解鎖內容等機制，玩家可以在遊戲中體驗到成長和進步的感覺。這種有目標和進展的設計可以增加遊戲的長期可玩性和吸引力。

另一個重要的因素是遊戲世界的多樣性和細節。純粹的隨機生成可能會導致內容的重複和缺乏獨特性。為了增加遊戲的深度和視覺吸引力，可以在生成過程中引入手工設計的元素、預定義的模板或特殊的事件和場景。

你也可以在這個Observable筆記本中互動式地嘗試這些波形。

總之，為了提供更有趣和豐富的遊戲體驗，隨機生成的設計需要結合其他的生成技術、遊戲進展機制和手工設計的元素。這樣可以為玩家創造出有深度、有吸引力且充滿活力的遊戲世界。

作為下一步，我們希望找到一種方法，將純隨機性轉化為具有可識別的“結構”——一種看起來具有隨機性但又不完全混亂的熵源。更正式地說，我們的目標是創建一個噪聲函數，在全局觀察時變化明顯，但在局部放大時具有一致性。為了理解製作這樣一個函數的直覺，讓我們從一些基本的東西開始：正弦波！簡要回顧一下，正弦波是一個方程，它看起來像y = 幅度* sin(頻率* x)。幅度和頻率參數允許您在水平和垂直方向上壓縮或拉伸波形。

另一個有趣的概念是疊加（superposition）：即將不同的波函數相加。看看當我們將許多具有隨機參數的正弦波相加時會發生什麼：

我們在全局上得到了更多的變化，同時保持了我們所期望的局部相似性特性。這就是程序化生成的工作原理！在形式上，每個組成波被稱為一個“八度”（octave），每個八度都為輸出表面增加了更多的複雜性。

Perlin噪聲不使用正弦波，而是使用了不同的函數。雖然它遵循了相同的思想，但與正弦波相比，它的規律性較弱，振幅更加一致。雖然技術上來說，我們可以使用簡單的三角函數（如正弦波）構建下面描述的所有生成算法，但Perlin噪聲更易於使用（且更美觀），因此我們將在接下來的內容中重點介紹Perlin噪聲。

Perlin噪聲是怎麼工作的？

在我們開始探索Perlin結構之前，我們還要介紹一種程序化生成的概念：維度性。在前面的部分，我們只使用了一維波形——那麼我們如何將這個概念擴展到二維地圖（或者說，N維空間）呢？首先，我們現在需要在不僅僅是一個維度上保持規律性，而是兩個維度上。

Perlin算法的核心思想可以概括如下：將二維網格劃分為塊（比如5×5的大小）。然後，在每個塊的角落放置隨機向量。接下來，要計算任意坐標（x，y）處的噪聲函數，獲取該塊角落處的隨機向量，並在它們之間進行插值——這只是一種使用某種微積分計算“在角落的隨機向量之間計算平滑值”的高級說法。有一些技巧可以在向量之間進行乾淨/巧妙的插值，但對於本討論來說，這些並不是特別重要。

Perlin噪聲算法通過在二維空間中進行插值，將一維的隨機性擴展到了二維。通過將隨機向量與塊的角落相關聯，並在不同塊之間進行插值，可以生成具有連續性和自然變化的二維地圖。這種插值方法可以保持相鄰塊之間的一致性，從而創造出具有平滑變化和規律性的地形或紋理效果。

使用這個過程在樣本二維地圖上分配灰度顏色值，可能會得到如下結果：

上面的圖像同時展示了一些隨機元素和一些局部結構元素。然而，這與一個豐富的遊戲世界地圖相去甚遠。

作為第一步，我們可以通過將可能的Perlin值範圍劃分為“區間”，為坐標分配方格類型。我們將把Perlin值解釋為相對於海平面的海拔高度：具有較低Perlin值的方格將被標記為水方格；接下來的較高Perlin值將被標記為沙灘（用於海灘）、森林、石頭和雪山（用於山頂）。

通過這樣的劃分，我們可以根據Perlin值的高低為每個坐標分配相應的方格類型。這樣就可以生成一個具有不同地形和特徵的遊戲世界地圖。根據不同的Perlin值範圍，玩家可以在地圖上探索水域、沙灘、森林、山地和雪山等各種地貌類型。

然而，僅僅通過Perlin噪聲生成地形還不足以構建一個豐富的遊戲世界。後續步驟可能涉及添加更多的元素和規則，例如地形高度對溫度、降水和植被分佈的影響，不同地形類型之間的過渡區域，以及人工設置的地標或城市等。

通過創造性地利用Perlin噪聲和其他生成技術，可以構建出獨特而豐富的遊戲世界，提供令人興奮的探索和豐富的遊戲體驗。

現在我們有了一些進展！這個地圖看起來更像一個世界了。人們可以想像玩家穿越森林，釣魚在海岸線，攀登壯觀的山脈到達一個地下城。

對於我們的Perlin算法，我們將進行一個進一步的修改。在上面的圖片中，地形有點“模糊”——所有的地理特徵存在於大致相同的尺度上。在下面的內容中，我們通過將不同頻率和振幅的Perlin函數相加來構建一個“多八度”（multi-octave）的Perlin函數，這在精神上類似於上面提到的三角函數的“疊加”（super-position）概念。

通過使用多八度的Perlin函數，我們可以在地圖上創建不同尺度和層次的地理特徵。低頻率的Perlin函數可以用於生成大範圍的山脈和山脈脊線，而高頻率的Perlin函數可以用於生成小規模的嶺、溝壑和細節。這樣的多層次生成方法可以增加地形的複雜性和細節，使遊戲世界更加真實和有趣。

通過使用多八度Perlin算法，我們可以創造出一個更加多樣和細緻的遊戲世界，其中不同尺度的地理特徵交織在一起。這為玩家提供了更多的探索和冒險的可能性，使遊戲世界更加豐富和引人入勝。

通過創建一個線性漸變，從地圖頂部的較低溫度過渡到底部的較高溫度，我們可以模擬緯度的影響，並創建一個更加真實的溫度模式。這為生成的世界增加了另一層深度，允許氣候和生物群落的分佈變化。

在包含溫度作為參數後，我們現在可以將不同的方格類型與特定的溫度範圍關聯起來。例如，高溫的方格可以被指定為沙漠或熱帶雨林，而較低溫度的方格可以被分配給溫帶森林或凍土地區。這進一步增加了生成世界的多樣性和逼真感，為玩家提供了地理真實感。

通過將溫度參數與地形高度、方格類型等其他因素結合起來，我們可以創建一個更加細緻和復雜的遊戲世界。這樣的生成過程可以為玩家提供更加真實、多樣和富有挑戰性的探索體驗。

 temperature += Math.floor((coords.x - 50) / 2);

通過將我們的類似正弦波的函數與線性函數相加，我們可以保留我們所期望的大致模式，同時保留通過將我們的舊正弦波函數與線性函數相加，我們可以保留我們所期望的大致模式，同時保留真實的地形特徵。現在，我們可以將這個溫度值與高度結合起來，用於切換方格類型：

通過結合溫度和高度值，我們可以為地圖上的每個坐標分配不同的方格類型。例如，高溫低海拔的方格可以被指定為沙灘，而低溫高海拔的方格可以被指定為雪山。溫度和高度的結合使得地形的呈現更加細膩和多樣化。

通過同時考慮溫度和高度參數，我們可以創建一個更加動態和逼真的遊戲世界。玩家在探索地圖時可以遇到不同的氣候和生物群落，遭遇各種多樣的地貌，並相應地調整他們的策略。

此外，溫度和高度參數可以影響遊戲中其他方面的內容，如資源分佈、生物棲息地和環境效果。這增加了遊戲機制的深度和復雜性，為玩家提供了更加沉浸和吸引人的體驗。

 function seedToTileType( Coords memory coords, uint256 perlin1, uint256 perlin2 ) internal pure returns (TileType) { uint256 height = perlin1; uint256 temperature = perlin2; temperature = uint256(int256(temperature) + (int256(coords.x) - 50) / 2); AltitudeType altitudeType = AltitudeType.SEA; if (height > 40) { altitudeType = AltitudeType.MOUNTAINTOP; } else if (height > 37) { altitudeType = AltitudeType.MOUNTAIN; } else if (height > 32) { altitudeType = AltitudeType.LAND; } else if (height > 30) { altitudeType = AltitudeType.BEACH; } TemperatureType temperatureType = TemperatureType.COLD; if (temperature > 42) { temperatureType = TemperatureType.HOT; } else if (temperature > 22) { temperatureType = TemperatureType.NORMAL; } TileType tileType = TileType.UNKNOWN; if (temperatureType == TemperatureType.COLD) { if (altitudeType == AltitudeType.MOUNTAINTOP) { tileType = TileType.SNOW; } else if (altitudeType == AltitudeType.MOUNTAIN) { tileType = TileType.SNOW; } else if (altitudeType == AltitudeType.LAND) { tileType = TileType.SNOW; } else if (altitudeType == AltitudeType.BEACH) { tileType = TileType.SNOW; } else { tileType = TileType.WATER; } } else if (temperatureType == TemperatureType.NORMAL) { ... // less snow, more grass } else { ... // less grass, more sand } return tileType; }

通過這一系列的修改，我們得到了這個美麗的地球地圖：

只需對顏色方案和視覺感知進行一些創意性的調整，就可以輕鬆衍生出新的地圖。比如，通過對這個地圖進行一些修改，可以將其視為類似於《Minecraft》下界（Nether）的地圖：

在之前創建這兩個地圖的過程中，我們使用了簡單的x 坐標來賦予我們的程序化生成的溫度值一種酷炫的全局特性——x 坐標較低的單元格比x 坐標較高的單元格更冷。那麼，如果我們根據距離地圖中心的距離來分配溫度呢？讓我們試試看：

我們得到了一個島嶼，中心是一座山峰，被雪地包圍，邊緣是沙灘。也許，如果你運用想像力，它看起來像是一個側面的笑臉幽靈的畫像。

讓我們進一步深入這個想法。與其在笛卡爾坐標系中考慮我們的地圖，為什麼不用極坐標係來看呢？簡單回顧一下，極坐標系統根據點到原點的距離和從原點到點與x 軸之間的角度來劃分點的位置。如果我們將極坐標系統作為生成的基礎，會發生什麼呢？

把世界放到鏈上

到目前為止，這篇文章關注的是在生成漂亮的地圖時使用Perlin噪聲和程序化生成的應用場景。但是，我們如何將這些世界上鍊呢？實際上，上面描述的所有生成過程都有相應的Solidity實現——如果你在本地檢查鏈接的分支，並在任何方格上右鍵單擊，你應該會看到在Solidity和JavaScript版本之間驗證生成的方格類型的控制台日誌——你可以在eth/contracts/TinyWorld.sol中找到生成代碼。所有Perlin代碼都被整潔地封裝在Perlin.sol庫中，你可以將其導出到自己的項目中使用。

感謝DarkForest團隊，他們還提供了一個可以計算和驗證Perlin噪聲生成的ZK電路，這對讀者來說可能會很有用。

更瘋狂的想法

在探討Perlin噪聲和程序化生成的過程中，我們還可以探索一些更加離奇和創新的想法。下面是一些可能會激發創意的想法：

1.將其放入SNARK中：為了構建一個擁有多種生物群落並隱藏在戰爭迷霧後面的豐富宇宙，Dark Forest在circom SNARK電路中實現了Perlin噪聲函數，而不是在Solidity中。

2.分形布朗運動：創建遞歸使用Perlin噪聲輸出以產生更多噪聲的地圖- 有點像採取我們在阿姆斯特丹探索中描述的前述矩形/極坐標系統，並用由Perlin噪聲定義的坐標系統替換它們。

3.Perlin星球：創建力場以生成連續的球形地圖是非常巧妙的！ Dark Forest還使用各種程序生成技巧來渲染豐富且視覺上獨特的行星。

4.體積雲：有效地創建逼真的移動雲天空是一項艱鉅的任務！儘管完整的生成方法有很多（嘈雜的）細節，但它也基於Perlin噪聲！

我們為什麼使用procgen？

有趣的是，在一方面，加密原生遊戲感覺就像是一個未被開發的潛力巨大的領域，有可能改變我們對遊戲的思考方式；而另一方面，現在我們仍然處在非常早期的階段，一些最好的鏈上游戲只需要使用簡單到可以在像這篇博客中描述的算法。約束會激發創造力，我們希望這篇博客能夠激發你的靈感，通過構建自己的加密原生遊戲來探索區塊鏈的優勢，無論它可能看起來多麼基礎。也許當前加密原生遊戲開發者面臨的最大陷阱就是陷入過度雄心勃勃的陷阱，為土地NFT和通證經濟學等運行L1。簡單而實用是原則（KISS）。

致謝：

如果您覺得這篇文章有趣，您可能會對在exgrasia上構建或探索方格合約感興趣，exgrasia最初是從對這種鏈上程序化生成形式的探索開始的！

這是gubsheep和Nalin在DEF CON上演講的更完善版本。這個概念最初是由Alan Luo介紹給我們的，他是Dark Forest核心團隊的早期成員，在構建Dark Forest渲染器時大量使用了程序化生成，並建議將Perlin Noise作為放入SNARK的候選算法。 Perlin Noise的Solidity實現最初由gubsheep編寫，zk-SNARK電路實現由Dark Forest團隊的另一位早期成員Robert Cunningham編寫。還要感謝與我們一起進行exgrasia景觀探索的Yush。

這些個人在探索和發展鏈上程序化生成方面發揮了重要作用。在這裡向他們表示感謝：

• Alan Luo：Dark Forest早期核心團隊成員，介紹了程序化生成和Perlin Noise的概念。
• Gubsheep：開發了Perlin Noise的Solidity實現，為演講和鏈上程序化生成的探索做出了貢獻。
• Nalin：為演講和鏈上程序化生成的探索做出了貢獻。
• Robert Cunningham：開發了與Perlin Noise相關的zk-SNARK電路實現。
• Yush：與我們一起進行了exgrasia景觀的初步探索。

這些個人在鏈上程序化生成的探索和發展中發揮了重要作用，對於理解和應用像Perlin Noise這樣的概念以及在區塊鏈遊戲領域中的鏈上程序化生成具有重要意義。

此外，還提到了Dark Forest項目，該項目大量使用了程序化生成，並對區塊鏈遊戲領域中的鏈上程序化生成的理解和應用產生了影響。

他們的貢獻和努力推動了鏈上程序化生成領域的發展，並激發了在這一領域的進一步探索和發展。