在Unity中程序化生成的地牢环境

作者：vazgriz Unity官方平台 2020-01-06

本文由开发者 vazgriz撰写，将与各位分享如何在Unity中程序化生成2D和3D的地牢环境。

我非常喜欢Roguelike类游戏，而且Roguelike类游戏的关卡往往由许多地牢环境组成，所以我萌生出尝试自己编写程序化地牢生成器的想法。

地牢生成器有很多不同的实现方法，但我最后决定使用《TinyKeep》游戏的算法。通过扩展该算法，我使它可以在3D环境中使用，创建出带有多个楼层的地牢。

示例代码

下载示例的代码：

https://github.com/vazgriz/DungeonGenerator

了解《TinyKeep》游戏的算法：

https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/

2D环境

首先，我必须编写适用于2D环境的算法。我的算法和《TinyKeep》游戏的算法大致相同，但进行了一些调整，使算法可以实现更加有趣的关卡。

本文中示例场景的名称为Dungeon2D，代码保存在Scripts2D文件夹。

算法详解

在项目中，游戏世界被划分为矩形网格。假设1个单位的宽度足以表示一个通道。例如：在一个游戏中，1个单位可能对应着5米的距离。因此，我最后决定把游戏世界的大小设为30×30。

1、首先随意放置地牢区域，确保它们不会互相重叠。这些区域的布置方式并不重要，在本文示例中，我只是随机放置并调整了它们的大小。

我还在每个面添加了1个单位宽度的缓冲区，从而确保各个区域不会互相接触，但这对算法来说并不必要。


2、使用所有地牢区域创建Delaunay三角剖分图。我使用了Bowyer-Watson算法，该算法有不同语言的多种实现方法。我选择了最容易转化为C#代码的实现方法。


3、 使用三角剖分图创建最小生成树，我在此使用了Prim算法。


4、使用第3步中的每个边缘，创建通道的列表。生成树包含每个区域，因此它可以保证有通向每个区域的通道。

通过三角剖分图随机添加边缘到列表中。这样会把通道连成一圈，在这里，我把每个边缘的添加几率设为12.5%。


5、对于列表中的每个通道，使用了A*算法来寻找从通道开始到结束的路径。在找到一条路径后，它会修改游戏世界的状态，从而让之后的通道可以使用现有通道的路径。

通过使用特别的代价函数，我让算法可以使用之前迭代的结果，该方法的开销比创建新通道的开销更低。这样可以让寻路程序使用组合通道穿过相同的区域。

虽然寻路程序可以穿过区域，但是开销较大。因此在大多数情况下，寻路程序更倾向于绕着区域走。


下图是使用了美术资源实现的示例场景，美术资源和放置资源的代码不包含在示例代码中。



3D环境

有了2D环境的地牢生成器后，我开始把生成器转变为适用于3D环境。我们使用的所有算法都有3D版本，因此转换过程不会很困难。

算法详解

现在，我们的网格大小设置为30x5x30。

1、首先要修改的是：让所有地牢区域在3D环境中生成。


2、计算地牢区域的3D Delaunay三角剖分结果，或改为计算Delaunay四面体剖分结构。

然而，我在网上虽然可以搜索到很多研究论文，但没有找到任何实际的代码。最接近项目情况的结果是CGAL的3D三角剖分实现方法，但是该方法存在两个问题：

该功能模块只可以在GPL许可下使用。

代码有大量模板部分，而且非常难以理解，导致我无法找到实现算法的具体位置。

最后，我不得不学习Bowyer-Watson算法的工作原理，以便自己修改代码。

虽然，我并不理解外接圆对该算法的重要性，但至少我可以参考Wolfram MathWorld网站相关页面的信息，在编写的代码中使用了外接球体。由于大部分运算是4×4矩阵运算，我使用了Unity的Matrix4x4结构来处理运算过程。

MathWorld网站的相关页面：

http://mathworld.wolfram.com/Circumsphere.html

新的代码实现版本在Scripts3D/Delaunay3D.cs脚本中，如果需要基于MIT许可且易于理解的版本，可以参考这个脚本。


这种方法不会生成带有3个顶点的三角形，而是会生成带有4个顶点的四面体。其中至少有一个顶点会位于不同的楼层，否则该四面体会被销毁。这为寻路过程提供了很多在不同楼层之间移动的机会。

