程序化地牢生成算法

Number of views 405
gamedev

这篇文章解释了一种首次由Tiny Keep的开发者描述的生成随机地牢的技术。我将会比原帖中的步骤更详细地讲解它。此算法的工作原理大致如下：

image1738821275833.png

image1738821349920.pngimage1738821372503.png

生成房间

首先，你需要在圆内的随机位置生成一些具有一定宽度和高度的房间。TinyKeepDev的算法使用正态分布来生成房间大小，我认为这通常是一个好主意，因为它给你提供了更多的参数来调整。选择不同的宽度/高度均值与标准偏差的比例，通常会导致地牢看起来有所不同。

这意味着你可以通过调整这些参数来控制生成的地牢的风格和布局。例如，如果你设置较小的标准偏差，那么大多数房间将会接近你设定的平均尺寸；而较大的标准偏差则会导致房间尺寸变化更大，可能会有非常小或非常大的房间出现。这种灵活性可以帮助你创建出多样化的地牢设计。

你可能需要使用getRandomPointInCircle函数来实现在圆内随机位置生成房间的需求：

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

有了这个函数之后，你应该能够执行类似下面的操作来生成房间：

image1738821828891.png

image1738821849628.png

有一件非常重要的事情你必须考虑，那就是因为你（至少在概念上）处理的是一个瓷砖网格，你需要将所有的东西对齐到这个网格。在上面的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

分离房间

现在我们可以进入到分离的部分。有很多房间挤在一个地方，它们不应该以某种方式互相重叠。TinyKeepDev使用了分离引导行为来实现这一点，但是我发现使用物理引擎来做这件事要容易得多。在你添加了所有房间之后，只需添加与每个房间位置相匹配的实体物理体，然后运行模拟，直到所有物体都停止移动（进入“休眠”状态）。在gif图中，我正常运行模拟，但当你在关卡之间进行这项操作时，可以加快物理模拟的速度。

image1738822255704.png

image1738822281892.png

物理体本身并不与瓷砖网格绑定，但是在设置房间位置时，你使用 roundm函数进行包裹，这样就能得到既不互相重叠也符合瓷砖网格的房间。下面的图像展示了这一过程的实际效果，其中蓝色轮廓表示物理体，并且由于房间的位置总是被四舍五入，因此它们与实际房间之间总存在轻微的不匹配：

image1738823382627.png

一个可能出现的问题是，当你想要有横向或纵向倾斜的房间时。例如，考虑我正在开发的游戏：

战斗是非常横向导向的，因此我可能希望大多数房间的宽度大于其高度。这个问题在于，当长房间彼此靠近时，物理引擎如何决定解决它们之间的碰撞：

在处理房间布局设计时，特别是对于那些具有特定方向性要求的游戏，比如战斗场景非常强调横向布局的情况，可能会遇到一些挑战。当你希望房间宽度大于高度时，如果这些长房间相互靠近，物理引擎在解决它们之间的碰撞时可能会出现问题。这是因为物理引擎通常基于物体的实际形状和位置来计算碰撞反应，而这种计算方式可能导致不符合预期的结果，尤其是在需要保持房间在网格上对齐的情况下。例如，长房间之间可能会以奇怪的方式互相推挤，导致布局混乱或者不自然。这要求开发者寻找解决方案，确保房间既能满足游戏设计的需求（如横向或纵向的倾斜），又能正确地避免重叠并保持良好的视觉效果。

image1738823715086.png

如你所见，地牢变得非常高，这不是理想的情况。为了修复这个问题，我们可以最初在较窄的条带内而不是圆形区域内生成房间。这确保了地牢本身将具有不错的宽高比。

image1738823783901.png

要在这种条带内随机生成点，我们可以简单地修改getRandomPointInCircle函数，使其改为在椭圆内生成点（在上面的图中，我使用了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 > 1 then 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在这里的方法相当稳固：只需挑选宽度和高度超过某个阈值的房间作为主要房间。对于下面的图，我使用的阈值是1.25倍的平均值，这意味着，如果平均宽度和平均高度（width_mean 和 height_mean）都是24的话，那么宽度和高度大于30的房间就会被选中。

image1738824136742.png

Delaunay三角剖分 + 图

