程序生成地下城洞穴(2)

在上一篇教程的最后，我們可以得到類似下面一張地下城圖：

proc2_1.png

存在兩個(gè)問題，一個(gè)是存在一些零星的獨(dú)立區(qū)域，一個(gè)是有些大區(qū)域互不相連。要解決這兩個(gè)問題，要先引入區(qū)域Region的概念，把每個(gè)獨(dú)立的區(qū)域（包括墻和空白區(qū)域）看做一個(gè)Region，然后針對(duì)這些Region進(jìn)行處理。

用Flood Fill方法獲取屬于同一Region的格子Grid

先建立一個(gè)struct Coord 來抽象格子，里面只有兩個(gè)屬性，X坐標(biāo)和Y坐標(biāo)。

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，簡單來說，就是遞歸查找格子的上下左右四個(gè)相鄰格子，直到所有相鄰格子的類型（0表示空地，1表示墻）不同。

proc2_7.gif

考慮到遞歸方法雖然容易理解，但會(huì)大量占用function stack，在對(duì)程序效率要求比較高時(shí)還是盡量采取非遞歸的函數(shù)實(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;
}

從一個(gè)起始點(diǎn)(startX, startY)開始，用一個(gè)queue(First In First Out)儲(chǔ)存屬于同一type的周邊格子，然后每次加入到返回結(jié)果列表tiles時(shí)再次檢查周邊格子，實(shí)現(xiàn)Flood Fill的遞歸。mapTag數(shù)組用來防止重復(fù)檢查。

有了這個(gè)方法，我們就可以獲取到各個(gè)Region，以及各個(gè)Region所包含的所有Coord坐標(biāo)信息。

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

設(shè)定一個(gè)thresholdSize值，在獲取所有wallRegions和roomRegions時(shí)，如果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ī)整了許多：


去除過小region后的地下城

連接房間roomRegions

Flood Fill
獲得的各個(gè)Room列表roomRegions

既然獲取到了所有房間的列表，接下來就是要遵循一定規(guī)則把所有房間連接起來：

  1. 所有房間與距離最接近的房間相連。
  2. 確保所有房間互相連接，不會(huì)出現(xiàn)獨(dú)立的房間。

新建一個(gè)Room類，用來抽象房間，里面屬性包含：

  • List<Coord> tiles，Room包含的所有點(diǎn)的坐標(biāo)
  • List<Coord> edgeTiles，所有Room內(nèi)邊緣的點(diǎn)，即left，up，right，down四周有一個(gè)點(diǎn)是墻
  • List<Room> connectedRooms，所有已連接的Room索引

在構(gòu)造函數(shù)中，計(jì)算出edgeTiles，后面會(huì)用它來計(jì)算兩個(gè)房間之間的最短連接路線。

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);
                    }
                }
            }
        }
    }
}

另外加入兩個(gè)方法ConnectRooms(Room a, Room b)和IsConnected(Room other)來把已連接的Room添加到connectedRooms里和檢測是否已連接到當(dāng)前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)造一個(gè)函數(shù)ConnectClosestRooms(List<Room> allRooms)，Input是所有Room的List，然后用Unity里面Debug.DrawLine方法先畫出Room間的連接路徑。思路是：

  1. 遍歷allRooms，獲取roomA，其他所有Room集合稱為roomBList。
  2. 遍歷roomBList，獲取roomB。
  3. 遍歷roomA的邊緣edgeTiles和roomB的邊緣edgeTiles，算出最小距離distanceBetweenRooms和兩邊的邊緣點(diǎn)tileA和tileB。
  4. 重復(fù)步驟2的遍歷，直到找到最小的distanceBetweenRooms和對(duì)應(yīng)的tileA，tileB。
  5. 連接tileA和tileB。
  6. 重復(fù)步驟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);
        }
    }
}

加入運(yùn)行后在Scene窗口可以看到如下圖的路徑被創(chuàng)建：


并沒有完全連接的Room

等等，似乎有哪里不對(duì)！為什么少了一條路徑，難道是前面的ConnectClosestRooms方法實(shí)現(xiàn)思路有問題？

的確，再想想的話，會(huì)發(fā)現(xiàn)前面的思路可以滿足條件1： 所有房間與距離最接近的房間相連，但無法確保滿足條件2：不會(huì)出現(xiàn)獨(dú)立的房間。在上面實(shí)現(xiàn)的基礎(chǔ)上，我們需要引入一個(gè)新概念：主房間MainRoom。

主房間就是所有房間中面積最大的房間，在ConnectClosestRooms處理過后，按照下面流程再做一次處理：

  1. 在建立roomRegions時(shí)，選出面積最大的房間mainRoom。
  2. 設(shè)定所有與主房間連接的房間為connectedRooms，所有未和主房間連接的房間為otherRooms。
  3. 遍歷otherRooms和connectedRooms的邊緣tiles，找出一條最短連接路線和兩個(gè)頂點(diǎn)tileA和tileB。
  4. 連接tileA和tileB，把剛連接的Room加入connectedRooms。
  5. 重復(fù)步驟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的處理流程：

  1. 用Flood Fill方法選出房間集合和墻區(qū)域的集合。
  2. 設(shè)定閾值，清除過小的墻和房間。
  3. 獲取房間列表，兩兩連接最接近房間。
  4. 獲取主房間，確保所有房間都連接到主房間。

處理好了路徑，接下來的工作就是處理map數(shù)組，把路徑描繪出來，這個(gè)涉及到一些新的概念，可以下一章單獨(dú)聊。

本篇內(nèi)容包含Procedural Cave Generation系列視頻教程的第5章，第6章和第7章

源代碼可參考SebLague小哥的Github，戳我直達(dá)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容