本周，我开始研究一个新主题：地下城和洞穴的产生。我使用空间分区来生成房间，使用迷宫生成算法来生成走廊，并使用元胞自动机使洞穴看起来更自然。

空间分割

有很多方法可以生成地牢室（随机放置，基于代理的生成，使用分离转向行为或物理引擎等）。但是我最喜欢的方法是分割空间，因为它易于控制和扩展。

还有很多划分空间的方式：划分为网格，空间的二进制划分，用象限树划分空间，Voronoi图等。我决定使用空间的二进制分区，因为它非常适合生成矩形房间。由于在RogueBasin上发表了一篇文章，此方法已广受欢迎。

该算法的唯一复杂性是分离位置的选择。如果我们不对分隔位置施加限制，则会得到奇怪的空间分区：

有几种方法可以避免这种现象。其中之一是将分离位置限制为两个纵横比，例如在30％至70％或40％至60％的范围内。另一种方法是使用正态分布或二项式分布而不是均匀分布，从而增加了在边的中心而不是在边缘处分离的可能性。这些方法解决了这个问题，但是很难理解参数如何精确地影响最终结果。

因此，我使用了另一种方法，其优点是它具有一个参数并且易于理解：单元格的长度和宽度之间的最大允许比率。在对新分离进行采样时，我首先计算它可以具有的最小值和最大值，以使两个新像元的比率小于限制，然后在这两个边界之间进行均匀采样。这是更改最大允许比率时的结果：

以2.0至3.0的最大比率可获得良好的结果：

房间生成

下一阶段是房间中每个单元的生成。这里没有特别的问题，我只是设置了限制，以使房间不会太小且离牢房壁也不太近。

结果如下：

排骨选择

在二元分割地牢生成器中，分割步骤中使用的二叉树通常会重新用于生成通道。我没有这样做，因为这种方法似乎限制了我。

取而代之的是，在划分空间的阶段，我建立了一个双边连接的列表结构，这使我们能够知道哪些单元格彼此相邻。这样，我得到以下图形：

这种方法有三个优点。首先：如果将来我想改变空间的划分方式，则生成器的其余部分将保持有效，因为它在输入端仅接收半边缘数据结构。第二：现在选择要成为走廊的边缘，我可以使用任何算法生成迷宫。第三：如果我想向地牢中添加循环，则可以轻松实现。

现在，我仅使用Kruskal算法和城市街区的距离来选择边。结果如下：

走廊生成

下一步是从选定的边缘生成道路。这可能是生成器中最棘手的部分，因为我需要小心，以免走廊与另一个走廊相交。

结果如下：

洞穴产生

先前的结果适合创建地牢，地穴和其他人造结构，但我想给洞穴和矿山一个更自然的外观。如本 RogueBasin 文章所述，生成洞穴的经典方法是使用元胞自动机。细胞自动机的最大问题是其结果未得到完全控制。

无论如何，我决定使用元胞自动机来创建自然外观，但对它们施加限制以得到可控制的结果。我不仅使用两种状态：已死和还活着，还使用四种：绝对已死，已死，还活着，肯定还活着。 “完全准确”的状态不能在过程中更改；它们用于限制结果。

前面步骤中生成的房间和走廊中充满了“确实存在”的单元格。也就是说，我们仍然有支持室，我们保证它们将相互连接。尚未选择的边缘填充有“完全死”单元，因此在房间之间不会出现新路径。最后，在房间和走廊周围，我们随机地使一些细胞存活。这是初始配置：