在上一篇教程的最后，我们可以得到类似下面一张地下城图：
存在两个问题，一个是存在一些零星的独立区域，一个是有些大区域互不相连。要解决这两个问题，要先引入区域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表示墙）不同。
考虑到递归方法虽然容易理解，但会大量占用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;
}
}
}
加入这步处理，可以看到上面的地下城图又规整了许多：
连接房间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窗口可以看到如下图的路径被创建：
等等，似乎有哪里不对！为什么少了一条路径，难道是前面的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，戳我直达
