本文翻译自 Procedural medieval islands from 4,100 hex tiles, built with WebGPU and a lot of backtracking，原载于 Hacker News。

每张地图都独一无二。每张地图都是可种子的（seeded）且确定性的。

我从儿时在《AD&D 地下城主指南》的随机地下城表上掷骰子开始，就着迷于程序化地图。那种感觉很神奇——你不是在设计地下城，而是在发现它，一个房间接一个房间，骰子决定你得到的是宝库还是满是老鼠的死胡同。

多年后，我决定构建自己的地图生成器。它创建小型的中世纪岛屿世界——道路、河流、海岸线、悬崖、森林和村庄——完全程序化生成。使用 Three.js WebGPU 和 TSL 着色器构建，约 4,100 个六边形格子分布在 19 个网格中，约 20 秒生成完成。

在线演示 · GitHub 源码

就像 Carcassonne，但由计算机完成

核心技术是 Wave Function Collapse（WFC，波函数坍缩），这是 Maxim Gumin 创建的算法，已成为程序化游戏开发的宠儿。

如果你玩过《卡卡颂》（Carcassonne），你就已经理解 WFC 了。你有一叠地砖，放置它们使一切对齐。每块地砖都有边缘——草地、道路、城市。相邻的地砖必须有匹配的边缘。 道路边缘必须连接到另一条道路边缘。草地必须对接草地。唯一的区别是计算机做得更快，而且在遇到困难时抱怨得更少。

转折是：六边形地砖有 6 个边缘而不是 4 个。这意味着每个地砖的约束多 50%，组合爆炸是真实的。方形 WFC 已是被充分探索的领域。六边形 WFC……则不然。

地砖定义

这个地图有 30 种不同的地砖，定义草地、水域、道路、河流、海岸和斜坡。集合中的每块地砖都有一个定义，描述其 6 个边缘的地形类型，以及用于偏重某些地砖的权重。

30 种地砖类型，每种有 6 种旋转和 5 个高度级别。这意味着每个格子有 900 种可能的状态。

例如，这个三向交叉口有 3 个道路边缘和 3 个草地边缘。地砖定义：

{ name: 'ROAD_D', mesh: 'hex_road_D',
  edges: { NE: 'road', E: 'grass', SE: 'road', SW: 'grass', W: 'road', NW: 'grass' },
  weight: 2 }

每块地砖定义 6 种边缘类型。匹配边缘是唯一的规则。

WFC 如何工作

1. 从混沌开始。 网格上的每个格子最初是所有可能地砖的叠加态——所有 30 种类型，所有 6 种旋转，所有 5 个高度级别。纯粹的可能性。

2. 坍缩最受约束的格子。 选择剩余选项最少的格子（最低熵）。随机选择其有效状态之一。

3. 传播。 该选择约束其邻居。删除边缘不匹配的任何邻居状态。这向外级联——一次坍缩可以消除网格上数百种可能性。

4. 重复 直到每个格子都解决——或者你卡住了。

卡住才是有趣的部分。

多网格问题

WFC 对于小网格是可靠的。但随着网格变大，把自己逼入死胡同的几率快速上升。217 格的六边形网格几乎从不失败。4123 格的网格经常失败。

解决方案：模块化 WFC。不是一次性解决整个巨大的网格，而是将地图分割成 19 个围绕中心排列成两圈的六边形网格——总共约 4,100 个格子。每个网格独立解决，但它必须匹配相邻网格中已经放置的地砖。这些边界地砖成为固定约束。

有时这些约束根本不兼容。当前网格内部无论怎么回溯都无法解决由邻居造成的问题。这是我花费大量开发时间的地方。

19 个网格中已解决 5 个。每个网格是独立的 WFC 解决方案，受邻居边界地砖的约束。

回溯

这是 WFC 的肮脏秘密：它经常失败。你做一系列随机选择，传播约束，最终把自己逼入死角，某个格子没有有效选项了。恭喜，这个谜题无解。

