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

在上一篇教程的最后，我们可以得到类似下面一张地下城图：

存在两个问题，一个是存在一些零星的独立区域，一个是有些大区域互不相连。要解决这两个问题，要先引入区域Region的概念，把每个独立的区域（包括墙和空白区域）看做一个Region，然后针对这些Region进行处理。

用Flood Fill方法获取属于同一Region的格子Grid

先建立一个struct Coord 来抽象格子，里面只有两个属性，X坐标和Y坐标。

struct Coord {
    public int tileX;
    public int tileY;

    public Coord(int x, int y) {
        tileX = x;
        tileY = y;
    }
}

用Flood Fill（可参考Wiki）方式来寻找同一Region内的Coord，简单来说，就是递归查找格子的上下左右四个相邻格子，直到所有相邻格子的类型（0表示空地，1表示墙）不同。 4方向的Flood Fill动态示意

考虑到递归方法虽然容易理解，但会大量占用function stack，在对程序效率要求比较高时还是尽量采取非递归的函数实现。

List<Coord> GetRegionTiles(int startX, int startY) {
    // List to store region tile
    List<Coord> tiles = new List<Coord>();
    // Checked(1) or not(0)
    int[,] mapTag = new int[width, height];
    // Start tile filled or empty
    int tileType = map[startX, startY];

    Queue<Coord> queue = new Queue<Coord>();
    queue.Enqueue(new Coord(startX, startY));
    mapTag[startX, startY] = 1;

    while (queue.Count > 0) {
        Coord tile = queue.Dequeue();
        tiles.Add(tile);
        // Check tile's surrounding tiles
        for (int x = tile.tileX - 1; x <= tile.tileX + 1; x++) {
            for (int y = tile.tileY - 1; y <= tile.tileY + 1; y++) {
                // (x == tile.tileX || y == tile.tileY) just to check four neighbour tiles: up, left, right, down
                if (IsInMapRange(x, y) && (x == tile.tileX || y == tile.tileY)) {
                    if (mapTag[x, y] == 0 && tileType == map[x, y]) {
                        queue.Enqueue(new Coord(x, y));
                        mapTag[x, y] = 1;
                    }
                }
            }
        }
    }

    return tiles;
}

从一个起始点(startX, startY)开始，用一个queue(First In First Out)储存属于同一type的周边格子，然后每次加入到返回结果列表tiles时再次检查周边格子，实现Flood Fill的递归。mapTag数组用来防止重复检查。

有了这个方法，我们就可以获取到各个Region，以及各个Region所包含的所有Coord坐标信息。

List<List<Coord>> GetRegions(int tileType) {
    List<List<Coord>> regions = new List<List<Coord>>();
    // 0 unchecked, 1 checked
    int[,] mapTag = new int[width, height];

    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            if (mapTag[x, y] == 0 && map[x, y] == tileType) {
                List<Coord> region = GetRegionTiles(x, y);
                regions.Add(region);
                // Set all tiles to checked
                foreach (Coord tile in region) {
                    mapTag[tile.tileX, tile.tileY] = 1;
                }
            }
        }
    }

    return regions;
}

传入的tileType表示我们要查找的Region属性，如果传入1，则返回所有表示墙的Region列表wallRegions，如果传入0，则返回所有空白区域列表，即所有的房间roomRegions。

去除小型Region

设定一个thresholdSize值，在获取所有wallRegions和roomRegions时，如果Region包含的格子数量小于thresholdSize，则消除或填充该Region。

List<List<Coord>> wallRegions = GetRegions(1);
int wallThresholdSize = 50;
foreach (List<Coord> wallRegion in wallRegions) {
    if (wallRegion.Count < wallThresholdSize) {
        foreach (Coord tile in wallRegion) {
            // Set all tiny wall region to empty tile
            map[tile.tileX, tile.tileY] = 0;
        }
    }
}

