链上程序化生成

原文：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在D.E.F 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项目，该项目大量使用了程序化生成，并对区块链游戏领域中的链上程序化生成的理解和应用产生了影响。

他们的贡献和努力推动了链上程序化生成领域的发展，并激发了在这一领域的进一步探索和发展。