Farbrausch 演示场景工具源码合集(fr_public)
Farbrausch 2001—2011 年 demo 工具源码合集,使用 C++,涉及 demoscene 与 D...
WaveFunctionCollapse · mxgmn/WaveFunctionCollapse
用 C# 实现的 WaveFunctionCollapse(WFC)程序化生成算法,可从单张示例位图生成局部相似的新位图:输出只包含输入中出现过的 N×N 像素模式,并在大量输出中近似保持这些模式的分布。程序先把输出初始化为「未观察」的叠加态,再逐步坍...
WaveFunctionCollapse(简称 WFC)是 mxgmn 用 C# 编写的程序化生成程序。它的目标很单纯:给一张示例位图,生成一堆和它“局部相似”的新位图。README 用两条准则来界定什么叫局部相似:
示例中 N 常取 3。输出被初始化成完全“未观察”的叠加态——每个像素值都是输入颜色的叠加,黑白输入下未观察状态会显示为深浅不同的灰。作者特别说明:叠加中的系数是实数而非复数,因此这并不是真正的量子力学,只是从量子力学借来了直觉。
README 设有 “How to build” 一节,说明如何从源码构建本项目;此外官方提供 Windows 版 release 下载,itch.io 上有可交互的图形版本,也能直接在浏览器里运行。想快速了解效果,可以在 YouTube 上观看算法演示视频。
README 给出了完整的五步描述:
关于“矛盾”:传播过程中某个像素的所有系数可能同时归零,说明算法撞上了矛盾、无法继续。README 指出,判断某张位图是否允许存在满足(C1)的其他非平凡位图是 NP-hard 问题,所以不可能造出永远能快速结束的解法;但在实践中,矛盾出现得异常罕见。作者还解释了为什么选择最小熵启发式——他注意到人类作画时往往也遵循类似的策略。
算法最简单的非平凡情形是 N×N 取 1×2。如果再简化一步,不存颜色对的概率而只存单个颜色的概率,就得到所谓“simple tiled model”——它的传播阶段本质上就是邻接约束传播。这种模型用“瓦片列表 + 邻接数据”来初始化,比用示例位图更顺手,邻接数据可以理解成一大批极小的样本。
实际瓦片集中相邻瓦片对的数量可能非常多,于是作者实现了一套对称性系统来压缩枚举:每块瓦片都要指定对称类型,这些类型与 D4 二面体群在瓦片及其对应字母上的作用同构;这样只需枚举到对称等价即可,对含大量对称瓦片的集合能把邻接表缩短数倍。
README 还辨析了几类瓦片集:无约束的 knot 瓦片集属于“easy”集合,永远不会出现无瓦片可放的死局,但 easy 集合中瓦片的相关性随距离迅速衰减,没有特殊启发式就难以产生有趣的全局结构;而 Circuit、Summer、Rooms 属于非 Wang 类型,其邻接关系无法由边标签导出,例如 Circuit 中两个 Corner 不能相邻却可以通过 Connection 相连,斜向轨道也不能改变方向。
高维下 WFC 的工作方式与二维完全一致,问题主要出在性能上。README 中的体素模型使用 N=2 的重叠拼接模型,块尺寸为 5×5×5 与 5×5×2,并叠加了高度、密度、曲率等额外启发式。三维简单拼接模型的实现在作者的另一个仓库 MarkovJunior 中,附带多套瓦片集与示例。
由于 WFC 天然支持约束,它可以很方便地与其他生成算法或手工创作结合。README 演示了 WFC 自动补全一个人工开头的关卡。与其他方法的配合关系也值得注意:ConvChain 满足强版(C2),输出的模式极限分布与输入完全一致,但不满足(C1),常产生明显缺陷,因此可以先用 ConvChain 得到充分采样的构型,再用 WFC 修正局部缺陷,思路类似先蒙特卡洛再梯度下降;Harrison 的纹理合成算法比 WFC 快得多,却难以处理长程相关(例如生成砖块严格对齐的砖墙),而这恰是 WFC 的强项,可以先让 WFC 生成完美的砖墙蓝图,再在蓝图上跑带约束的纹理合成。
WFC 已被移植到 C++、Python、Kotlin、Rust、Julia、Go、Haxe、Java、Clojure、Free Pascal、Dart、p5js、JavaScript 等多种语言,并被适配进 Unity、Unreal Engine 5、Godot 4 与 Houdini。它被用于 Bad North、Caves of Qud、Dead Static Drive、Townscaper、Matrix Awakens 等作品以及大量原型,也催生了新的学术研究。README 的 ports, forks and spinoffs 一节汇总了更多相关讲解、交互演示、指南与示例,适合作为延伸阅读。
Farbrausch 2001—2011 年 demo 工具源码合集,使用 C++,涉及 demoscene 与 D...
OpenKore 是《仙境传说 Online》(Ragnarok Online)的免费开源客户端与自动...
该仓库为 Java 语言项目,名称 BuildGDX 由「Build」与「GDX」组合,推测与 B...
《破碎像素地牢》是一款开源传统 Roguelike 地牢探索游戏,基于 Watabou 的《...
Hypersomnia 是 TeamHypersomnia 用 C++ 从零编写的一款多人俯视角(top-down...