程序生成地下城(1) #整理 #翻译 #Unity

前言

原始资料是油管上的视频教程，链接戳我，播主是南非小哥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次，可以看到地图的变化如下：可以看到整个网格变得越来越聚拢规整如果你对其他处理规则感兴趣，可以查阅下面两个链接：