datasheet

QbitAI量子位

文章数:1134 被阅读:11761439

账号入驻

无边无际的虚拟城市来了!能走能飞的Demo,一火再火的“波函数坍缩”开源算法

2018-12-26
    阅读数:
安妮 栗子 发自 凹非寺 
量子位 报道 | 公众号 QbitAI

神说,要有光。

于是有了光。

神说,要有一座城。

于是有了一座城。

神说,这座城要无限大。

神啊你别再说了,那是另外的价钱

不过,有种叫做波函数坍缩 (Wave Collapse Function) 的算法,可以让一座白茫茫的城,在虚拟世界里无限延伸

你跑得再快,飞得再远,都到不了它的尽头。

因为,这座城可以实时扩张,你往哪里走,它就往哪里生成,不会让你跑出去的。

而它背后的波函数坍缩 (WFC) 算法自诞生以来,每隔一段时日,便会引起人类蜂拥而至的关注。

不管是因为这赏心悦目的应用:

还是因为有人做了完整而深刻的解读:

无限之城一日游

一位推特名Marian42_ (简称玛丽安) 的妹子,用WFC建造了无限之城。

这座城里没有街道,有的是各式各样的房屋,和房屋之间的走道与楼梯。

沿着它们,你可以登上高台俯视全城,也可以穿行在安静的小道。

不安分的你,还可以从栏杆上一跃而下,并不会受伤,可以继续往前跑。

当你以为快要走到城市的尽头,前面看不到建筑物了,只要再跑几步,眼前便又实时生出一片新城

这里没有死胡同,只要你一直跑,城市就会在你前行的方向不断扩张。

除了跑跑跳跳,还可以用M键切换飞行模式,以上帝视角观察这座城,是如何流畅地向远方延伸:

当然,进城之后不要只顾着活动筋骨,偶尔也看看风景吧。

你会愉快地发现,中式的屋顶与罗马式的栏杆和石柱,在同一幢建筑里相敬如宾,丝毫不会忸怩。

有闲情的话,可以细数一下,把这89种元素集齐:

毕竟,除了标配的屋顶啦、回廊啦,幸运的人类还能在转角遇到优雅的喷泉 (Demo传送门见文底) 。

原理揭秘

无限城市一日游结束,是时候认真了解一下它背后的算法了:波函数坍缩,究竟是什么?

这个名字,来自量子力学中的一个概念,不过算法本身倒是比量子力学好理解得多,我们先从一个例子开始科普。

婚礼座次问题

想象一下你正在计划一场婚礼。问题来了,办几桌宴席、嘉宾坐哪里都需要考虑。不巧的是,为了照顾大家的情绪和满足各种条条框框的习俗,你需要调节几个问题:

  • 老爹不能坐在老妈两张桌子以内的距离

  • 老妹如果不能和其他兄弟姐妹坐一桌,会开启可怕的狂暴模式

  • 最好不要让叔叔和环保主义者挨在一起坐

不好,离婚礼只有五个小时了。此情此景下,你可以选择波函数坍缩来解决这个看似棘手的问题。

先画一张空白的座位表,记录下规则。

我们可以构建一张每个座位对应一个人的一一对应图,每个座位都可以对应任何人,也就是我们的初始波函数。

你的座位计划波函数就从这种变化万千的情况下开始了,开始的座次就是就是每个座位有效布局的完全叠加。

“叠加”的概念用薛定谔的猫来理解最好不过,在未查看猫的状态前,这就是一种叠加态,猫死猫活都可能存在。打开盒子后猫的叠加态小时,坍缩成确定态。

先选择一个位置,随机安排名单中一个人进去,此时座位波函数开始坍缩。

随后,确定下的每个人都影响后面人员的排布。如果Michele不想坐在2号桌,那他的妹妹Barack也肯定不在这一桌。通过不断更新可以坐在2号桌的人员名单,调整座位计划的波函数。

不断重复这个过程,直到每个座位的波函数都坍缩了或者遇到了矛盾无法安排。举个例子,如果遇到无法将剩余任何人安排到这个空位的情况,那这就是一种矛盾状态,最好的解决方法就是:重新开始。

再尝试几次,能按规则安排下每个人就算大功告成了。

位图(Bitmap)同理

婚礼排座位如此,波函数生成无限城市,将几十种不同的建筑元素拼接组合也是如此。

这个过程非常相似,只是改变了规则。台阶可以直接和平地连接,但无法和屋顶元素相连,波函数不断坍缩直到矛盾出现或全部坍缩。

两种情况也有不同,婚礼座次问题的规则是提前写好的,但无限城市的规则是用示例图像形式呈现的:

