Fl0w3r

carpe diem

Procedural Dungeon Generation Algorithm

Posted on In
3.7k 7 mins.

本文经 @a327ex：https://twitter.com/a327ex 授权翻译与转载

这篇文章阐释了一种生成随机地牢的技术,该技术首先由 TinyKeepDev：http://store.steampowered.com/app/278620 在此描述 https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/。我将比原始帖子中的步骤更详细地介绍它。此算法的实现流程如下：

生成房间

首先，你需要在一个圆内生成随机的生成一些具有一定宽度和高度的房间。TKdev 的算法通过正态分布来控制房间的大小，我认为这是一个好主意，因为它可以通过更多参数来进行控制。通过控制宽高比和标准方差可以生成外观不同的地牢。

一个你可能需要的方法 getRandomPointInCircle：

function getRandomPointInCircle(radius)
  local t =2*math.pi*math.random()
  local u = math.random()+math.random()
  local r =nil
  if u >1then r =2-u else r = u end
  return radius*r*math.cos(t), radius*r*math.sin(t)
end

你可以通过这里：https://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly 获取有关此代码原理的相关信息。这样你就能完成以下的内容：

有一件事是你需要考虑的，由于你（至少想法中）处理的是网格，因此你需要将所有的内容都对齐到相应的网格上。在上面的 gif 中，图块的大小是 4 像素，这意味着所有的房间的位置和大小都是 4 的倍数。为此，我们将宽度/高度的分配通过一个通过的函数进行处理，这个函数将处理图块的大小已达到整体的统一：

function roundm(n, m)
  return math.floor(((n + m -1)/m))*m
end



--Now we can change the returned value from getRandomPointInCircle to:function getRandomPointInCircle(radius)

  ...
  return roundm(radius*r*math.cos(t), tile_size), roundm(radius*r*math.sin(t), tile_size)

end

分离房间

现在我们将进入分离房间的部分，许多的房间都不应该像现在这样重叠并混杂在一个地方。TKdev 使用 separation steering behavior（直译为分离转向行为）来做到这一点，但我发现只使用物理引擎会容易的多。添加完所有的房间后，将物理引擎添加到每个房间上，然后模拟运行直至所有的房间都重新进入休眠状态。在 gif 中，我们正常的运行并模拟，但是当你在你的关卡之间进行此操作的时候，你可以使用更快和简单的方法。

我们并没有将物理效果绑定到网格上，但是在设置房间位置的时候，你可以使用 roundm 将其包裹起来, 这样你就可以得到彼此不重叠并且也视频网格的房间了。下面的 gif 显示了这一点，蓝色的轮廓是物理引擎得到的位置，因为他们对位置进行了取整，使得了他们和房屋之间的位置总有不匹配的情况。

可能会出现的一个问题，如果你的房间是水平或垂直居多的时候，比如我正在开发的游戏：

由于战斗是横向的，所以我希望大多数的房间的宽度是大于高度的。那么问题就变成了物理引擎如何解决长房间在互相重叠的时候解决碰撞：

如你所见，地牢变得很高，这样并不理想。为了解决这个问题，我们最初的时候在一个椭圆内而不是圆形上生成房间。这将保证地牢本地有合适的宽高比：

要在此区域内随机生成, 我们可以更改 getRandomPointInCircle 函数以便可以在椭圆内生成（在上面的 gif 中, 我们使用了 ellipse_width = 400 和 ellipse_height = 20）

function getRandomPointInEllipse(ellipse_width, ellipse_height)
  local t =2*math.pi*math.random()
  local u = math.random()+math.random()
  local r =nil
  if u >1then r =2-u else r = u end
  return roundm(ellipse_width*r*math.cos(t)/2, tile_size), 
         roundm(ellipse_height*r*math.sin(t)/2, tile_size)end

主要房间

下一步是要确定哪些房间是主要/中心房间，哪些不是。TKdev 使用的方法十分可靠：只需要宽度和高度高于某个阈值的房间。在下面的 gif 中，我使用的是 1.25*mean，这意味着如果 width_mean 和 height_mean 为 24，那么将选择宽度和高度大于 30 的房间。

