叠加、数独、波函数坍缩算法。

Superpositions, Sudoku, the Wave Function Collapse algorithm.

频道:Martin Donald · 时长:14:27 · 发布:2020-07-31 · 播放:766805

在 YouTube 观看

简介

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

相关视频