算法自己剖析示例,分析模式,自己推断出像素或者图块的规则如何。

那无限城市到底是如何将建筑元素拼接到一起的?我们先考虑一种简单的特殊情况,一种称为更简单的平铺模型(Even Simpler Tiled Model)的方法。

在这个模型中,可以将每种元素用像素形式呈现,并赋予一种单独的颜色。举个例子,下图陆地、海岸、海洋和山川四种地形图块都用了不同的颜色来表示。

更简单的平铺模型的规则指定了哪些图块可以彼此相邻放置,也规定了放置方向。每个规则都对应一个坐标,内含两个相邻的图块和一个方向,比如(海洋,海岸,左边)代表一个海洋图块可以放置在一个海岸图块的左边。

除了明确规则,还需要明确每种图块出现的频率,在生成时这些频率将作为权重,决定最终生成的画风。

前面看到的无限城市,生成过程也和这个“比简单还简单的平铺模型”类似,只是涉及的元素、规则更多。

坍缩

规则权重设置好,波函数坍缩可以开始了。

在无限城市问题中,最先确定的建筑元素是随机的,但算法会按照熵值最小排列方法不断扩充,也就是按系统的混乱程度最小排列。

一般来说,一个低熵的图块集合中,波函数坍缩时能选择的图块类型相对较少,最终图块遇到矛盾的可能性就会小一些了。

遵循单个图块的权重的同时,还要考虑整张图的全局权重。

比如,一个图块周围,台阶平地图块出现的概率各占0.5时,在全局权重的指导下,不会出现一块台阶一块平地的尴尬情境,而可能直接用10块平地拼接成“大平地”。

此时,波函数坍缩持续进行中。目之所及,无限城市中的地平线在不断快速向远处延伸。

所有输出的波函数,要么完全坍缩,支撑不断建起的亭台楼阁,要么出现了矛盾情况返回到某个节点重新不断生成。

最终,我们创造出一个虚拟的无尽头世界。

玩法还可以很花

想用波函数坍缩 (WFC) 来创造世界的,不止玛丽安。

2016年,两位美国少年发表了一个都市场景的滑板游戏,叫Proc Skater 2016

他们说,这是世界上第一个用WFC来生成关卡的游戏。

只不过,这个游戏里的空间,并非实时生成,也不是没有尽头。

在那之前,少年们还用同样的方法,建起过一座属于自己的城,有限的城。

当然,除了大兴土木之外,WFC还有其他功能。

比如,有人就用它来写十四行诗

爱丽丝还不知道自己的路该往哪走,就已经不在这里了。

(她来到了一个陌生的地方。)

那里有座厅堂,周围排满了门。

每一扇门都在说着一些友好的话。

(仿佛在请她进去。)

后面几句有点恐怖:

Down down down down.

Let me see that would be of very like a candle.

I wish you were down here with me.

大概,走进一扇门,便是不停地降落,降落。停下之后,周围已不是人间。

底下是清冷幽暗的世界,如果有人陪就好了。

句子再不通顺,也不妨碍人类的想象。反而越不通顺,越有梦境的错觉。

 《咒怨》试玩,来自山下智博

说不定有一天,恐怖游戏就不再需要循环场景来告诉你:逃不出去的。

只要有无限生成的世界,和鬼魅的情节或者台词搭配食用,就够了吧?

无限城市Demo试玩:
https://marian42.itch.io/wfc

无限城市开源代码:
https://github.com/marian42/wavefunctioncollapse

波函数坍缩原理:
https://github.com/mxgmn/WaveFunctionCollapse

波函数坍缩论文:
https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf

波函数坍缩科普文:
https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

年度评选报名

加入社群

量子位AI社群开始招募啦,欢迎对AI感兴趣的同学,在量子位公众号(QbitAI)对话界面回复关键字“交流群”,获取入群方式;


此外,量子位专业细分群(自动驾驶、CV、NLP、机器学习等)正在招募,面向正在从事相关领域的工程师及研究人员。


进专业群请在量子位公众号(QbitAI)对话界面回复关键字“专业群”,获取入群方式。(专业群审核较严,敬请谅解)

诚挚招聘

量子位正在招募编辑/记者,工作地点在北京中关村。期待有才气、有热情的同学加入我们!相关细节,请在量子位公众号(QbitAI)对话界面,回复“招聘”两个字。

量子位 QbitAI · 头条号签约作者

վ'ᴗ' ի 追踪AI技术和产品新动态

喜欢就点「好看」吧 !




最新有关QbitAI的文章

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: TI培训

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved