在这篇文章中，我将描述一种用于以程序方式生成具有预定结构的二维地牢等级的算法。 在第一部分中，将给出一般性描述，第二部分中，将介绍算法的实现。
引言
该算法是作为
学士学位工作的一部分编写的，基于
Ma et al（2014）的文章 。 这项工作的目的是加速算法并为其添加新功能。 我对结果很满意，因为我们使算法足够快，可以在游戏执行期间使用它。 完成学士学位的工作后，我们决定将其变成
一篇文章 ，并将其发送到Game-ON 2018会议。
演算法
为了创建游戏关卡，该算法接收一组多边形构建块和关卡连通性（关卡拓扑）图作为输入。 图的节点指示房间，边缘确定它们之间的连接。 该算法的目的是为图形的每个节点分配房间的形状和位置，以使两个房间的形状不相交，并且每对相邻的房间都可以通过门连接。
（一）
（b）
（c）
（d）
图（c）和（d）显示了根据输入图（a）和构件块（b）生成的图。
使用连接图，游戏设计者可以轻松地控制游戏流程。 您是否需要一条通向老板间的公共路径，并带有几个可选的旁路径？ 只是从路径图开始，然后指定玩家可以选择的几个节点：沿着主要路径走，或者探索侧路，可能有宝藏和/或怪物等待着它。 您需要切路吗？ 只需选择图中的两个节点，然后添加一条连接它们的短路即可。 该方案的可能性是无限的。
输入图示例。 主路径显示为红色，辅助路径显示为蓝色，短路径显示为橙色。该算法不仅允许游戏设计人员管理生成的地图的高级结构，而且还提供控制单个房间的外观以及如何将它们彼此连接的功能。
不同房间的形状不同
我在关卡末尾提到了老板室。 我们不希望老板房间看起来像其他普通房间，对吧？ 该算法允许您为每个房间设置表格。 例如，我们可以在关卡的开头创建一个房间，并创建一个老板房间，该老板房间应具有自己的一组房间形状，而所有其他房间都应具有一组通用形状。
根据输入图生成两个电路，其中一种特殊形式的房间与房间号8相关联。
明确指示的门位置
想象一下，您有一个高质量的老板会议脚本，并且我们需要玩家从特定的区域进入老板的房间。 或者我们可能有一个房间模板，其中保留了一些瓷砖用于墙壁和其他障碍物。 该算法允许设计人员为各个房间形状明确设置可能的门位置。
但是有时目标可能相反。 我们可以以这样的方式创建房间模板，即通往房间模板的门几乎可以在任何地方。 因此，我们对算法施加的限制更少；因此，它通常运行速度更快，并且生成的电路似乎不太单调且更加有机。 在这种情况下，可以简单地指示门的长度以及门距拐角的距离。 距拐角的距离是所有门的手动布置与任何位置的门之间的一种折衷。
（一）
（b）
图（a）展示了不同类型的门放置-方形房间有8个明确定义的门位置，而矩形房间则使用长度和距角落的距离。 图（b）显示了一个简单的生成图，其中包含图（a）中房间的形状。
房间之间的走廊
当我们谈论地牢的高度时，我们经常会想到房间之间由狭窄的走廊相连。 我想假设输入图上的连接指示了走廊，但没有。 它们只是保证所有相邻节点将通过门直接连接。 如果要通过走廊将房间连接起来，则需要在所有相邻房间对之间插入一个新节点，并假装它们是走廊房间（具有某些形式的房间并具有给定的门位置）。
（一）
（b）
说明如何修改输入图以在房间之间添加走廊。 图（a）显示了添加走廊房间之前的输入图。 图（b）显示了通过（a）在原始图的所有相邻房间之间添加新房间而创建的输入图。
不幸的是，这大大增加了算法的工作量，因为通常节点数会增加一倍。 因此，我实现了考虑走廊的算法版本，可以减少布置走廊房间时性能的下降。 目前，该算法支持所有房间之间的走廊，或者完全不支持走廊，但是将来我计划使其更加灵活。
例子
从不同的构建块集生成的几种方案，并且打开了走廊。从具有不同通道的构建块的不同集合中生成的几种方案。在文章的第二部分，我将讨论算法的内部操作。
我还在研究用于程序地牢生成的Unity插件，该插件将包含此算法。 我这样做是因为尽管有可能直接在Unity中使用此算法（用C＃编写），但使用它的便利性远非理想。 在没有GUI的情况下创建会议室模板需要花费大量时间，并且需要大量代码才能将算法的输出转换为游戏中使用的表示形式。
由于我自己不是游戏开发人员，因此我的目标是使插件足够好以供其他人使用。 如果一切顺利，那么当我有话要说的时候，我将尝试发布更新。 我已经对生成器本身和测试其功能有很多想法。
Unity插件的屏幕截图（该项目正在开发中）第2部分。算法的实现
在这一部分中，我将讨论在帖子的第一部分中描述的算法基础中奠定的基本思想。 最初，我想描述基本概念以及算法足够快所需的主要改进。 但是，事实证明，即使是基本概念，对于这篇文章来说也绰绰有余。 因此，我决定在以后的文章中介绍性能改进。
动机
在继续实施之前，我想展示一下我们将做的结果。 下面的视频显示了从一个输入图和一组构建块生成的30种不同电路。 该算法在生成电路后始终会停止500 ms，然后尝试生成下一个。
如何运作
该算法的目的是将房间的形状和位置分配给图中的每个节点，以便没有两个房间相交，并且相邻的房间通过门连接。
实现此目的的一种方法是尝试房间形状及其位置的所有可能组合。 但是，您可能会猜到，这将非常低效，并且即使基于非常简单的输入图，我们也可能无法生成电路。
该算法代替搜索所有可能的组合，而是计算如何正确连接所有单个房间（所谓的配置空间），并使用此信息指导搜索。 不幸的是，即使有了这些信息，仍然很难找到正确的方案。 因此，为了有效地研究搜索空间，我们使用了概率优化技术（在这种情况下为退火模拟）。 为了进一步加速优化，我们将输入任务分解为更小且更易于解决的子任务。 这是通过将图分成较小的部分（称为链）并随后依次为每个部分创建方案来完成的。
配置空间
对于其中一个固定在一个位置而另一个可以自由移动的一对多边形，配置空间是两个两个多边形不相交且可以通过门连接的自由多边形的位置集合。 使用多边形时，每个配置空间都可以表示为一组可能为空的线，并可以通过简单的几何工具进行计算。
（一）
（b）
空间配置。 图（a）显示了相对于固定L形多边形的自由矩形的配置空间（红线）。 它确定两个块不相交且彼此接触的正方形中心的所有位置。 图（b）显示了移动正方形相对于两个固定矩形的配置空间的交点（黄点）。
以下算法用于计算一个固定块和一个空闲块的配置空间。 我们在移动块上选择一个参考点，并考虑其中的所有位置
，以便在移动多边形使其参考点位于此位置时，可移动块和固定块都相互接触，但不相交。 所有这些点的集合形成了两个块的配置空间（上图（a））。 为了获得相对于两个或多个固定块的移动块的配置空间，需要计算各个配置空间的交集（上图（b））。
该算法以两种方式使用配置空间。 首先，我们没有尝试单个房间的随机位置，而是使用配置空间搜索导致门连接的相邻房间数量最多的位置。 为此，我们需要获取邻居的配置空间的最大非空交集。 其次，我们使用配置空间来检查是否所有相邻房间对都可以与门相连。 这是通过检查房间的位置是否在其所有邻居的配置空间内来完成的。
由于房间的形状在游戏执行期间不会改变，因此我们可以在算法开始之前预先计算所有成对的房间形状的配置空间。 因此，整个算法得到了显着加速。
增量方案
解决复杂问题时，一种可能的方法是将其分为更小和更简单的子任务，并已经解决了。 这正是我们将要放置单个房间的任务。 与其一次安排所有房间，不如将输入图分成较小的子图，然后尝试一一对应地从中创建图。 原始算法的作者称这些子图为“链”是因为这些图的原理，其中每个节点最多具有两个邻居，因此创建它们的方案非常简单。
最终的输出电路始终是一个连接的组件，因此将各个组件连接到电路中然后尝试对其进行组合是没有意义的，因为组合的过程可能非常复杂。 因此，放置链后，下一个连接的链将始终是已连接到电路中已对齐的顶点的链。
Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; }
伪代码显示了找到正确方案的一种增量方法。上面显示的伪代码演示了增量方案的实现。 在算法的每次迭代中（第6-18行），我们首先从堆栈中取出最后一个电路（第7行），然后计算下一个要添加的链（第8行）。 这可以通过简单地存储添加到每个部分电路的最后一个电路的编号来完成。 下一步，我们将以下链添加到电路（第9行），生成几个详细的电路，并保存它们。 如果扩展阶段失败，但是没有新的部分方案添加到堆栈中，并且算法需要继续使用最后保存的部分方案。 我们将这种情况称为返回搜索，因为该算法无法扩展当前的部分方案，必须返回并继续另一个已保存的方案。 当没有足够的空间将附加电路连接到电路中已经组成的顶点时，通常这是必需的。 同样，返回搜索是我们始终尝试生成几种高级方案的原因（第9行）。 否则，我们将一无所有。 当我们生成完整的电路或堆栈为空时，该过程结束。
（a）输入图
（b）局部图
（c）局部图
（d）概述
（e）完整的大纲
增量方案。 图（b）和（c）显示了在规划第一个电路之后的两个局部示意图。 图（d）示出了第二电路扩展（b）之后的完整电路。 图（e）示出了第二电路扩展（c）之后的完整电路。
要将图分成几部分，您需要找到输入图的平面嵌入，即，平面上的图形，其中边仅在端点处相交。 然后使用该附件获取图形的所有面。 分解的主要思想是从循环创建电路更加困难，因为它们的节点有更多的限制。 因此，我们试图将循环安排在分解开始时，以便尽早处理它们，并减少在后续阶段中需要返回的可能性。 第一条分解链由附件的最小面形成，然后按广度优先搜索顺序添加后续面。 如果可以选择其他面，则使用最小的面。 当没有剩余面时，将添加其余的非循环分量。 图4显示了根据这些步骤获得的链中分解的示例。
（一）
（b）
分解成链。 图（b）显示了如何在电路上布置图（a）的示例。 每种颜色代表一个单独的链。 数字表示链创建的顺序。
（c）良好的局部设计
（d）概述
（a）输入图
（b）错误的局部图
搜索返回。 图（b）显示了一个不良的局部电路的示例，因为其中没有足够的空间来连接节点0和9。要生成完整的电路（d），必须返回到另一个局部电路（c）。
模拟退火
退火模拟算法是一种概率优化技术，其目的是研究可能电路的空间。 它是由原始文章的作者选择的，因为事实证明它在过去的类似情况下很有用。 在实现该算法时，我决定使用相同的方法，因为我想从已经证明其解决此问题有效性的方法开始。 但是，我认为可以用另一种方法替换它，并且编写我的库的方式使得替换该方法的过程非常简单。
退火模拟算法可迭代地评估当前配置或电路中的细微变化。 这意味着我们通过随机选择一个节点并更改其位置或形状来创建新配置。 如果新配置改善了能量功能，则始终可以接受。 否则，几乎没有机会接受配置。 随着时间的流逝，做出更差决策的可能性降低。 能量函数的设计方式是对相交的节点和不互相接触的相邻节点施加较大的罚款。
A是图中所有块对之间的总相交面积。 D是输入图中相邻但彼此不接触的一对块对的中心之间的距离的平方和。 价值
影响模拟退火被允许进入最差配置的可能性； 此参数是根据构建块的平均面积计算得出的。
选择要更改的节点后，我们更改其形状或位置。 我们如何选择新职位？ 您可以随机选择它，但这通常会降低能量函数，并且算法收敛速度非常慢。 我们可以选择一个更有可能增加能量功能的位置吗？ 看到我要去什么？ 我们使用配置空间来选择一个位置，该位置满足最大数量的相邻房间的限制。
然后，要更改形状，只需选择可用的房间形状之一。 虽然算法不会尝试确定哪种形式最有可能导致我们找到正确的方案。 但是，尝试此功能并查看它是否可以加快算法的速度将很有趣。
List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if () { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if () { currentLayout = newLayout; } else if () { currentLayout = newLayout; } } } return generatedLayouts; }
这是负责通过模拟退火创建独立电路的方法的伪代码。
为了加快整个过程，我们将尝试查找初始的低能耗配置。 为此，我们将从与该方案中已包含的节点相邻的节点开始，对当前链中的节点进行宽度优先搜索。 然后，将有序节点一次放置一个，并从配置空间中选择能量最低的位置。 在这里，我们不做任何回溯-这是一个简单的贪婪过程。
奖励视频
下面的视频显示了从与第一个视频相同的输入图生成的图表。 但是，这次显示了一种增量方法。 您可能会注意到，该算法一次添加一个节点链。 还可以看出，有时存在两个连续的具有相同数量节点的部分电路。 当算法返回时会发生这种情况。 如果第一个尝试将另一个电路添加到第一个子电路失败，则算法尝试另一个子电路。
可下载资料
.NET上的算法实现可以在
我的github中找到。 该存储库包含.NET DLL和WinForms GUI应用程序，这些应用程序由YAML配置文件控制。