Unity 编写代码，生成随机洞穴（类似蜂巢）（2D、3D地图迷宫），平滑地图块，渲染地图。

参考官网教程：Procedural Cave Generation tutorial

完整Github工程：CaveGeneration

跟着官方教程走了一遍，基本明白如何创建一个随机地图了。主要是算法的问题，如用广度优先获取区域（房间或墙）大小，用深度优先递归查找区域边界，还有计算两点之间经过结点的梯度变化。吐槽一下官方教程，教程中把结构和类全都放一起，不少方法耦合度很高，需要自己就优化了一下。

数据结构

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,是因为含有一层内部房间轮廓，还有最外面一圈矩形。

完整Github工程：CaveGeneration