教科书式的解决方案是 回溯（backtracking）——撤销你最后的决定并尝试不同的地砖。我的求解器跟踪它在传播过程中移除的每个可能性（delta 的”轨迹”），所以它可以廉价地回退而无需复制整个网格状态。它会尝试最多 500 次回溯才会放弃。

但仅靠回溯是不够的。真正的问题是跨网格边界。

恢复系统

在尝试了许多失败的方法后，我采用了一个分层恢复系统：

第 1 层：取消固定（Unfixing）。 在初始约束传播期间，如果邻居格子产生矛盾，求解器将其从固定约束转换回可解决格子。它自己的邻居（两格之外——”锚点”）成为新约束。这很廉价，可以处理简单情况。

第 2 层：局部 WFC（Local-WFC）。 如果主解决失败，求解器在问题区域周围的小半径 2 区域运行迷你 WFC——重新解决重叠区域的 19 个格子以创建更兼容的边界。最多 5 次尝试，每次针对不同的问题格子。局部 WFC 是突破。不再试图解决不可能的问题，而是回去改变问题本身。系统甚至达到了约 86% 的成功率一次性解决整个地图。

第 3 层：丢弃并隐藏。 最后手段。完全删除有问题的邻居格子并放置山地地砖来覆盖接缝。山脉很棒——它们的悬崖边缘匹配任何东西，而且看起来是有意的。没有人会质疑一座山。

之前：邻居冲突阻止了解决 之后：局部 WFC 修补边界

调试模式显示灾难。紫色=邻居冲突。红色=损坏的地砖。

第三维度

这个地图不是平面的——它有 5 个高度级别。海洋和草地从 0 级开始，但斜坡和悬崖可以向上或向下移动一级。低斜坡上升 1 级，高斜坡上升 2 级。3 级的道路地砖需要连接到另一个 3 级的道路地砖，或者在级别之间过渡的斜坡地砖。弄错了，你最终会得到道路死胡同在悬崖表面，或者河流向上流入天空。高度轴将 2D 约束问题转变为 3D 问题，这是大量地砖多样性（以及大量求解器失败）的来源。

自然渲染 | 调试颜色 | 高度颜色 地砖使用基于节点的 PBR 材质着色——MeshPhysicalNodeMaterial——带有自定义 TSL 颜色节点。每个地砖的高度编码在实例颜色中，着色器使用它在两个调色板纹理之间混合——低地获得夏季颜色，高地获得冬季颜色。

六边形坐标：出奇地奇怪

六边形数学很奇怪。由于有 6 个方向而不是 4 个，六边形位置和 2D x,y 坐标之间没有简单的映射。天真的方法是 偏移坐标（offset coordinates）——像常规网格一样从左到右、从上到下编号格子。这在你需要查找邻居、计算距离或做任何涉及方向的事情之前都有效。然后它很快就变得令人困惑，奇数行和偶数行有不同的公式。

偏移坐标：简单，直到你需要用它做任何有用的事情。

更好的方法：立方体坐标（cube coordinates）（q,r,s，其中 s=-q-r）。这是三个六边形轴的 3D 坐标系统。查找邻居变得微不足道——只需从两个坐标中加或减 1。

好消息是 WFC 并不真正关心几何。它关心哪些边缘匹配哪些——它本质上是一个图问题。六边形坐标只对渲染和多网格布局重要，其中 19 个网格本身被排列为六边形之六边形，有自己的偏移位置。

如果你曾经处理过六边形网格，你欠 Red Blob Games 的 Amit Patel 一笔感谢。他的六边形网格指南是权威参考。

树木、建筑，以及为什么不是所有东西都应该用 WFC

早期，我尝试使用 WFC 进行树木和建筑放置。坏主意。WFC 擅长局部边缘匹配但不擅长大规模模式。你会得到随机散落的树木而不是聚集的森林，或者均匀分布的建筑而不是聚集的村庄。

