最近几日闲来无事，后来看到了RogueLike的游戏，就像来试一下地牢生成算法。

网上看到了一篇文章写的挺好的。后面会有转载，不急哈。

先看一下我实现的效果图

生成过程：

地牢生成算法的思路是：

1.生成大量随机位置随机大小的房间2.通过物理碰撞将房间分散开3.通过阈值选取主要的房间4.对主房间进行三角剖分运算，得到房间之间的可选路径5.使用最小生成树选定房间之间的路径，并且保留少量回圈6.确定房间路路线7.路上经过的房间划入次要房间中8.绘制房间和路线.

随机生成房间

需要随机生成房间的初始位置，以及房间的长宽高

文章中提供了一种思路，在圆形中随机确定一个点，作为房间的初始位置。

而如何在圆形中随机生成一个点。

圆中生成随机点

先从一个三角形中入手

假设三角形ABC 且|AB| =|AC|。

在AB中找一个点X，在AC中找一个点Y，并用AX和AY做一个平行四边形XAYZ。那么这个随机点Z就找到了。

那万一Z超出了三角形呢

没事，超出了三角形，就将点Z以BC翻折到三角形中。

那我们该怎么运用在圆中呢？

其实这里去了一个极限，将一个圆细分成无数的等腰三角形

这样，我们只要在圆中选择一个三角形，再从三角形中随机选择一个点。

这样就能随机生成一个点了。

现在轮到房间大小了

房间大小可以利用上面的方法，在圆内生成一个点，再用这个点生成一个矩形。

可以有两种生成方法，如下图。

分散房间

这里可以选择使用Unity中自带的Rigidbody分散，

因为Unity的碰撞不好控制，常常跑出来一堆小数，所以我选择自己写一个Rigidbody。

逻辑非常简单，只需要判断自己是否覆盖别人的房间，如果覆盖就移动到没有覆盖。

移动距离计算

假设房间1 和房间2发生碰撞，

对于房间1

Offset= pos1-pos2

如果选择竖直方向的移动

需要判断是向上还是向下

方向:dirY= offsetY>0?1:-1;

距离:dis= y1/2+y2/2– abs(offsetY)

pos1+= vector2.up*dirY*dis

水平方向移动同理。

然后在FixUpdate中调用Simualeting。

筛选主房间

这里没什么好说的了，就是这个筛选房间可以在碰撞之前进行。

还有就是 item.size.Sum();这个是自己写的一个方法。

三角剖分

这里是第一个难点，花了不少时间理解和实现。

三角剖分就是将多个点连起来生成多个三角形，并且三角形之间没有重叠的部分，或者说是线段没有交叉。

就是类似下面的图：

这里实现的是Delaunay三角剖分算法，

我先走一遍流程。

首先生成一个三角形(又称超级三角形)，这个三角形将所有的点都包含进去。

例如：

要实现将所有的点包围起来，我的想法是：

找到x和y的最大值和最小值，生成一个矩形，利用这个矩形生成一个圆形。

最后利用这个圆形生成一个三角形，这个三角形内接刚才生成的圆形。

如图：

将这个超级三角形放入待确认的三角形列表中。

开始遍历三角形列表，

如果当前三角形的外接圆内有点，

选定一个点，将当前三角形拆分成三个边，让这个点和三个边分别连接成三角形，

将这三个三角形放入列表中，并且将当前三角形删除。

如果三角形的外接圆内没有点，那么这个三角形就是Delaunay三角形。

将三角形放入Delaunay三角形列表中。

上面的流程看起来挺正确的，

但似乎忽略了一种情况

按照刚才的算法，会生成下面的情况：

这时候应该怎么办？

不急，先执行另一个三角形看看

执行后多出来了三个三角形，这里用了蓝色的线标记起来。

此时有两个三角形是完全相同，(大小相同，位置相同)

如果将这两个三角形删除，就会得到下面的情况。

这可太美妙了。(当时理解的时候的想法)

下面展示一下伪代码

输入顶点列表

对顶点的x进行排序

生成一个超级三角形，并添加到待确定三角形列表中

遍历顶点

遍历待确定三角形列表

如果该点在三角形外接圆中

将三角形拆分，分成三个边，将三个边添加到缓存区中，将本三角形删除

继续当前循环

如果该点在三角形外接圆的右侧，即该点的x>三角形外接圆最右侧

这时候所有的点都不可能在圆内，

此时将三角形添加到Delaunay三角形列表中

将三角形从待确定三角形中移除。

如果该点不在三角形外接圆右侧，这时候不能确定其他点不在三角形内部

继续当前循环。

查找缓存区中相同的边，

将相同的边根除，即一条边不止出现一次，就将这条边在列表中全部删除。

将顶点和缓存中所有的边组合成三角形。

添加剩下的三角形到delaunay三角形列表中。

算法完成

删除与超级三角形相关的三角形。

输出Delaunay三角形列表。

