前言
原始资料是油管上的视频教程，链接戳我，播主是南非小哥Sebastian Lague，专门在油管上做Procedural Generation和Unity的相关教程视频。Unity官方也把这个系列加到了推荐教程中。"Procedural Cave Generation"这个系列已经完结，自己跟着后面做了一遍，收获颇多，这里做个整理和翻译，也算帮助自己理解。他还有一个正在连载的系列“Landmass Generation”，动态生成3D Terrain，等完结了也可以考虑做个整理。
这个整理以理解和介绍背景知识为主，会贴部分代码，想看详细代码的可以看他的Github项目主页。部分代码小哥是一笔带过，可能看完你知道怎么做，但为什么这么做理解起来可能有些困难，我也尽量找出相关资料辅助理解，Let's Start!
Cellular automata(细胞自动机)
Cellular Automata最早是冯诺曼依大爷提出的离散数学模型，详细的信息可以参考Wiki，在洞穴生成里面我们只需要借鉴这个模型的三个特点：
- 一个由多个格子Cell组成的N维网格（这里只要用到2维网格）
- 每格Cell状态有限（这里只取两个状态，每格值是0-空地，或者1-墙）
- 网格按照某种规则演变，每格Cell状态变化受周围格子状态的影响而变化
背景知识就介绍这么多，接下来开始一步步实现。
随机生成2维网格
根据上面介绍的Cellular automata第一和第二条规则，在Unity中建立一个脚本"MapGenerator"负责二维网格的实现。
public int width;
public int height;
public string seed;
public bool useRandomSeed;
[Range(0,100)]
public int randomFillPercent;
int[,] map;
width和height为可设置的地图大小。生成地图的规则也很简单，设置一个randomFillPercent值，对每一点进行遍历，随机取值，如果小于randomFillPercent，将该点设置为1，否则设置为0。一般设置randomFillPercent为50左右。
考虑到有时候我们需要能够存储和重新生成相同的地图，所以在初始化网格时并不是完全随机，而是设置一个seed，进行伪随机生成。
void RandomFillMap() {
if (useRandomSeed) {
seed = Time.time.ToString();
}
System.Random pseudoRandom = new System.Random(seed.GetHashCode());
for (int x = 0; x < width; x ++) {
for (int y = 0; y < height; y ++) {
if (x == 0 || x == width-1 || y == 0 || y == height -1) {
map[x,y] = 1; //设置边缘固定为墙
} else {
map[x,y] = (pseudoRandom.Next(0,100) < randomFillPercent)? 1 : 0;
}
}
}
}
首次生成的图可能是这个样子，别着急，接下来根据Cellular Automata的第三个特征处理网格。
应用规则处理网格
Cellular Automata网格的处理规则并不是固定的，比较经典的如Conway's Game of Life生命游戏的规则，不过我们这里处理规则比较简单：
- 统计当前格子Cell周围8个网格状态为1（墙）的总和S
- 如果S大于4，则把Cell设为1。如果S小于4，则把Cell设为0。
- 如果S等于4，则Cell值保持不变。
void SmoothMap() {
for (int x = 0; x < width; x ++) {
for (int y = 0; y < height; y ++) {
int neighbourWallTiles = GetSurroundingWallCount(x,y);
if (neighbourWallTiles > 4)
map[x,y] = 1;
else if (neighbourWallTiles < 4)
map[x,y] = 0;
}
}
}
int GetSurroundingWallCount(int gridX, int gridY) {
int wallCount = 0;
for (int neighbourX = gridX - 1; neighbourX <= gridX + 1; neighbourX ++) {
for (int neighbourY = gridY - 1; neighbourY <= gridY + 1; neighbourY ++) {
if (IsInMapRange(neighbourX, neighbourY)) {
// 统计周围8个点的情况，请参考Moore neighborhood(https://en.wikipedia.org/wiki/Moore_neighborhood)
if (neighbourX != gridX || neighbourY != gridY) {
wallCount += map[neighbourX, neighbourY];
}
}
else {
wallCount ++;
}
}
}
return wallCount;
}
循环上述步骤5次，可以看到地图的变化如下：
如果你对其他处理规则感兴趣，可以查阅下面两个链接：
1.Generate Random Cave Levels Using Cellular Automata
2.Procedural Level Generation in Games using a Cellular Automaton
规则是先设定一个DeathLimit（如3）和BirthLimit（如4）：
- 统计当前Cell周围为1（墙）的值S
- 如果Cell为1（墙），S值小于DeathLimit，则设置Cell为0
- 如果Cell为0（空地），S值大于BirthLimit，则设Cell为1
需要解决的问题
虽然目前可以生成一个卖相不错的地图，但还存留一些问题：
- 地图中依然存在小块的空地集合或墙集合。
- 大块的空地并不确保互相连通。
要解决这两个问题，可以参考下面这篇文章，在生成规则上做一些优化
Cellular Automata Method for Generating Random Cave-Like Levels
也可以参考Procedural Cave Generation这个系列教程里，Sebastian小哥引入的“房间Room”的概念，去除过小的房间，然后对空房间进行连接，这个是part2要讲的部分。
注：原始教程中，讲完本文的内容，Sebastian小哥先去讲了怎么在Unity里生成二维网格的Mesh，然后再回头讲房间连接，这里我先换个顺序，把和网格处理相关的内容一块说了，再把Mesh生成放到最后说。
