👨🏻‍🌾 👰🏻 💇🏽 多层3D地牢的程序生成 😟 💇🏿 👨‍👩‍👦‍👦

最近，我玩了几次“ roguelike”游戏，所以我决定尝试编写自己的程序地牢生成器。解决这个问题的方法很多，我选择了此处描述的 TinyKeep作者的算法。我对该算法进行了扩展，使其可以在3D模式下工作，并且可以创建多层地牢。

示例代码发布在Github存储库中。为了演示，我使用Unity3D，但是这些概念当然适用于任何其他引擎。

二维

首先，我需要编写一个二维算法。通常，它的工作原理与TinyKeep算法相同，但在创建更有趣的关卡方面有所不同。

此示例的场景称为Dungeon2D。它的代码在Scripts2D文件夹中。

演算法

世界被划分为矩形网格。我假设1个单位足以指示走廊。在完整游戏中，Unity的1个单位可以对应于5米。对于网格，我选择了30×30的大小。

1.我们任意安排房间，但不要使它们彼此重叠。位置无关紧要，因此在此示例中，我只是给他们一个随机的位置和大小。另外，在每一侧，我添加了一个单位宽度为1的缓冲区（这样，房间之间就不会相互接触），但这对于算法起作用不是必需的。

红色矩形是房间

2.为房间创建一个Delaunay三角剖分图。我为此使用了Bower-Watson算法。此算法有多种语言的多种实现，我选择了一种易于移植到C＃的实现。

德劳内三角剖分

3.从三角剖分创建最小生成树（MST）。我为此使用了Prim算法。

MST走廊

4.我们创建一个走廊列表，从第3阶段的树的每个边缘开始。树包含所有房间，因此可以保证存在通往每个房间的路径。将三角剖分的边随机添加到列表中。因此，我们将在走廊中创建多个回路。在我的代码中，我使用了将每个边增加到12.5％的概率。

向MST添加多个边后的走廊。 请注意已出现循环。

5.对于列表中的每个走廊，使用A *算法查找从走廊的起点到终点的路径。找到一条路径后，它将改变世界状况，以便将来的走廊始终可以绕过现有的走廊。

我使用的成本函数使在不同的迭代中沿道路切割移动的成本比创建新道路的成本低。这激发了一种寻路算法来组合通过一个空间的走廊。可以在房间中移动，但费用昂贵。因此，在大多数情况下，寻路算法倾向于避开空间。

蓝色矩形是走廊

以下是一些使用实际图形资源的算法示例（资源和用于放置它们的代码不在存储库中）：

三维

创建了可用的2D地牢生成器后，我开始将其传输到3D。所有使用的算法都有3D版本，因此应该很简单，对吧？

演算法

现在，网格的大小为30x5x30。

1.第一个变化是3D房间的生成。这种变化是微不足道的。

请注意，房间可能高数层。

2.然后我们找到这些房间的Delaunay 3D三角剖分，或者说是Delaunay四面体。在搜索了有关“ 3D Delaunay三角剖分”或“ Delaunay四面体化”的信息后，我发现了很多研究文章，但没有一个代码示例。

与我需要的最接近的是3D CGAL三角剖分的实现，但是有两个问题。首先，该模块仅在GPL许可下可用。第二个-代码太多了，而且模棱两可，以至于我无法弄清楚算法的实现位置。

最后，我必须自己研究Bower-Watson算法的原理才能自己进行更改。我仍然不太明白为什么外接圆如此重要，但是至少我能够使用Wolfram MathWorld使用此页面用所描述的球体重写算法。由于这些主要是对4x4矩阵的运算，因此我将所有复杂的工作分配给Unity3D中的Matrix4x4类型。

如果有人需要带有MIT许可证的易于理解的代码，则此新版本位于Scripts3D/Delaunay3D.cs中。

很难注意到，但是该算法现在创建了具有四个顶点的四面体，而不是具有三个顶点的三角形。这些峰中的至少一个将位于另一层，因为否则四面体将退化。这给搜索阶段提供了许多在楼层之间移动的机会。

图3和图4。来自阶段2的完全不重要的变化的边缘可以传递给Prim算法。

3D-MST走廊

再次添加具有多个肋骨的走廊

5.当以3D算法A *实现时，困难就开始了。 2D版本非常简单，它是A *的标准实现。要将其传输到3D，我需要在路径搜索算法中添加功能，使其能够上下移动并连接不同楼层的房间。我决定不将地板连接到垂直楼梯，而是将楼梯连接起来。

这就是问题所在。爬楼梯比仅仅爬起来要复杂得多。要垂直移动，楼梯需要水平移动。也就是说，她有上升和跨度。看一下下面的图片。当前单元格是一个蓝色实心方块。可能的邻居是空的正方形。路径搜索算法无法移动到当前单元正上方的单元。相反，他将不得不水平和垂直移动。

侧面图。 您可以在侧面创建节点，但不能在顶部创建节点。

要为楼梯创建路径搜索算法，我需要选择其形状。高度与长度的比例为1：1太陡了，所以我选择了1：2的比例。对于每个垂直度量单位，梯子将移动两个水平单位。此外，要放置角色，楼梯上方必须有空间，也就是说，楼梯上方的两个单元也必须打开。通常，一个楼梯占用四个单元：

楼梯及其上方的自由空间

楼梯的顶部和底部也应该有一条走廊。路径搜索算法不应能够从侧面或相反方向进入楼梯。如下图所示，如果楼梯撞到走廊上将是不切实际和奇怪的。

也就是说，最后，楼梯的格式应如下图所示。路径查找算法应确保在两个蓝色正方形中存在走廊。

楼梯以蓝色实心方块开始，然后向上移动一层。

路径搜索算法应该一步一步地从起点移动到终点。这意味着它必须水平移动3个单位，上下移动1个单位。算法A *设计为在每个步骤中从一个节点移动到下一个节点。要创建楼梯，我必须“跳跃”楼梯的四个单元。

困难在于我需要某种方式让算法绕过它创建的阶梯。我无法将它们添加到封闭集 A *中，因为那样一来，通过这些单元格将无法从另一个方向进行操作。但是我也不能离开它们，因为这样路径搜索算法将能够沿着新创建的阶梯移动，从而产生上面所示的不良情况。

解决方案是，每个节点都应跟踪其路径中的所有先前节点。然后，在考虑相邻节点时，如果它引用当前节点的路径，则将拒绝该节点。楼梯末端的走廊将包含楼梯所占据的所有单元，楼梯起点处的节点以及通往楼梯的所有节点，依此类推，直到最开始。路径搜索算法可能会创建另一条经过楼梯的路径，因为第二条路径不会知道楼梯。

仅对于同一路径函数调用中的一些潜在路径，才需要上述行为。要生成所有走廊，寻找路径仍然存在许多挑战。随后的迭代将像以前一样简单地绕过现有楼梯。

此阶段的算法不再完全是A *。仅用于会计阶梯，其中有太多特殊情况。需要在每个阶段验证整个先前的路径是一个昂贵的过程。天真的实现会在开始之前跟踪所有节点，并将它们作为链表读取。然后，将花费O（N）时间检查每个相邻节点的路径。

我选择了此实现：在每个节点中存储一个哈希表，其键是先前的节点。由于此原因，在O（1）中执行了路径检查，但是，在将节点添加到路径时，需要复制哈希表，这就是O（N）。我之所以选择这种方法，是因为我意识到该算法读取路径的次数要多于更改路径。

尽管如此，尽管我不知道如何正确分析，但总体复杂度将约为O（N ^ 2）。此修改是地下城生成算法的主要“瓶颈”。

进行所有这些更改之后，结果如下：