现在我们取所有选定房间的中点，并将这些点输入到Delaunay过程（Delaunay triangulation）中。你可以自己实现这个过程，或者找一个已经实现了它并分享了源码的人。在我的情况下，我很幸运，Yonaba已经实现了它。从那个接口可以看到，它接收点并输出三角形：

image1738824442593.png

在你获得了三角形之后，就可以生成一个图了。如果你手头有一个图数据结构或库，这个过程应该是相当简单的。如果你还没有这样做的话，最好确保你的房间对象/结构有唯一的ID，这样你就可以将这些ID添加到图中，而不需要到处复制房间信息。

最小生成树

在这之后，我们从图中生成一个最小生成树。同样，你可以自己实现这个算法，或者找到用你所用编程语言已经实现了该算法的人。

image1738824595487.png

最小生成树将确保地下城中的所有主要房间都是可达的，但同时也会使得它们不像之前那样全部互相连接。这很有用，因为默认情况下我们通常不希望地下城过度连通，但我们也不希望有无法到达的孤立区域。然而，我们通常也不希望地下城只有一条线性的路径，所以现在我们要做的就是从Delaunay图中重新添加一些边回去。

image1738824681260.png

image1738824709126.png

这将增加一些额外的路径和循环，使地下城变得更加有趣。TinyKeepDev得出的结论是重新添加15%的边，而我发现大约8-10%的比例更好。这个数值可能会根据你最终希望地下城的连通程度而有所不同。

走廊

对于最后一步，我们希望给地下城添加走廊。为此，我们需要遍历图中的每个节点，然后对每一个与它相连的其他节点之间创建线条。如果节点在水平方向上足够接近（它们的y位置相似），那么我们就创建一条水平线。如果节点在垂直方向上足够接近，那么我们就创建一条垂直线。如果节点既不在水平方向也不在垂直方向上接近，那么我们就创建两条线形成一个L形。

我用来判断何为“足够接近”的测试方法是计算两个节点位置之间的中点，并检查该中点的x或y坐标是否位于节点的边界内。如果在边界内，则从中点的位置创建线条。如果不在边界内，那么我会创建两条线，这两条线都从源节点的中点指向目标节点的中点，但只在一个轴向上进行连接。

image1738824967063.png

在上面的图片中，你可以看到所有情况的例子。节点62和47之间有一条水平线，节点60和125之间有一条垂直线，而节点118和119之间有一个L形。同样重要的是要注意，这些并不是我创建的唯一线条。它们只是我绘制的线条，实际上我还在这每一条线的侧面创建了两条额外的线，间隔为瓷砖大小（tile_size），因为我希望我的走廊在宽度或高度上至少有3个瓷砖宽。

之后，我们会检查哪些不是主要房间的房间与每条线相交。然后将这些相交的房间添加到你当前用于保存所有这些数据的结构中，它们将作为走廊的骨架：

image1738825103199.png

根据你最初设置的房间的均匀性和大小，你会得到外观不同的地下城。如果你想让你的走廊更加统一且看起来不那么奇怪，你应该瞄准较低的标准差，并且应该采取一些措施来防止房间在某个方向上过于狭长。

最后一步，我们只需添加单个瓷砖大小的网格单元来填补缺失的部分。请注意，实际上你并不需要一个网格数据结构或者任何复杂的东西，你可以按照瓷砖大小遍历每条线，并将经过网格舍入的位置（这些位置对应于一个瓷砖大小的单元）添加到某个列表中。这就是为什么有3条（或更多）线而不是只有1条线会显得重要的原因。

image1738825276810.png

image1738825341409.png

image1738825370062.png

这之后我们就结束了！

结束

从整个过程中返回的数据结构包括：一个房间列表（每个房间只是一个包含唯一ID、x/y位置以及宽度/高度的结构）；图结构，其中每个节点指向一个房间ID，边则包含房间之间以瓷砖为单位的距离；以及一个实际的2D网格，每个单元可以为空（意味着它是空的），可以指向一个主要/枢纽房间，可以指向一个走廊房间，或者可以作为走廊单元。有了这3种结构，我认为你可以获取布局中的任何类型的数据，然后你可以确定门、敌人、物品的位置，哪些房间应该放置Boss等。

image1738825501026.png

image1738825539912.png

image1738825602340.png

image1738825620623.png

作者：A Adonaac

点识成金AI端一碗翻译，转载请注明出处。

端一碗9
0 Answers