在上一篇教程的最后，我們可以得到類似下面一張地下城圖：
存在兩個問題，一個是存在一些零星的獨立區(qū)域宗收，一個是有些大區(qū)域互不相連。要解決這兩個問題亚兄，要先引入區(qū)域Region的概念混稽，把每個獨立的區(qū)域（包括墻和空白區(qū)域）看做一個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內(nèi)的Coord洽洁，簡單來說，就是遞歸查找格子的上下左右四個相鄰格子菲嘴，直到所有相鄰格子的類型（0表示空地饿自，1表示墻）不同汰翠。
考慮到遞歸方法雖然容易理解，但會大量占用function stack昭雌，在對程序效率要求比較高時還是盡量采取非遞歸的函數(shù)實現(xiàn)复唤。
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的周邊格子烛卧，然后每次加入到返回結(jié)果列表tiles時再次檢查周邊格子佛纫，實現(xiàn)Flood Fill的遞歸。mapTag數(shù)組用來防止重復檢查总放。
有了這個方法呈宇，我們就可以獲取到各個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型豁，則返回所有空白區(qū)域列表，即所有的房間roomRegions尚蝌。
去除小型Region
設定一個thresholdSize值迎变，在獲取所有wallRegions和roomRegions時，如果Region包含的格子數(shù)量小于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;
}
}
}
加入這步處理，可以看到上面的地下城圖又規(guī)整了許多：
連接房間roomRegions
既然獲取到了所有房間的列表姿鸿，接下來就是要遵循一定規(guī)則把所有房間連接起來：
- 所有房間與距離最接近的房間相連谆吴。
- 確保所有房間互相連接，不會出現(xiàn)獨立的房間苛预。
新建一個Room類句狼，用來抽象房間，里面屬性包含：
-
List<Coord> tiles热某，Room包含的所有點的坐標 -
List<Coord> edgeTiles腻菇，所有Room內(nèi)邊緣的點，即left昔馋，up筹吐，right，down四周有一個點是墻 -
List<Room> connectedRooms秘遏，所有已連接的Room索引
在構(gòu)造函數(shù)中丘薛，計算出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);
}
下面開始構(gòu)造一個函數(shù)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昌妹。
程序?qū)崿F(xiàn)如下：
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窗口可以看到如下圖的路徑被創(chuàng)建：
等等，似乎有哪里不對握截！為什么少了一條路徑飞崖，難道是前面的ConnectClosestRooms方法實現(xiàn)思路有問題？
的確谨胞，再想想的話固歪，會發(fā)現(xiàn)前面的思路可以滿足條件1： 所有房間與距離最接近的房間相連，但無法確保滿足條件2：不會出現(xiàn)獨立的房間胯努。在上面實現(xiàn)的基礎上牢裳，我們需要引入一個新概念：主房間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);
}
}
}
加入了上面的處理独郎，最終結(jié)果如下圖所示：
結(jié)尾
總結(jié)下Room的處理流程：
- 用Flood Fill方法選出房間集合和墻區(qū)域的集合枚赡。
- 設定閾值，清除過小的墻和房間谓谦。
- 獲取房間列表贫橙，兩兩連接最接近房間。
- 獲取主房間反粥，確保所有房間都連接到主房間卢肃。
處理好了路徑，接下來的工作就是處理map數(shù)組才顿，把路徑描繪出來莫湘，這個涉及到一些新的概念，可以下一章單獨聊郑气。
本篇內(nèi)容包含Procedural Cave Generation系列視頻教程的第5章幅垮，第6章和第7章
源代碼可參考SebLague小哥的Github，戳我直達
