Notifications
Article
在Unity中程序化生成的地牢环境
Updated 12 days ago
1.2 K
11
本文由开发者 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许可且易于理解的版本,可以参考这个脚本。
新的代码实现版本在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环境的算法以及编写编写寻路程序。
创建的地牢环境非常有趣,可以作为一款游戏的基础,来动手尝试一下吧。
开发过程中遇到问题?打开Unity Connect App或者Unity编辑器内置群聊工具,在“技术交流”群聊组中提问。
Tags:
Unity教程推荐
9
Comments
汤梦龙
10 days ago
在校大学生
强啊!希望有朝一日也可以拥有这样的能力
0
匹诺曹
11 days ago
牛批
0
l
lqb
11 days ago
很酷,但是不会用
0
Force
11 days ago
不明觉厉,很强大
0
江南
11 days ago
膜拜大佬
0