Unity生成随机房间、洞穴（2D、3D地图）总结
发表于2018-01-04
本篇文章主要介绍在Unity开发中生成随机房间、洞穴的方法，参考了官网教程：Procedural Cave Generation tutorial ，跟着官方教程操作一次，基本就会明白如何创建一个随机地图了。主要是算法的问题，如用广度优先获取区域（房间或墙）大小，用深度优先递归查找区域边界，还有计算两点之间经过结点的梯度变化。但官方教程也有些问题，将结构和类全都放一起，不少方法耦合度较高，所以需要大家自己就优化下。
数据结构
| 结构、类名 | 说明 | 图释 |
|---|---|---|
| Node | 顶点。Vector3 position;// 坐标int vertexIndex;// 索引号 |  |
| ControlNode | 继承于Node，地图位置的基本单位。bool active; //是否有效（True为墙，False为洞）Node above,right; //上结点和右结点 |  |
| Square | 包含八个方位的结点，渲染地图的基本单位。ControlNode topLeft, topRight, bottomRight, bottomLeft; //四个角的点 Node centreTop, centreRight, centreBottom, centreLeft;//四边中点int configuration; //标志位，用于判断四个角哪些是激活状态的 |  |
| SquareGrid | 地图集。如图8 x 8个ControlNode，包含7 x 7个Square（深绿色框框），亮绿色的是不需要用到的结点。Square[,] squares; //包含小于ControlNode一行和一列的Square |  |
| Coord | 包含xy两个坐标。int tileX,tileY; | 略。 |
| Triangle | 三角形。包含三个点的索引值。int vertexIndexA,vertexIndexB,vertexIndexC; | 略。 |
| Room | 房间。成员变量包含所有结点，边界结点们，直接相连的房间们，房间大小（结点个数），是否连接（直接或间接）到主房间，是否是主房间。主要方法：SetAccessibleFromMainRoom() ：如果本身可以连接到主房间，则使其与之相连的其他房间们都设置为可以连接到主房间（传递性）。ConnectRooms(Room roomA, Room roomB) ：连接AB两个房间，并根据房间属性修改相应的值。 | 略。 |
MapGenerator（地图生成器）
1.产生随机的地图结点（RandomFillMap()）。
1.1. 根据给宽高还有填充百分比，随机分配洞或墙结点（就像二维码）。
2.平滑结点们生成房间（SmoothMap()）。
2.1. 遍历每个结点，计算其周围8个结点为墙个数，等于4个时保持不变，大于一半则自己也变成墙，反之为洞。
3.清除小的墙体、空洞（ProcessMap()）。
3.1. 先删掉小墙体，这样有些房间就会变大。
3.2. 删掉小空洞，并且把没删掉的作为房间存起来，最后把房间最大的作为主房间。
3.3. 获取区域的大小时用广度优先的方法来查找（GetRegionTiles(x,y)）。
4.清除后幸存房间相互连接（ConnectClosestRooms(survivingRooms)）。
4.1. 首先依次为每个房间（还没连接过任何房间的）,通过每个房间边界（room.edgeTiles）找到距离最近的房间，并且连接（CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB) //连接距离A最近的房间B，最近的两个点bestTileA和bestTileB）。 但不一定所有房间都能互相连通。
4.2. 将所有房间连通到主房间，分两列，一列是能连通主房间的房间列表，另一列不连通主房间，同样方法，找到两个队列最近的房间和最近的点，相互连接。ConnectClosestRooms(allRooms, true)。
4.3. 通过上面一步还不一定就能连接完所有房间，需要继续递归调用ConnectClosestRooms(allRooms, true)，知道最后找不到需要连接的房间。
5.相互连接时，创建通道（CreatePassage(roomA, roomB, tileA, tileB)）。
5.1. 通过给的tileA和tileB获取一条线段（梯度变化的结点列表）（GetLine(tileA,tileB)），原理很简单，就是先看成直角坐标，计算两个点产生的直线，可以求出线的斜率（梯度），通过斜率可以计算出下一个移动位置。
5.2. 根据算出来的线段（List<Coord>），已经给的通道宽度，给每个线段结点，以通道宽度为半径挖洞（DrawCircle(coord,passageWidth)）。
6.最后给地图加一层墙（外边框），避免有洞出来（CrateStaticBorder()）。
7.最最后就是把做好的地图丢给网格生成器（MeshGenerator），用于渲染还有碰撞检测。
生成一个简单的8x8随机地图。
说明：
1. 黑色：ControlNode.active == true，墙体。
2. 白色：ControlNode.active == false，空洞（房间）。
3. 橙色：ControlNode，一个位置结点，包含上面和右边的蓝色结点。
4. 蓝色：Node，是橙色结点的子节点（ControlNode.above, ControlNode.right）。
5. 绿色：Square，包含四个橙色结点。共7x7个。
MeshGenerator（网格生成器）
1. 首先将每个Square（上图绿色部分）重新绘制（TriangulateSquare(squareGrid.squares[x, y])）成一系列三角形，以便于绘制网格。
1.1. Square有一个成员变量configuration，就是标志位。用于标志周围四个ControlNode的状态（墙还是洞），如下。
一个Square含有8个主要方位结点（如图粉色）。
简化出来，看成一个绿色方框，四个角分别代表四个标志位如下图。
| 实例 | 说明 | 划分三角形顺序（深至浅） |
|---|---|---|
 | 四个角只有左下角是墙。 |  |
 | 四个角下面两个是墙。 |  |
 | 左下角右上角是墙。 |  |
 | 只有左上角是洞。 |  |
 | 四个都是墙。 |  |
