叠加、数独、波函数坍缩算法。
Superpositions, Sudoku, the Wave Function Collapse algorithm.
频道:Martin Donald · 时长:14:27 · 发布:2020-07-31 · 播放:766805
简介
Martin Donald 使用类似数独的约束求解来解释波函数坍缩算法,并展示了他如何用 Blender 和 Godot 实现它。它链接了演示和参考文章。
HN 为什么推荐
评论者推荐它作为理解 WFC 的最清晰方式,尤其是在关于 Townscaper 和基于瓦片的内容生成的线程中。
我发现它们很难理解,直到我找到了 Martin Donald 的这个视频 — HN, 2022
中文字幕节选
数独是一种在 9x9 网格上玩的单人游戏,其中 81 个格子进一步 被分成九个 3x3 的宫格,目标是用 1 到 9 之间的数字填满网格的每个空格 同时遵守某些规则或约束 这些规则如下:每一行、每一列和每一个宫格都必须包含 1 到 9 的所有数字,且同一行、列或宫格中任何数字都不能重复出现。当 观察一个空白的数独谜题时,网格上的每个方格都有可能是 九种可能数字中的任意一个,我们也可以说它们处于叠加态 同时占据所有九种可能状态,但通常数独谜题并不是从 空白开始的,而是已经填入了几个数字,它们的叠加态 坍缩为单一可能性。这些已坍缩的格子当然会影响 周围格子的可能性空间。例如我们知道,既然这一行里有一个 5 那么同一行、列或宫格中的其他格子都不能包含 5,因此我们可以把这个信息传播到受影响的格子,从 它们的叠加态中移除 5。在传播完初始条件所施加的 所有约束之后,接下来合乎逻辑的做法是寻找剩余 可能状态数量最少的格子,换句话说,我们要找到 熵最低的格子,并将其坍缩为单一可能性,再次 将结果传播到受影响的格子。我们优先处理低熵格子的原因 是剩余可供选择的状态更少,因此我们 做出糟糕选择的概率更低。我们将继续这个迭代过程, 不断坍缩和传播,直到所有格子都坍缩为单一 可能性,谜题就解开了。现在你大概期待的是 波函数坍缩算法如何工作的解释,而不是如何玩数独 所以让我来解释一下。波函数坍缩算法是一种程序化求解器, 它接收一个格子网格,每个格子都占据一个包含该格子所有可能状态的 叠加态,我们称之为波函数。格子的每个潜在状态,我们 称之为一个瓦片,都带有自己的一套相邻规则。例如瓦片 A 只允许这些瓦片在它北边,这些在东边,这些在它南边, 而这些在西边。就像人类解数独谜题的方式一样, 波函数坍缩算法会寻找熵最低的格子,或者 如果所有单元格的熵相等,就随机选择一个,并将其坍缩为单个 瓦片。接着它会进入传播这一坍缩后果的过程, 将其影响传递到其他单元格。例如,如果选中了瓦片 A,我们知道 紧邻已坍缩单元格东侧的那个单元格的叠加态,现在必须 被限制为只包含瓦片 A 在该方向上的有效邻居。而由于 这个单元格的可能性空间已经缩小,波函数坍缩 算法就需要继续把这些新的后果传播到与该单元格 相邻的单元格,如此类推,直到所有因我们初始单元格的坍缩 而失效的瓦片都被移除。这就是波函数 坍缩算法的一次迭代,它会继续对波函数进行迭代, 再次从寻找一个低熵单元格并将其坍缩开始,直到所有单元格都只包含 单个瓦片——无论是通过使所有其他可能的瓦片失效,还是通过 将该单元格坍缩为单一可能性。一旦出现这种情况,我们就可以说 波函数已经坍缩了。如你所见,波函数坍缩算法 其实相当直白,而且由于它与解决数独谜题的过程 有着不止是表面上的相似之处,它解释起来和直觉理解起来就更加容易。 现在你已经对波函数坍缩算法的工作原理有了很好的了解,
HN 上的讨论
在偶然遇到 Townscaper 之前,我不知道波坍缩函数。尽管如此,直到我看到 Martin Donald 的这个视频,我才觉得它们难以理解:[VIDEO] 现在,我只是在寻找一个用例,以便将来自己实现它们。 — V__, 2022-06
我不是 OP,但我最近碰巧看到一个很好的视频讲这个:[VIDEO] 简而言之,它是一种用于程序化生成平铺内容的算法,比如 2D/3D 游戏地图。 — orls, 2022-05
这使用了“波函数坍缩”算法。Oskar Stalberg 也做了一个很棒的工作原理解释演示[0],但仅凭那个可能不太容易理解。Martin Donald 做了一个非常好的 YouTube 视频讲解其原理[1]。“波函数坍缩”这个名字可能让人望而却步,但它其实相当直接,而且这个算法在很多场景都很有用,无论是游戏开发还是一般软件开发。其实我现在正在 HN 上拖延,本来在做一个 GPU 并行化版本,可以每帧生成数百万个位置。在 Townscaper 中,你其实可以看到这个算法运行得相当慢,会滞后于玩家输入,只是有一堆动画把它掩盖了。我希望最终能做出一个可以在 log2(mapsize) 时间内运行的版本。[0] [LINK] [1] [VIDEO] — t8y, 2021-12
我受到了 Nicky Case[0] 的启发,但最近独立地得出了和你这里相同的结论。2020 年 3 月,当疫情刚开始冲击美国时,在正式封锁之前,在公司范围内发布任何公告之前,也没有任何沟通,我的整个团队周五都来了,而我的整个团队周一都待在家里。本质上,周末发生了足够多的信息,使波函数坍缩了[1]。这正是我们追求的——如果你能照亮未来,使其他任何选项都不再是选项。我没有游戏开发经验,所以这条路会很长,但我认为我们走在正确的轨道上。[0]: [LINK] [1]: [VIDEO] — ItsMonkk, 2022-01
相关视频
- 破产的美国城市如何存活——债务 [ST04] · Not Just Bikes · 11:01
- 新线索!MH370 完整故事,迄今为止.. · Mentour Pilot · 56:06
- 医学测试悖论,以及重新设计贝叶斯法则 · 3Blue1Brown · 21:13
- 世界依赖于一系列奇怪的物品。它们并不便宜 · Veritasium · 18:32
- 为什么电子投票仍然是个坏主意 · Tom Scott · 12:00
- 贝塞尔曲线之美 · Freya Holmér · 24:25
- 样条曲线的连续性 · Freya Holmér · 1:13:50
- Rgba 与 TBC 的 elevated | 4k intro(FullHD 1080p 演示场景 demo) · Demoscene High-Quality Videos (Annikras) · 3:36
- 《守望先锋》游戏架构与网络代码 · GDC Festival of Gaming · 1:04:03
- 用数学绘制角色 · Inigo Quilez · 24:46
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- Wayland 和 X 背后的真实故事 - Daniel Stone (linux.conf.au 2013) · Mladen Mijatov · 45:35
- RustConf 2018 - 闭幕主题演讲 - 使用 Rust 进行游戏开发 by Catherine West · Rust Programming Language · 42:29
- 深入解析Nanite虚拟化几何体 · SIGGRAPH Advances in Real-Time Rendering · 1:09:59
- 古惑狼如何黑掉原版PlayStation | 战争故事 | Ars Technica · Ars Technica · 31:37
- Jonathan Blow - 如何编写独立游戏 - CSUA 演讲 · Alexandre Franco · 1:15:50