// Get empty rooms
List<List<Coord>> roomRegions = GetRegions(0);
int roomThresholdSize = 50;
foreach (List<Coord> roomRegion in roomRegions) {
    if (roomRegion.Count < roomThresholdSize) {
        foreach (Coord tile in roomRegion) {
            // Set all tiny room to filled tile
            map[tile.tileX, tile.tileY] = 1;
        }
    }
}

加入这步处理，可以看到上面的地下城图又规整了许多：去除过小region后的地下城

连接房间roomRegions

Flood Fill 获得的各个Room列表roomRegions

既然获取到了所有房间的列表，接下来就是要遵循一定规则把所有房间连接起来：

所有房间与距离最接近的房间相连。
确保所有房间互相连接，不会出现独立的房间。

新建一个Room类，用来抽象房间，里面属性包含：

List<Coord> tiles，Room包含的所有点的坐标
List<Coord> edgeTiles，所有Room内边缘的点，即left，up，right，down四周有一个点是墙
List<Room> connectedRooms，所有已连接的Room索引

在构造函数中，计算出edgeTiles，后面会用它来计算两个房间之间的最短连接路线。

public Room(List<Coord> roomTiles, int[,] map) {
    tiles = roomTiles;
    roomSize = tiles.Count;
    connectedRooms = new List<Room>();

    edgeTiles = new List<Coord>();
    foreach (Coord tile in tiles) {
        for (int x = tile.tileX-1; x <= tile.tileX+1; x++) {
            for (int y = tile.tileY-1; y <= tile.tileY+1; y++) {
                if (x == tile.tileX || y == tile.tileY) {
                    if (map[x,y] == 1) {
                        edgeTiles.Add(tile);
                    }
                }
            }
        }
    }
}

另外加入两个方法ConnectRooms(Room a, Room b)和IsConnected(Room other)来把已连接的Room添加到connectedRooms里和检测是否已连接到当前Room。

public static void ConnectRooms(Room roomA, Room roomB) {
    roomA.connectedRooms.Add (roomB);
    roomB.connectedRooms.Add (roomA);
}

public bool IsConnected(Room otherRoom) {
    return connectedRooms.Contains(otherRoom);
}

下面开始构造一个函数ConnectClosestRooms(List<Room> allRooms)，Input是所有Room的List，然后用Unity里面Debug.DrawLine方法先画出Room间的连接路径。思路是：

遍历allRooms，获取roomA，其他所有Room集合称为roomBList。
遍历roomBList，获取roomB。
遍历roomA的边缘edgeTiles和roomB的边缘edgeTiles，算出最小距离distanceBetweenRooms和两边的边缘点tileA和tileB。
重复步骤2的遍历，直到找到最小的distanceBetweenRooms和对应的tileA，tileB。
连接tileA和tileB。
重复步骤1。

程序实现如下：

void ConnectClosestRooms(List<Room> allRooms) {
    int bestDistance = 0;
    Coord bestTileA = new Coord();
    Coord bestTileB = new Coord();
    Room bestRoomA = new Room();
    Room bestRoomB = new Room();
    bool possibleConnectionFound = false;

    foreach (Room roomA in allRooms) {
        possibleConnectionFound = false;

        foreach (Room roomB in allRooms) {
            if (roomA == roomB) {
                continue;
            }

            if (roomA.isConnected(roomB)) {
                possibleConnectionFound = false;
                break;
            }

            for (int tileIndexA = 0; tileIndexA < roomA.edgeTiles.Count; tileIndexA++) {
                for (int tileIndexB = 0; tileIndexB < roomB.edgeTiles.Count; tileIndexB++) {
                    Coord tileA = roomA.edgeTiles[tileIndexA];
                    Coord tileB = roomB.edgeTiles[tileIndexB];
                    int distanceBetweenRooms = (int)(Mathf.Pow(tileA.tileX - tileB.tileX, 2) + Mathf.Pow(tileA.tileY - tileB.tileY, 2));
                    if (distanceBetweenRooms < bestDistance || !possibleConnectionFound) {
                        bestDistance = distanceBetweenRooms;
                        possibleConnectionFound = true;
                        bestTileA = tileA;
                        bestTileB = tileB;
                        bestRoomA = roomA;
                        bestRoomB = roomB;
                    }
                }
            }
        }

        if (possibleConnectionFound) {
            CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
        }
    }
}

