在Unity中程序化生成的地牢环境
本文由开发者 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#代码的实现方法。
Delaunay三角剖分效果
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算法。
通道的3D生成树
重新添加了带有边缘的通道
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环境的算法以及编写编写寻路程序。
创建的地牢环境非常有趣，可以作为一款游戏的基础，来动手尝试一下吧。
下载Unity Connect APP，请点击此处。观看更多Unity官方精彩视频，请关注“Unity官方”B站账户。
扫码在“技术交流“群聊组中提问，Unity社区和官方团队帮你解答。
推荐阅读
Made with Unity | 中国元素海外开花，打造西游新玩法
Unite Shanghai 2020正式启动，暖冬特惠票热销中
官方活动
点击“阅读原文”下载示例代码
↓↓↓