【技术贴】如何简单地做游戏随机生成地图
对于大多数游戏而言，内容消耗是开发商面临的棘手问题。而随机生成地图的方法能显著提高游戏的可重复性，丰富玩家体验。近期，一位海外资深开发者在博客中分享了其随机生成地图的方法，以下是编译后的博客内容。
整体算法概述
这篇博客主要介绍一种随机生成地图的技术。此前，TinyKeepDev曾对此进行过简要描述，本文将用更多细节和步骤来详细阐释。总体而言，整个算法的运行方式可用下面的 gif 图表示。
生成房间
随机生成房间尺寸与位置
首先，需要生成一些宽和高不同的房间，并随机放置在一个圈内。TKdev 的算法采用常见方法随机生成房间尺寸，这是个不错的思路，因为它能提供更多可调节的参数。通过使用不同的宽高比例和标准偏差，可以生成外观各异的副本地牢。
这里可能会用到 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 网格
需要注意的是，由于是在处理 tile 网格，所有元素都必须对齐到同一个网格中。在上图的 gif 中，tile 的尺寸为 4 像素，这意味着所有房间的位置和尺寸都必须是 4 的公倍数。为实现这一点，可将位置和宽高比例处理逻辑封装到一个函数中，使这些数值与 tile 尺寸相匹配。
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 使用了分离转向的方法，而本文作者发现使用物理引擎实现更为简便。在添加完所有房间后，为每个房间添加匹配其位置的物理物体（solid physics body），然后运行模拟，直到所有物体都处于休眠状态。在 gif 中，模拟以正常速度运行，但在处理不同关卡间的模拟时，可以加快速度。
物理物体与 tile 网格匹配问题
这些物理物体本身与 tile 网格并无直接关联，但当设定好房间位置并结合随机指令后，就能得到不重叠且与 tile 网格匹配的房间。下面的 gif 展示了这一过程，蓝色外形代表物理物体，由于其位置分散，与房间之间总会存在一些不匹配。
水平或垂直分布房间的问题及解决方法
当需要创建水平或垂直分布的房间时，可能会出现问题。例如，在作者正在开发的游戏中，战斗是水平向的，大部分房间更宽但高度较矮。此时，物理引擎在处理这些长房间的冲突时，可能会导致地牢变得过高，这并非理想状况。
为解决该问题，可以将房间初始分布方式从环形改为带状，以确保地牢具有合适的宽高比例。为了在带状区域内随机分布房间，只需修改 getRandomPointInCircle 函数，将分布点置于椭圆形中。以下是修改后的函数：
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 Triangulation）+图形
将所有选中房间的中心点提取出来，放入三角剖分程序中。你可以自行实现该过程，也可以向有经验的人获取相关资源。作者在开发游戏时，幸运地使用了 Yonaba 实现的该功能。
完成三角剖分后，可以生成一个图形，该图形能提供数据结构或数据库信息。若你之前未进行过此类操作，建议为房间物体或结构设置独特的 ID，以便将这些 ID 添加到图形中，避免重复复制。
最小化生成树（Spanning Tree）
生成最小化生成树
完成图形生成后，需要从图形中生成最小化生成树。同样，你可以自己实现，也可以找使用相同编程语言的有经验的人协助。
最小化生成树的作用及边界添加
最小化生成树能确保地牢中所有主房间都是可达的，并且会改变房间之间的连接方式。这很有用，因为我们既不希望地牢连接过于紧密，也不希望出现不可达的孤岛。同时，我们也不希望地牢只是简单的平行路径，因此需要为剖分图形添加一些边界。
添加边界可以增加更多的路径和循环，使副本地牢更有趣。TKdev 当时添加了 15% 的边界，而作者认为 8 - 10% 是更好的选择，具体比例取决于你期望的副本地牢连接密度。
走廊
生成走廊
最后，需要为地牢添加走廊。具体做法是检查图形中的所有节点，在相邻节点之间创建直线。如果相邻节点排列较为平行，则创建水平线；如果节点垂直，则创建垂直线；如果节点既不相邻也不平行或垂直，则创建两条线形成 L 形状。
作者判断节点是否相邻的标准是：计算两个节点之间的中间点，检查中间点的 X 或 Y 属性是否在节点的边界内。若满足条件，则从该中间点创建直线，但只能在一个轴上进行。
处理非主房间与走廊的冲突
在上图中，可以看到各种情况下的示例，如节点 62 和 47 之间是平行线，60 和 125 之间是垂直线，118 和 119 之间是 L 形线。此外，作者在每条线旁边还额外创建了两条线，以确保其与 tile 尺寸匹配，因为游戏中的战士宽度和高度至少需要 3 个 tiles。
完成上述步骤后，检查非主房间与这些线的冲突情况，将有冲突的房间添加到使用的结构中，它们可作为走廊的轮廓。
完善地图
根据最初设定的房间尺寸和均匀度，此时你应该能得到外观不同的副本地牢。若希望走廊更加统一、外观更自然，可减小偏差，并进行检查，确保房间宽度和高度合适。
最后，只需添加一个 tile 尺寸的网格，补齐缺失部分即可。实际上，无需复杂的网格数据结构，只需根据 tile 尺寸检查每条线，并在列表中记录网格分布位置。
总结
整个流程返回的数据结构包括：
- 一个房间列表，每个房间是带有独特 ID、x/y 位置和宽高比的结构。
- 图形，每个节点对应一个房间 ID。
- 真实的 2D 网格，每个房间为空，可指向主房间、走廊或走廊间。
有了这三个数据结构，你可以生成任何类型的数据，进而确定门、敌人、物品的放置位置，以及哪些房间中有 BOSS 等。