请选择 进入手机版 | 继续访问电脑版

查看: 944|回复: 0

[技术] 在Unity中使用WFC算法无限生成城市

[复制链接]

1278

主题

1985

帖子

2万

贡献

管理员

Rank: 9Rank: 9Rank: 9

积分
26195
QQ
发表于 2019-1-17 04:00:01 | 显示全部楼层 |阅读模式
在游戏中,当玩家穿行于一座无止尽的城市,这座城市会随着玩家的移动由程序自动延伸,这是如何作到的呢? 本文将介绍使用WFC(Wave Function Collapse)算法程序化生成方法创建游戏中的无限城市。

01.jpg


项目下载
我们将介绍开发者Marian的游戏,你可以在itch.io下载到游戏的可玩版本,并在GitHub获取游戏源代码。

访问GitHub下载源代码:
https://github.com/marian42/wavefunctioncollapse

下载游戏可玩版本:
https://marian42.itch.io/wfc

下面的视频演示了在自动生成的城市中行走的过程。

观看视频

算法设计
在本文中,我们将使用“槽口”(slot)来表示3D体素网格中可以包含一个建筑模块或空白的位置,使用“模块”(module)来表示可以占用这类槽口的建筑模块。

WFC算法会为游戏世界中的每个槽口选择模块。槽口数组被看作是在未观测状态下的波函数。那意味着每个槽口都有一组可以放到槽口位置的模块。

按照量子力学的说法,也就是说“槽口是所有模块的叠加”。游戏世界从一个完全未观测的状态开始,该状态下每个模块都可以加入任意槽口。然后每个槽口会逐个坍塌。

这表示,算法会随机选取可用模块组中的一个模块。接下来会进行约束传播步骤。对于每个模块而言,只有以部分模块允许放在特定模块的相邻位置。无论槽口何时坍塌,可放在相邻槽口的模块组都需要更新。约束传播步骤是该算法中计算量最大的部分。

该算法的重点是决定要坍塌哪个槽口。算法总会使熵值最低的槽口坍塌。因为该槽口拥有的选择数量最少。如果所有模块都有相同的可能性,可用模块数量最少的槽口拥有最低的熵值。

通常情况下,模块被选中的可能性不同。具有相同可能性的二个可用模块的槽口,和具有不同可能性的二个模块的槽口相比,前者的选择比后者的多,即熵值更大。

02.gif


该算法本来用于从单个示例生成2D纹理。因此,模块可能性和相邻规则会根据它们在示例中的具体情况而定。

了解WFC算法的更多信息和示例:
https://github.com/mxgmn/WaveFunctionCollapse

下图是WFC算法的实现效果。

03.gif


建筑模块和原型
游戏世界约由100多个建筑模块生成,这些建筑模块都是使用Blender制作的。

04.png


WFC算法需要知道哪些模块可以彼此相邻放置。模块在每个方向各有一个可用相邻位置的列表,共有6个邻居列表。但我们不想手动创建列表。而且我们想实现自动生成建筑模块的旋转变体。

这二个需求可以通过使用模块原型(module prototypes)实现。模块原型是一个MonoBehaviour方法,它可以在Unity编辑器中方便的进行编辑。这些模块,可用相邻位置的列表以及旋转变体都是由模块原型一起自动创建。

一个重要的难题是:如何找到制作邻接信息的方法,从而实现自动流程。下图是我们想到的方法示意图。

05.png


每个建筑模块有6个连接点,每一个面一个,连接点带有一个数字。此外,水平连接点分为翻转,不翻转,对称三种类型。垂直连接点的旋转索引要么在0和3之间即上图的b、c、d,要么被标记为旋转恒定。

基于这些信息,我们可以自动检查哪些模块可以彼此相邻。相邻模块必须有相同的连接值。而且,模块的对称信息必须互相匹配,即垂直旋转索引相同且水平翻转情况相符,或者相邻模块必须是对称或恒定的。

06.png


我们设置了排除规则阻止原本允许相邻的情况。虽然有些建筑模块带有匹配的连接值,但它们相邻放置的效果并不好。

下图是没有使用排除规则生成的地图示例。

07.jpg


实现无限生成功能
原始的WFC算法生成的是有限地图,但是我们想要实现的是随玩家移动而无限延伸的游戏世界。

我们使用的第一个方法是生成有限大小的组块,并使用相邻部分的连接点作为约束。如果一个组块生成时,它的相邻组块已经生成,只有适合已有模块的特定模块才允许使用。这种方法的问题在于,无论槽口何时坍塌,约束传播都会限制可能性,即使只有少量槽口。

下图中,我们可以看到只坍塌一个槽口就影响到了所有位置。

08.png


当一次仅生成一个组块时,约束不会传播到相邻组块。这会导致原本因其它组块而无法使用的模块被选中。因此,当算法尝试生成下一个组块时,算法无法找到任何可用结果。

我们将地图存在字典中,该字典会映射槽口位置到槽口上。字典只在需要时出现。部分算法需要经过字典的调整。当选择要坍塌的槽口时,算法不会考虑所有无限槽口。而是只在玩家到达时生成地图的小部分区域。约束仍会在该区域外传播。

有些情况下,这种方法无法使用。试想,如果一个模块组带有之前截图中的直通管道,但却没有管道入口。如果算法选择使用了这种管道模块,它将创建出无限延长的管道。约束传播步骤会尝试分配无限的槽口数量给它。因此我们在设计模块组时想办法避免了这种问题。

边界约束
游戏中有2种重要的边界约束:面向地图顶部的面必须拥有“空气”连接点。面向地图底部的面必须拥有“固体”连接点。如果这些约束没有满足,则会出现地面的坑洞和没有房顶的建筑。

在有限地图中,解决办法很简单:对位于顶层和底层的所有槽口,移除所有带着无用连接点的模块。然后使用约束传播来移除其它无效模块。

09.png


在无尽地图中,这种方法不会起作用,因为顶层和底层有无数个槽口。想要简单点的话,我们可以在槽口创建后只移除顶层和底层的模块。然而,移除顶层的模块会产生相邻槽口的约束。这会造成级联效应,导致算法无限分配槽口。

我们的解决方法是创建1×n×1的地图,其中n是高度。该地图使用世界包装功能来传播约束。实现方法类似吃豆人的地图,从关卡右侧离开会进入关卡的左侧位置。无论何时在无限地图创建新槽口,它都会随着地图对应位置的模块组而初始化。

错误状态和回溯方法
有时WFC算法会达到槽口没有可用模块的状态。在应用于有限世界时,我们可以直接放弃结果并重新开始。但在无尽世界中,这种方法无法奏效,因为世界的一部分已经向玩家展示。

我们的解决方法是回溯。槽口的坍塌顺序和约束传播的部分信息会保存为历史信息。如果WFC算法出错,部分历史信息会被撤销。

这种方法在多数情况下有效,但有时错误被识别得很晚,导致要回溯很多个步骤。在罕见的情况下,玩家所在的槽口会重新生成。必须要强调,这种限制导致用于实现无尽世界的WFC算法方法对于商业游戏会存在一些问题,有待解决。

小结
本文介绍的项目基于Oskar Stålberg的演讲后开发的,Oskar Stålberg使用了WFC算法来生成《Bad North》中的关卡。

该游戏的源代码可以免费获取,并在MIT许可下使用,所以如果你想在游戏中加入自己喜欢的游戏机制,那就动手来实现吧。更多Unity教程,尽在Unity官方中文论坛(UnityChina.cn)
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表