1.2. 划分出的三角形放入列表中（连续添加三个顶点索引），还有找到的结点们也放入列表中。需要注意的是，添加三角形顶点时要按顺时针依次添加，渲染原理：左手法则，顺时针后正面面向外部。
2.然后把获得的结点们，和三角形们，添加到Cave.mesh中，就可以产生平滑的地图了（setCaveMesh(map.GetLength(0) * squareSize)）。
2.1. 根据上面8x8的地图，会产生如下图的平滑边框（橙色）。
2.2. 去除自己渲染的Gizmos，就可以看到平滑的地图了。
3. 计算出房间的边缘（CalculateMeshOutlines()），存到List<List<int>> outlines 中，及如果有多个房间独立开来的，那么这个变量意思就是存放每个房间的边缘，而每个边缘含有一系列结点索引。
3.1. 遍历所有所有三角形顶点。通过遍历包含同一顶点的所有三角形（GetConnectedOutlineVertex(vertexIndex)），找到下一个能和其组成单面墙的顶点（其原理就是，判断这条边是否只被一个三角形占有，因为如果一条边同时被两个三角形占有时，说明他两边都是墙。）
3.2. 如果通过上一步成功找到下一个边缘顶点，在添加到边缘列表（outlines）之后，那么根据这个新顶点继续找下一个边缘顶点（FollowOutline(newOutlineVertex, outlines.Count - 1)）。
3.3. 在找下一个顶点时，其实就是递归了（FollowOutline(nextVertexIndex, outlineIndex);），结束条件就是找不到下一个顶点了。
3.4. 找出一条边缘后，要记得加上第一个顶点，使这个边缘线闭合。之后就可以找下一条边缘线了（回到3.1步骤）。
4. 可以添加一条最外边（AddBorderLine()），及整个地图的矩形外轮廓，原理和步骤3一样。
5. 如果是3D场景，则创建边缘有高度的墙网格（CreateWallMesh()）。
5.1. 遍历所有房间的外边缘（outlines），每两个点之间产生一片墙，创建方法如下图。
说明：
白色顶点：上面两个顶点是外边缘连续两个顶点。通过加上高度，产生多两个白色顶点，一共四个白色顶点添加到墙顶点列表（wallVertices）中以用来绘制mesh。
红色，蓝绿色三角形：同之前划分三角形一个意思，用来组成mesh的三角形单位。
6. 如果是2D场景（需要把Cave Mesh和其他相关组件旋转270°（-90°）），则只需画出一条边界碰撞框就好了（Generate2DColliders()）。
6.1. 遍历一遍边缘顶点，转换成2D坐标，加到EdgeCollider2D就好了。
测试地图
1.3D场景
创建一个Player（小球），还有个跟踪相机，丢到场景中。
监视板变量如下。
需要注意的是MeshCollider是单面，如果从背面看，是完全透明的，及如果小球在绿色墙体里面，是可以出来的，但是不能从外面正面穿过MeshCollider。同样，对光线来说其背面也是透明的，所以如果没有最外层的Mesh，光线可以直接穿过墙体。
2.2D场景
同样使用小球和跟踪相机测试。
监视板如下：
注意到下面创建有两个Edge Collider,是因为含有一层内部房间轮廓，还有最外面一圈矩形。