代码中使用了排序，外接圆右侧是个什么意思

其实是这样的

如果没有点1 和点2 ，这时只有点3和点4 ，遍历顺序是3 4，

判断点3 在圆外时，点4一定也在圆外。

但是如果点1 2 都存在，那么遍历顺序是1 2 3 4

此时点1 在圆外，而点2在却圆内。

这样懂了吧。

至此三角剖分环节结束了，

代码参考(代码是真的仅供参考，因为代码能力比较emmmm)

生成超级三角形

对顶点列表进行排序

遍历顶点列表

遍历三角形列表

如果顶点在三角形外接圆右侧

如果顶点在三角形外部，而不是在右侧

如果顶点在外接圆内部，拆分三角形，将三角形添加缓存区，

如果已经存在缓存区中，添加到待删除的缓存区。

根除重复的边(上面讲的是根除三角形，其实同理)

生成新的三角形，添加到待确认的列表中

最后合并所有的三角形，然后删除超级三角形相关的三角形。

要是觉得讲的不好可以去看一些我当时参考的博客

最小生成树算法

从上面获取的三角形列表，将三角形列表转换成边列表，对边列表进行最小生成树算法，

这里使用的是Kruskal的最小生成树算法

我就直接把算法流程画出来，看的方便

我们先从最小的边开始连接，这时候看边的两端的父亲是否为同一个节点。

如果没有父亲，那自己就是父亲节点。

接下来是第二条边，同样因为父亲节点不相同，所以连接起来

接下来边是1-3这条边，但是节点1和节点3 的父亲是相同，所以不能连接起来。

然后选择2-4这条边，连接起来。

剩下的同理

最小生成树有个性质，树的边数量等于节点数量-1

所以终止的条件是树的边数量等于节点数量-1；

下面是代码：

首先对边的权重进行排序

对边进行遍历

判断边的两个节点的父亲是否是同一个节点

至此最小生成树就结束了

最后我们要随机几条边到生成的路线中。

这里的方法比较简陋，就是随机找几个，然后添加进去。

现在大部分工作已经准备好了，剩下的就是如何讲我们的房间和道路展示出来

绘制房间和道路

这里采用了Unity中Tilemap工具来绘制房间和道路。

按照文章的设想，房间之间的通路是由水平和垂直的路组成的，并不是斜着的路。

如图

但是两个房间的路又存在两条，就像moba类游戏中的上路和下路一样，我们应该选择哪一种

如图：

虽然很不情愿，但是我还是得使用随机来指定路线，

接下来又面临一个问题，房间的出口究竟应该设置在哪里？

如果是中间，这样看起来就不够多样性。那只能选择随机了。没错又是随机，毕竟是随机生成地牢嘛。

我的想法是在图中红色的区域随机生成一个点，作为两个房间道路的拐角点或者是转折点。

代码：

为了方便以后放置门，我们还需要讲房间的出口计算出来

看图可以看出来房间A的出口坐标

DoorA.x = room.x+size.x/2

DoorA.y = Turnpoint.y

看上去很完美，但是如果出现了下面的情况门口就会出现问题。

假设拐角点在房间内，按照上面的计算公式，就会出现下面的情况

为了排除这种情况，有两种做法，

一、禁止转折点在房间内生成，这个也有问题，我不过多解释。

二、删除房间B的出口，将转折点修改为真正的出口

我的选择自然是删除房间B的出口

看图可以看出转折点的位置是

Turnpoint.x = Turnpoint.x

Turnpoint.y = roomb.y+size.y/2;

再将两点返回

最后调整一下每个方向应该的值，微调一下代码(这个微调花了我最多时间)

代码参考

这里稍微解释一下，代码中有很多这样的语句

(dir.x > 0) ? offset - 1 : -offset)

或者

(dir> 0) ? (roomB.size.y / 2) - 1 : -(roomB.size.y / 2)

这些 - 1 都是为了能够在Tilemap中绘制图的时候不会出错

如果我不减1 就会出现

心目中的6*6

现实中画出来的6*6注意：这里指的是如果不 减 1 的情况。

接下来继续上代码

将主房间和次方间，以及道路绘制出来

绘制房间到Tilemap的代码：

绘制道路到Tilemap代码

最后生成效果展示

终于结束了，真的花费了太长的时间，感觉有些不务正业hhh，

当然问题还是有的，比如，大量的射线检测导致的性能问题，还有道路的选择也有写小问题。

由于房间之间的碰撞使用的是组件，所以碰撞的顺序常常不相同，即使设置随机种子，房间的位置也会不相同。

剩下的以后有机会再写，保证不咕咕咕。

最后，我写了一个月才完成了这些代码，不知道大佬们需要花多久。

参考文章：

随机地牢作者的博客：

随机地牢作者的github：

随机地牢的国内翻译：

圆内随机点算法：

三角剖分算法：

最小生成树算法：

其他生成算法(未参考)：