Building a Procedural Hex Map with Wave Function Collapse
过程化六边形地图生成器：技术详解 (Procedural Hex Map Generator: A Technical Deep Dive)
本文描述了一个使用过程化技术生成中世纪岛屿世界的项目，该世界包含道路、河流、海岸线、悬崖、森林和村庄等元素。
核心技术：波函数坍缩 (Wave Function Collapse - WFC)
该项目采用 波函数坍缩 (WFC) 算法，该算法最初由 Maxim Gumin 创建，现在已成为程序生成游戏开发中的热门技术。WFC 的基本原理类似于玩卡卡松 (Carcassonne) 游戏：拥有一系列图块，并确保相邻图块的边缘相互匹配（例如，道路连接到道路，草地连接到草地）。本项目扩展了这一概念，使用六边形图块，每个图块有 6 个边缘，因此约束条件更多，复杂性也更高。
地图生成流程：
- 混沌初始状态: 初始时，每个六边形单元格都处于“叠加态”，即可以包含所有 30 种图块类型的可能性 – 6 种旋转和 5 种海拔高度，总共900种状态。
- 约束单元格坍缩: 选择具有最少剩余选项（最小熵值）的单元格，随机选择一个有效的状态，从而“坍缩”该单元格。
- 约束传播: 该选择会约束其相邻单元格，移除与当前单元格边缘不匹配的相邻单元格状态。这种约束会像涟漪一样向外扩散。
- 重复: 重复步骤 2 和 3，直到所有单元格都被解决，或者程序陷入困境。
多网格问题与解决方案：
为了解决大型地图生成失败的问题，项目采用 模块化 WFC 方法。地图被分割成 19 个六边形网格，这些网格围绕中心排列成两个环，总共约 4100 个单元格。每个网格独立求解，但必须与相邻网格中已放置的图块匹配。
恢复系统：
WFC 算法可能会失败。项目包含一个分层恢复系统：
- 解固定 (Unfixing): 在约束传播过程中，如果相邻单元格产生矛盾，将其从固定约束转换为可解决的单元格，并将其邻居（两个单元格外）作为新的约束。
- 局部 WFC (Local-WFC): 如果主求解失败，则在问题区域周围的小半径（2 个单元格）内运行一个小型 WFC，重新求解重叠区域的 19 个单元格，以创建更兼容的边界。
- 放弃与隐藏 (Drop and hide): 如果以上方法都失败，则放弃有问题的相邻单元格，并放置山脉图块来遮盖接缝。
第三维度：海拔高度
地图包含 5 个海拔高度级别，用于模拟地形变化。道路图块必须与相同高度的道路图块或过渡图块连接，否则会产生不自然的场景，如悬崖峭壁或河流向上流动。
六边形坐标：
项目使用立方坐标系 (q, r, s) 来处理六边形网格，这简化了邻居查找和距离计算。
其他技术：
- 树木和建筑物: 使用 Perlin 噪声来确定树木和建筑物的分布，实现自然的聚类效果。
- 水效果: 使用程序化技术模拟水面效果，包括闪烁的波光和从海岸线发散的波浪。
- 渲染: 使用 Three.js 和 WebGPU 渲染器，以及 TSL (Three.js Shading Language) 编写自定义着色器。
- 优化: 使用 BatchedMesh 和共享材质来优化渲染性能。
技术栈：
- Three.js r183 with WebGPU
- TSL (Three.js Shading Language)
- Web Workers
- Vite
- BatchedMesh
- Seeding RNG
总结：
该项目成功地利用 WFC 算法、多网格方法和各种优化技术，生成了具有逼真细节和视觉效果的程序化六边形地图。项目代码和演示可在 GitHub 上获取。