解决方案：老派的 Perlin 噪声。全局噪声场决定树木密度和建筑放置，完全独立于 WFC。噪声高于阈值的区域获得树木；略微不同的噪声驱动建筑放置。这给你有机的聚集——森林、空地、村庄——这是 WFC 永远无法产生的。我还使用一些额外的逻辑将建筑放置在道路尽头，港口和风车在海岸上，巨石阵在山顶等。

WFC 处理地形。噪声处理装饰。每个工具做它擅长的事。

建筑沿道路聚集。森林形成自然群组。这些都不是 WFC——全是基于噪声的放置。

水面：比看起来更难

水面效果是最难解决的视觉问题。海洋不只是蓝色平面——它有动画焦散闪光和从海岸线发出的海岸波浪。

粉色是最好的调试颜色。

闪光

我想要水面上那种”塞尔达传说：风之杖”的卡通微光。最初我尝试用四层 Voronoi 噪声程序化生成焦散。这非常耗费 GPU，而且看起来不太好。解决方案是使用简单的噪声蒙版采样小型滚动焦散纹理，看起来好多了而且超级廉价。有时简单的解决方案是正确的解决方案。

海岸波浪

波浪是从海岸线向外辐射的正弦带，灵感来自《Bad North》华丽的海岸线效果。要知道每个像素”离海岸多远”，系统渲染海岸蒙版——整个地图的俯视正交渲染，陆地白色，水域黑色——然后膨胀和模糊成渐变。波浪着色器读取这个渐变，以规则的间隔放置动画正弦带，用噪声打破模式。

逐层构建水面效果。

海湾问题

这在直海岸线上效果很好。在凹陷的海湾和入口，波浪线变得又粗又丑。基于模糊的渐变在海湾中将相同的值范围扩展到更宽的物理区域，拉伸波浪带。

我尝试了多种修复：

• 屏幕空间导数（Screen-space derivatives） 检测渐变拉伸——在一个缩放级别有效，在其他级别失效。
• 纹理空间梯度幅度（Texture-space gradient magnitude） 检测对向海岸边缘抵消——只检测狭窄河流，不检测真正有问题的海湾。
• 额外膨胀通道——也影响直海岸。

根本问题：模糊编码的是”附近有多少陆地”，而不是”最近的海岸边缘有多远”。这是不同的问题，无论多少后处理模糊都无法提取真正的距离。

解决方案是在 CPU 端做一个”包围度”探测，检查每个水域格子的邻居以检测海湾，写入单独的蒙版纹理，在封闭区域使波浪变薄。这有点像 hack，但它有效，波浪边缘在边缘处很好地变薄了。

在 Blender 中制作地砖

3D 地砖资源来自 KayKit 出色的低多边形中世纪六边形包。但它缺少完整地砖集所需的一些关键连接器，所以我重新拿起 Blender 技能并构建了新地砖：倾斜河流、河流死胡同、河流到海岸连接器，以及几种悬崖边缘变体。

关键约束：每块地砖正好 2 个世界单位宽，边缘类型必须在六边形边界完美对齐。正确设置 UV 意味着纹理图集正确映射跨地砖接缝。即使几个像素的 UV 错位也会产生可见的接缝线，破坏幻觉。

让它漂亮

算法给你一个有效的地图。让它看起来像你想去的地方是一个完全独立的问题。

WebGPU 和 TSL 着色器

渲染器是 Three.js with WebGPU 和 TSL（Three.js Shading Language）——新的基于节点的着色器系统，取代原始 GLSL。所有自定义视觉效果都用 TSL 编写，读起来像一种在你的 GPU 上运行的稍微外星方言的 JavaScript。

后处理堆栈

原始渲染看起来……还行。平淡。就像在荧光灯下拍摄的桌游。后处理管道是给它氛围的原因：

1. GTAO 环境光遮蔽——加深地砖之间、建筑和树木周围的缝隙。这让一切感觉更坚实。AO 结果被去噪以减少斑点。这在半分辨率运行，因为 AO 和去噪很昂贵。