Delaunay 三角分割+图

现在我们将选择所有房间的中电并将其输如到 Delaunay 过程中。你也可以自己实现此过程，或者去寻找他人完成并共享的代码。我很幸运 Yonaba 完成了它：https://github.com/Yonaba/delaunay。正如你从此页面中看到的，它接受点并输出三角形：

有了三角形后，你就可以生成图形了。如果你的手头有图形化数据的结构/库，这个过程应该很简单。如果你还没有这么做，那么你可以使你的 Room 对象/结构具有唯一的 id，这样你就可以将这些 id 添加到图形中，而不是四处复制它们。

最小生成树

在这之后，我们从图中生成一个最小生成树。同样，要么自己实现，要么找一个其他人完成的代码。

最小生成树将保证地牢中所有的主要房间都可以到达，但也使得它们不像以前那样全部相连。这是很有用的，因为在默认的情况下我们不希望所有的地牢都互相连接，同样我们也不想要存在无法到达的岛屿。然而，只有一条路线的地牢也不是我们想要的，所以我们要做的是从 Delaunay 中添加几条边。

在这添加更多的路径和循环，这会使得地牢更有趣。TKdev 会将 15% 的路径加回，我发现大于 8-10% 是一个更好的值。当然，取决于你的地牢的连接程度，这个值会有所不同。

走廊

对于最后的一部分，我们要为地牢添加走廊。为此我们需要遍历图中的每个节点，然后连接在它到其它节点直接的连线。如果节点在水平方向上足够近（他们的 y 位置相似），那么我们创建一条水平线。如果节点在垂直方向上足够接近，那么我们创建一条垂直线。如果节点在水平或垂直方向上都没有靠近，那么我们创建 2 条线形成 L 形。

我使用的测试足够的接近，这意味着计算两个节点的位置就应该检查中点的 x 或 y 属性是否在节点的边界内。如果是的话，那么我们从该中点的位置创建线。如果不是，那么创建两条线，从源的中点到目标的中点，但仅仅在一个轴上。

在上图中，你可以看到所有案例的示例。节点 62 和 47 之间有一条水平线，节点 60 和 125 间有一个垂直线。节点 118 和 119 具有 L 形。同样重要的是这些并不是我创建的唯一线条，他是是我绘制的唯一一条线，但我还在每条线的侧面创建了 2 条额外的线，以 tile_size 为间距，因为我希望我的走廊在宽度或高度上至少具有 3 个单位的宽度。

无论如何，在这之后我们要检查哪些不是主要/中心的房间并与线条直接发生冲突。然后将碰撞的房间加入到您现在所容纳这些信息的结构中，他们将作为走廊的骨架：

根据你最初设置的房间的均匀性和大小，你会在这看到不同外观的地牢。如果你想让你的走廊更统一，看起来不那么奇怪，那么你应该以降低偏差为目标，你要做一些检查，防止房间以某种方式显得太瘦。

对于最后一步，我们需要添加一个标准大小的网格来弥补缺失的部分。请注意，你实际上不需要网格的数据结构或任何太花哨的东西，你只需要根据图块的大小遍历每一行并将网格的圆角位置（将对应 1 个大小的单元格）添加到某个列表。这个在 3（或更多）行而不是只有一行的地方。

现在我们就完成了！？

最后

我从整个流程中返回的数据结构是：房间列表（每个房间具有唯一的 id，x/y 位置和高度/宽度的结果）；图，其中每个节点指向一个房间 id，边缘具有最小单位的房间的距离；然后是一个实际的 2D 网格，其实每个单元格都可以是空的（意味着它是空的），可以指向主/中心房间, 可以指向走廊房间或走廊单元。通过这三种结果，我认为可以从数据中活动你想要的任何类型的数据，然后你可以确认放置门、敌人、物品的位置，哪些房间有 Boss 等等。

Related Posts