3、现在到了2D版本的对应第3步和第4步。我简单修改第2步的边缘信息，然后把它传入Prim算法。



4、3D版本的A*算法是情况变得复杂的地方。2D版本A*算法非常简单，只要使用A*算法的标准实现方法即可。但为了实现3D版本，我必须给寻路程序添加向上和向下移动的功能，让它可以连接不同楼层的区域。

我决定使用楼梯台阶来连接楼层，而不是垂直的梯子。但这也是问题出现的地方。相对于垂直上下移动的梯子来说，台阶更加复杂。台阶必须通过水平移动，来实现垂直移动，也就是说，要结合上升和前进的过程。我们可以通过下图来理解这个过程。

中心网格是蓝色实心正方形。附近的网格都是空心的正方形。寻路程序不能直接移动到当前网格正上方的网格，而是必须同时在水平方向和垂直方向移动。

如下图所示，这是从侧面查看的视图。我们可以直接移动到水平方向的相邻位置，但是无法直接去到顶部位置。


为了针对台阶构建寻路程序，我必须选好台阶的形状。如果把垂直移动和水平移动的距离比设为1:1，楼梯可能会太陡，因此我把比值设为1:2。每当在垂直方向移动1个单位时，寻路程序都要在水平方向移动2个单位。

此外，我们也要有合适的天花板，让角色可以站在台阶上，因此台阶上也必须有2个网格的高度。总的来说，每个台阶会使用4个网格。


此外，楼梯的顶部和底部必须有合适的通道。寻路程序不可以从侧面或相反方向进入楼梯。如果让楼梯直接穿过通道，则会产生非常奇怪的情况，如下图所示。



因此，楼梯形状必须如下图所示，寻路程序必须确保通道位于两个蓝色正方形的位置。如下图所示，楼梯会从蓝色实心正方形开始，向上移动一个楼层。


寻路程序必须在一步中从开始位置移动到结束位置。这意味着它必须在水平方向移动3个单位，在垂直方向移动1个单位。

A*算法的原理是每一步都会从一个节点移动到邻近节点。为了制作楼梯，我需要“跳过”楼梯的四个网格。

这里的难点在于：我需要让寻路程序围绕着它创建的楼梯工作。我无法把楼梯添加到A*算法的封闭集合中，因为那样会阻碍不同的路径从其它方向穿过这些网格。

但我也不可以把它们排除在外，因为这样会使寻路系统可以在最初创建的楼梯移动，出现上图片中不合理的情况。

解决方法是：对于每个节点，我们要跟踪该路径上的之前节点，然后在评估相邻节点时，如果遇到当前节点的路径，寻路系统会拒绝生成路径。

楼梯末端的通道会包含楼梯占用的所有网格、楼梯起点的节点和之前路径的所有节点。

寻路程序可以创建另一条路径穿过楼梯，因为第二条路径不了解楼梯的情况。

以上行为只需调用一次寻路函数，就可以处理多条潜在的路径。我们可以多次调用寻路函数，生成所有通道。之后的迭代会围绕已有的楼梯进行处理。

现在使用的算法不完全是A*算法。为了处理好楼梯，我们要应对许多特别情况。但如果每一步都检查之前的整条路径，这样会费时费力。

最初的实现方法是一路跟随节点到起点位置，像链表一样读取节点。因此，对于每个相邻节点来说，检查路径的时间复杂度为O(N)。

我使用的实现方法是：在每个节点中保存一个哈希表，该哈希表使用之前的节点作为键值。因此，检查路径的时间复杂度为O(1)，但是在节点添加到路径时，哈希表必须进行拷贝，使用的时间复杂度为O(N)。

我选择这个方法的原因是：我发现该算法读取路径的频率比修改路径的频率更高。

虽然我不知道如何对它的时间复杂度进行分析，但我认为总体时间复杂度应该在O(N^2)左右。这项改动是地牢生成算法的主要瓶颈。

在完成所有改动后，实现的结果如下图所示。


下面是使用美术资源实现的3D地牢效果。



结语

本文分享了在Unity中程序化生成2D和3D的地牢环境的方法。项目最难的部分是实现适用于3D环境的算法以及编写编写寻路程序。

创建的地牢环境非常有趣，可以作为一款游戏的基础，来动手尝试一下吧。

作者：vazgriz  
来源：Unity官方平台
原地址：https://mp.weixin.qq.com/s/3yM-mAAXq_fX5tcy82s0uQ

参与评论