程序化地牢生成算法 // TinyFlare

翻译原文http://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php

这篇文章阐述了一个生成随机地牢的算法，这是由tinykeepdev 游戏最早使用的技术。我这里会比原文章更详细的介绍生成步骤。算法步骤是这样工作的:

生成房间

首先你需要在一个圆圈内随机宽高生成一些房间，我认为tinykeep使用的是正太分布的算法来生成房间大小的。这通常是一个好主意，因为你可以给定更多的参数。选择不同的宽高比例和标准差会生成式样不同的地牢。

你需要做的是一个这样的函数 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

你可以从这里获得更多的信息。接下来你需要做的的是这些：

一个你必须考虑的非常重要的事情(至少在理论上)是当你处理一个瓷片(tile)型网格,你需要保证所有东西都在相同的网格山峰。在上边gif图中每个瓷片(tile)的大小是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使用分离操作行为来进行的。但是我发现使用一个物理引擎来做这些更加简单。当你添加完所有房间后，简单添加实体物理体来匹配每个房间的位置，然后进行模拟运行，直到所有物理对象都进入sleep状态。在这个gif中我运行了物理模拟，当你对不同级别做模拟时，你可以加速物理仿真模拟速度。

除了通过调用roundm函数设置房间位置并且保证彼此不重叠、不超出网格时，其他时候不需要绑定物理物体到tile网格上。下面这个gif中的蓝色边框体是物理物体，虽然他们和房间的位置之间会有微小误差:

当你调整房间的水平和垂直位置时，一个问题可能会出现. 组合非常水平，你可能会得到大多数的房间宽度比高度大很多。这个问题在于如何在长房间彼此接近时物理引擎如何解决他们的碰撞:

正如你所看到的，地下城变的非常高，这是不理想的。为了解决这个问题，我们可以使用一个扁的椭圆提到圆圈来生成房间。这样可以保证地牢生成后有一个合适的宽高比例:

为了在一个扁平区域内随机生成，我们使用一个椭圆(在gif中我使用了ellipse_width = 400, ellipse_height = 20)来替换”geRandomPointInCircle”函数:

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的做法非常可靠，控制宽/高比例的阀值进行挑选，下面gif中的阀值我们采用1.25乘以平均数。如果宽度平均数和高度平均数为24，则宽和高大于30的房间将被选中。

Delaunay三角化剖分图

现在我们采用所有选定房间的中心点位种子进行Delaunay程序化。你可以自己实现这个程序化方法，也可以采用别人已经实现好的源代码。在我的例子中，我很幸运的得到了Yonaba的实现。正如你从界面中看到的通过点划分的三角形:

在你进行三角化后，你可以的到一个图。通过这个图你可以非常容易的实现一个图的数据结构。如果你已经这么做了，你可以添加房间对象的数据结构指针到图中，而不需要再拷贝他们了。

最小生成树

接下来我们要从图中生成一个最小生成树。每一个语言。的实现你都可以找到别人实现的例子

最小生成树时用来保证地牢所有主要房间都是可到达的。但不想图那样所有房间都有连接。这是很有用的，在默认情况下，我们通常不需要超级连接地牢，但我们也不想要产生到达不到的岛屿。尽管如此，我们也不希望只有一条线性路。所以我们现在所做的是为Delaunay图题添加一些返回的边。

这会增加更多的路径和循环路径，这将使地牢变的更有趣。TKdev添加了%15回来的边，我发现增加%8-%10会是一个更好的值。这也取决于你想要得到的最终地牢。

走廊

在最后一部分，我们要添加地牢的走廊。要做到这一点，我们通过图中每一点连接到其他节点。如果节点水平位置足够接近(它们的位置y值近似)，在它们之间创建一条水平直线。如果节点垂直位置足够接近(它们的位置x值近似)，在它们之间创建一条垂直直线。如果两个节点水平和垂直位置都不接近。那么创建2条线类似一个L形状。
这里的足够接近的意思是计算2个节点的中心点位置，检查中心点的x,y属性是否在系诶单边界内。如果在则在两个中心点间创造一条直线，如果不在，则创造两条直线，从源点到目标点，但只有一个轴。

在上图中你可以看到所有情况的例子。节点在47与62之间有一条水平线，几点60到125间有一条垂直线，在节点118与119之间有一个L形状。同样重要值得注意的是哪些不适我所创造的唯一的线，我同样根据tile_size在每一边空白处绘制了额外2条线，因为我想我们的走廊宽高至少有3个tile的宽度。

然后开始用这些线与所有非主房间的矩形进行碰撞检测，如果有泵装，添加他们到现有结构，将他们作为走廊的骨架。

根据不同大小的房间来初始化你的地牢样式，如果你想让走廊看上去更加均匀，你需要针对一个低差分标准来选择保留某个房间或替换某个过细的房间。

对于最后一步，我们只需要添加tile大小的网格单元来弥补丢失的部分。注意你并不需要一个网格的数据结构，你只需要将每条线根据tile大小来在周围添加一个网格位置列表(即对应一个tile大小的单元)。这里通常是3个tile(或更多)宽度而不是一个。

我们完成了。

结束语

通过这个程序化过程我们返回的数据结构是: 一个房间列表(每个房间结构包含一个唯一ID,位置xy和宽高width,heigh);一个图,每个节点包含房间的ID和到另外相连房间的距离(多少个tile宽度);一个真实的二维网格，包含的单元可以是空的，可以是指向主房间的指针，可以是指向走廊房间的指针，或者是走廊单元格。有了这三种数据结构我们可以认为你可以得到你想要的任何数据。通过布局你可以找出那个地方可以放置门、敌人、物品或者哪个房间有boss等等。