加入运行后在Scene窗口可以看到如下图的路径被创建：并没有完全连接的Room

等等，似乎有哪里不对！为什么少了一条路径，难道是前面的ConnectClosestRooms方法实现思路有问题？

的确，再想想的话，会发现前面的思路可以满足条件1：所有房间与距离最接近的房间相连，但无法确保满足条件2：不会出现独立的房间。在上面实现的基础上，我们需要引入一个新概念：主房间MainRoom。

主房间就是所有房间中面积最大的房间，在ConnectClosestRooms处理过后，按照下面流程再做一次处理：

在建立roomRegions时，选出面积最大的房间mainRoom。
设定所有与主房间连接的房间为connectedRooms，所有未和主房间连接的房间为otherRooms。
遍历otherRooms和connectedRooms的边缘tiles，找出一条最短连接路线和两个顶点tileA和tileB。
连接tileA和tileB，把刚连接的Room加入connectedRooms。
重复步骤2，直到所有房间都和mainRoom相连。

void ConnectClosestRooms(List<Room> allRooms) {
    int bestDistance = 0;
    Coord bestTileA = new Coord();
    Coord bestTileB = new Coord();
    Room bestRoomA = new Room();
    Room bestRoomB = new Room();
    bool possibleConnectionFound = false;

    foreach (Room roomA in allRooms) {
        possibleConnectionFound = false;

        foreach (Room roomB in allRooms) {
            if (roomA == roomB) {
                continue;
            }

            if (roomA.isConnected(roomB)) {
                possibleConnectionFound = false;
                break;
            }

            for (int tileIndexA = 0; tileIndexA < roomA.edgeTiles.Count; tileIndexA++) {
                for (int tileIndexB = 0; tileIndexB < roomB.edgeTiles.Count; tileIndexB++) {
                    Coord tileA = roomA.edgeTiles[tileIndexA];
                    Coord tileB = roomB.edgeTiles[tileIndexB];
                    int distanceBetweenRooms = (int)(Mathf.Pow(tileA.tileX - tileB.tileX, 2) + Mathf.Pow(tileA.tileY - tileB.tileY, 2));
                    if (distanceBetweenRooms < bestDistance || !possibleConnectionFound) {
                        bestDistance = distanceBetweenRooms;
                        possibleConnectionFound = true;
                        bestTileA = tileA;
                        bestTileB = tileB;
                        bestRoomA = roomA;
                        bestRoomB = roomB;
                    }
                }
            }
        }

        if (possibleConnectionFound) {
            CreatePassage(bestRoomA, bestRoomB, bestTileA, bestTileB);
        }
    }
}

加入了上面的处理，最终结果如下图所示：所有房间通过连接到主房间，确保房间贯通

结尾

总结下Room的处理流程：

用Flood Fill方法选出房间集合和墙区域的集合。
设定阈值，清除过小的墙和房间。
获取房间列表，两两连接最接近房间。
获取主房间，确保所有房间都连接到主房间。

处理好了路径，接下来的工作就是处理map数组，把路径描绘出来，这个涉及到一些新的概念，可以下一章单独聊。

本篇内容包含Procedural Cave Generation系列视频教程的第5章，第6章和第7章

源代码可参考SebLague小哥的Github，戳我直达

Gamer Cat

偶尔码字和写代码，大部分时间都在睡觉😪和玩PS4的懒猫

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

用Flood Fill方法获取属于同一Region的格子Grid

去除小型Region

连接房间roomRegions

结尾