2. 景深（Depth of Field）——基于相机距离的移轴模糊给它那种微型/立体模型的感觉。DOF 焦距随相机缩放缩放，在放大时给予更多 DOF。

3. 晕影 + 胶片颗粒——微妙的边缘变暗和噪声。刚好足够感觉模拟。

后处理。AO、景深和颗粒做了大量工作。

动态阴影贴图

阴影贴图视锥体每帧拟合到相机视图。可见区域投影到光源坐标系以计算最紧密的边界框，所以没有阴影贴图纹素浪费在屏幕外几何体上。缩小，阴影以较低分辨率覆盖整个地图。放大，阴影贴图收紧，给你个别地砖上清晰、详细的阴影。这防止了放大时的块状阴影伪影。

动态视锥体获得清晰细节。

优化

完整的地图有数千个地砖和装饰。单独绘制每一个会杀死帧率。解决方案是双重的：

BatchedMesh——每个六边形网格获得 2 个 BatchedMesh：一个用于地砖，一个用于装饰。BatchedMesh 的美妙之处在于每个网格可以有单独的几何体和变换，但它们都在单个绘制调用中渲染。GPU 处理每实例变换和几何体偏移，所以设置后 CPU 成本基本上为零。

无论地图复杂性如何，整个场景都用少量绘制调用渲染。这意味着基础渲染很便宜，所以你可以将 GPU 预算花在 AO、DoF 和颜色分级上。

一个共享材质——场景中的每个网格共享一个材质。网格 UV 映射到小调色板纹理，所以它们都从同一图像中提取颜色，就像共享的按数字涂色表。一个材质意味着绘制调用之间零着色器状态切换，所以 GPU 可以在不停止的情况下完成 38 个 BatchedMesh。

结果：4,100+ 个格子，38 个 BatchedMesh，整个东西在桌面和移动设备上以 60fps 渲染。

雪天。

总结

这次不需要骰子——但感觉是一样的。你按下一个按钮，地图自己构建，你发现算法决定放在那里的东西。看到道路和河流系统完美匹配是超级令人满意的。每次都不同，每次我都发现自己会探索一会儿。当年在地下城表上掷骰子的孩子会喜欢这个。

数字

• 30 种地砖类型
• 19 个六边形网格
• ~4,100 个总格子
• 每网格 2 次绘制调用
• 最多 500 次回溯
• 5 次 Local-WFC 尝试
• ~20s 构建所有网格
• 100% 成功率（500 次运行）

技术栈

• Three.js r183 with WebGPU renderer
• TSL (Three.js Shading Language) 用于所有自定义着色器
• Web Workers 用于离线程 WFC 解决
• Vite 用于构建
• BatchedMesh 用于高效地砖渲染（一次绘制调用）
• Seeded RNG 用于确定性、可重现的地图

试试看

玩在线演示——点击六边形按钮扩展地图，或点击”Build All”生成整个东西。有一个完整的 GUI 面板，有 50+ 个可调整参数，如果你想调整光照、颜色分级、水面效果和 WFC 设置。

GitHub 完整源代码

核心要点

1. WFC 算法的威力：Wave Function Collapse 是一种强大的程序化生成算法，但六边形网格比方形网格复杂得多，需要处理更多的约束和组合爆炸问题。

2. 模块化设计：对于大规模生成，将问题分解为小模块（19 个独立网格）比一次性解决整个问题更可靠。

3. 多层恢复系统：程序化生成必然会遇到矛盾，设计分层的恢复机制（取消固定 → 局部重解 → 隐藏问题）是关键。

4. 渲染优化：BatchedMesh 和共享材质是 Three.js 中高效渲染数千对象的关键技术。

5. WebGPU 的未来：TSL 着色器和 WebGPU 提供了比传统 GLSL 更现代、更灵活的渲染管线。

这个项目展示了如何将算法、美术和工程结合，创造出一个既有技术深度又有视觉吸引力的产品。对于对程序化生成或游戏开发感兴趣的开发者来说，这是一个极好的学习案例。