摘要：原文鏈接最近在知乎上看到一個問題，隨機生成指定面積單連通區域，感覺還挺有意思的，于是整理一下寫一篇新文章。問題闡述如下圖所示，在的區域中，隨機生成面積為的單連通區域，該隨機包括位置隨機以及形狀隨機。

原文鏈接：https://xcoder.in/2018/04/01/random-connected-area/

最近在知乎上看到一個問題，「隨機生成指定面積單連通區域？」，感覺還挺有意思的，于是整理一下寫一篇新文章。

如下圖所示，在 10x10 的區域中，隨機生成面積為 6 的單連通區域，該「隨機」包括「位置隨機」以及「形狀隨機」。

注意：

單連通區域定義是該區域每一個區塊上下左右至少連著另一個區塊；

采用周期性結構，超出右邊移到最左邊，以此類推。

其中點 2 可以分采用和不采用周期性結構分別討論。

這個問題，我不知道原題提問者想要做什么事。但是就這題本身而言，我們可以拿它去生成一個隨機地圖，例如：

建造、等待的沙盒類手游，游戲中有一個空島，玩家能在上面建造自己的建筑然后等待各種事件完成。空島形狀隨機生成，并且都聯通且面積一定，這樣每個玩家進去的時候就能得到不同地形。

在得知了問題原題之后，我們就可以照著題目的意思開始解決了。

其實這么一個問題一出現，腦子里面就瞬間涌出幾個詞匯：DFS、Flood fill、并查集等等。

那么其實這最粗暴的辦法相當于你假想有一個連通區域，然后你去 Flood fill 它——至于墻在哪，在遞歸的每一個節點的時候隨機一下搜索方向的順序就可以了。

我們先實現一個類的框架吧（我是 Node.js 開發者，自然用 JavaScript 進行 Demo 的輸出）。

const INIT = Symbol("init");

class Filler {
    /**
     * Filler 構造函數
     * @constructor
     * @param {Number} length 地圖總寬高
     * @param {Number} needArea 需要填充的區域面積
     */
    constructor(length, needArea) {
        this.length = length;
        this.needArea = needArea;
    }

    /**
     * 初始化地圖
     */
    [INIT]() {
        /**
         * 為了方便，地圖就用一個二維字符數組表示
         *
         *   + . 代表空地
         *   + x 代表填充
         */
        this.map = [];
        this.count = 0;
        for(let i = 0; i < this.length; i++) {
            let row = [];
            for (let j = 0; j < this.length; j++) row.push(".");
            this.map.push(row);
        }
     }

     /**
      * 填充遞歸函數
      * @param {Number} x 坐標 X 軸的值
      * @param {Number} y 坐標 Y 軸的值
      * @return 填充好的地圖二維數組
      */
     fill(x, y) {
        // 待實現
     }
}

有了架子之后，我們就可以實現遞歸函數 fill 了，整理一下流程如下：

隨機一個起點位置，并以此開始遞歸搜索；

fill(x, y) 進入遞歸搜索：

如果需要初始化地圖就調用 this[INIT]()；

this.count++，表示填充區域面積加了 1，并在數組中將該位置填充為 x；

this.count 是否等于所需要的面積：

若等于，則返回當前的地圖狀態；

若不等于，則繼續 2.4；

隨機四個方向的順序；

對四個方向進行循環：

x、y 軸的值按當前方向走一個算出新的坐標值 newX 和 newY；

判斷坐標是否合法（越界算非法）：

若非法則回 2.5 繼續下一個方向；

若合法則繼續 2.5.3；

遞歸 fill(newX, newY) 得到結果，若有結果則返回；

若循環完四個方向都還沒返回結果則會跳到這一步來，這個時候進行狀態還原，遞歸跳回上一層進行下一個狀態的搜索。

在這里「狀態還原」表示把 this.count-- 還原回當前坐標填充前的狀態，并且把當前填充的 "x" 給還原回 "."。

照著上面的流程很快就能得出代碼結論：

const _ = require("lodash");

class Filler {
    ...

    fill(x, y) {
        // 初始化地圖
        const needInit = !arguments[2];
        if(needInit) this[INIT]();

        // 如果當前坐標已被填充，則返回空
        if(this.map[x][y] === "x") return;

        // 填充當前坐標
        this.count++;
        this.map[x][y] = "x";

        // 填充滿了則返回當前地圖
        if(this.count === this.needArea) return Object.assign([], this.map);

        // 隨機四個方向的順序
        const dirs = _.shuffle([ [ 0, 1 ], [ 0, -1 ], [ 1, 0 ], [ -1, 0 ] ]);

        // 循環四個方向
        for(let i = 0; i < 4; i++) {
            const dir = dirs[i];
            let newX = x + dir[0];
            let newY = y + dir[1];

            // 判斷邊界
            {
                if(newX < 0 || newX >= this.length || newY < 0 || newY >= this.length) continue;
            }

            // 進入下一層遞歸并得到結果
            const ret = this.fill(newX, newY, true);

            // 若結果非空則返回結果
            if(ret) return ret;
        }

        // 狀態還原
        this.count--;
        this.map[x][y] = ".";
    }
}

這么一來，類就寫好了。接下去我們只要實現一些交互的代碼，就可以看效果了。

點我進入 JSFiddle 看效果。

如果懶得進入 JSFiddle 看，也可以看看下面的幾個截圖：

10x10 填 50 效果圖

10x10 填 6 效果圖

50x50 填 50 效果圖

其實原題說了一個條件，那就是采用周期性結構，超出右邊移到最左邊，以此類推。

而我們前文的代碼其實是照著非周期性結構來實現的。不過如果我們要將其改成周期性實現也很簡單，只需要把前文代碼中邊界判斷的那一句代碼改為周期性計算的代碼即可，也就是說要把這段代碼：

// 判斷邊界
{
    if(newX < 0 || newX >= this.length || newY < 0 || newY >= this.length) continue;
}

改為：

// 周期性計算
{
    if(newX < 0) newX = this.length - 1;
    if(newX >= this.length) newX = 0;
    if(newY < 0) newY = this.length - 1;
    if(newY >= this.length) newY = 0;
}

這個時候出來的效果就是這樣的了：

10x10 填 50 周期性效果圖

至此為止 DFS 的代碼基本上完成了。不過目前來說，當然這個算法的一個缺陷就是，當需要面積與總面積比例比較大的時候，有可能陷入搜索的死循環（或者說效率特別低），因為要不斷復盤。

所以我們可以做點改造——由于我們不是真的為了搜索到某個狀態，而只是為了填充我們的小點點，那么 DFS 中比較經典的「狀態還原」就不需要了，也就是說：

this.count--;
this.mat[x][y] = ".";

這兩行代碼可以刪掉了，用刪掉上面兩行代碼的代碼跑一下，我用 50x50 填充 800 格子的效果：

繼續之前的 50x50 填充 50：

上面 DFS 的方法，由于每次都要走完一條路，雖然會轉彎導致黏連，但在填充區域很小的情況下，很容易生成“瘦瘦的區域”。

這里再給出另一個方法，一個 for 搞定的，思路如下：

先隨機一個起始點，并將該點加入邊界池；

循環 N - 1 次（N 為所需要填充的面積）：

從邊界池中隨機取出一個邊界；

算出與其接壤的四個點，取出還未被填充的點；

在取出的點中隨機一個將其填充；

填充后計算改點接壤的四個點是否有全都是已經填充了的，若不是，則將該坐標加入邊界池；

拿著剛才計算的接壤的四個點，分別判斷其是否周邊四個點都已被填充，若是且該點在邊界池中，則從邊界池拿走；

回到第二大步繼續循環；

返回填充好的結果。

給出代碼 Demo：

function random(max) {
    return Math.round(Math.random() * max);
}

class Filler2 {
    constructor(length, needArea) {
        this.length = length;
        this.needArea = needArea;
    }

    _getContiguous(frontier) {
        return Filler2.DIRS.map(dir => ({
            x: frontier.x + dir[0],
            y: frontier.y + dir[1]
        }));
    }

    fill() {
        const mat = [];
        for (let i = 0; i < this.length; i++) {
            let row = [];
            for (let j = 0; j < this.length; j++) row.push(".");
            mat.push(row);
        }

        const start = {
            x: random(this.length - 1),
            y: random(this.length - 1)
        };
        mat[start.x][start.y] = "x";

        let frontierCount = 1;
        const frontiers = {
            [`${start.x}:${start.y}`]: true
        };

        for (let i = 1; i < this.needArea; i++) {
            // 取出一個邊界
            const randIdx = random(frontierCount - 1);
            const frontier = Object.keys(frontiers)[randIdx].split(":").map(n => parseInt(n));

            // _getContiguous 算出接壤坐標，filter 去除無用坐標
            const newCoors = this._getContiguous({
                x: frontier[0],
                y: frontier[1]
            }).filter(coor => {
                if (coor.x < 0 || coor.y < 0 || coor.x >= this.length || coor.y >= this.length) return false;
                if (mat[coor.x][coor.y] === "x") return false;
                return true;
            });

            // 隨機取一個坐標
            const newCoor = newCoors[random(0, newCoors.length - 1)];

            // 填充進去
            mat[newCoor.x][newCoor.y] = "x";

            // 獲取接壤坐標
            const contiguousOfNewCoor = this._getContiguous(newCoor).filter(coor => {
                if (coor.x < 0 || coor.y < 0 || coor.x >= this.length || coor.y >= this.length) return false;
                return true;
            });

            // 若有一個接壤點為空，就認為當前坐標是邊界，若是邊界則把當前坐標加入對象
            if (contiguousOfNewCoor.reduce((ret, coor) => {
                    if (mat[coor.x][coor.y] === "x") return ret;
                    return true;
                }, false)) {
                frontiers[`${newCoor.x}:${newCoor.y}`] = true;
                frontierCount++;
            }

            // 再檢查接壤的坐標是否繼續為邊界
            for (let i = 0; i < contiguousOfNewCoor.length; i++) {
                const cur = contiguousOfNewCoor[i];

                const isFrontier = this._getContiguous(cur).filter(coor => {
                    if (coor.x < 0 || coor.y < 0 || coor.x >= this.length || coor.y >= this.length) return false;
                    return true;
                }).reduce((ret, coor) => {
                    if (mat[coor.x][coor.y] === "x") return ret;
                    return true;
                }, false);

                // 若不是邊界的話，只管刪除
                if (!isFrontier && frontiers[`${cur.x}:${cur.y}`]) {
                    delete frontiers[`${cur.x}:${cur.y}`];
                    frontierCount--;
                }
            }
        }

        // 一圈下來，就出結果了
        return mat;
    }
}

Filler2.DIRS = [ [ 0, 1 ], [ 0, -1 ], [ 1, 0 ], [ -1, 0 ] ];

注意：上面的代碼是我一溜煙寫出來的，所以并沒有后續優化代碼簡潔度，其實很多地方的代碼可以抽象并復用的，懶得改了，能看就好了。用的時候就跟之前 DFS 代碼一樣 new 一個 Filler2 出來并 fill 就好了。
效果依然可以去 JSFiddle 看。

或者也可以直接看效果圖：

50x50 填充 800 胖胖的區域

50x50 填充 50 胖胖的區域

顯而易見，跟之前 DFS 生成出來的奇形怪狀相比，這種算法生成的連通區域更像是一塊 Mainland，而前者則更像是一個洼地沼澤或者叢林。

前面兩種算法，一個是生成瘦瘦的稀奇古怪的面積，一個是生成胖胖的區域。有沒有辦法說在生成胖胖的區域的情況下允許一定的稀奇古怪的形狀呢？

其實將兩種算法結合一下就好了。結合的做法有很多，這里舉一個例子，大家可以自己再去想一些出來。

首先將需要的區域對半分（即配比 1 : 1），例如如果需要 800，就分為 400 跟 400。（為了長得好看，其實這個比例可以自行調配）

將前一半的區域用 for 生成胖胖的區域；

將剩下的區域隨機幾次，每次隨機一個剩下所需要的面積以內的數，將這個數字作為 DFS 所需要生成的面積量，并從邊界數組中隨機取一個邊界坐標并計算其合法接壤坐標開始進行 DFS 得到結果；

循環第 3 步知道所需區域面積符合要求為止。

注意：為了保證每次 DFS 一開始的時候都能取到最新的邊界坐標，在 DFS 流程中的時候每標一個區域填充也必須走一遍邊界坐標更新的邏輯。

具體代碼就不放文章里面解析了，大家也可以到 JSFiddle 中去觀看。

或者也可以直接看效果圖：

50x50 填充 800 混合區域（配比 3 : 1）

50x50 填充 50 胖胖的區域（配比 4 : 1）

結合了兩種算法，我們得到了一個我認為可能會更好看一點的區域。

此外，我們還能繼續「喪心病狂」一點，例如兩種方式交替出現，流程如下：

指定特定方法和面積，奇數次用 for，偶數次用 DFS；

如果是 for 則隨機一個 Math.min(剩余面積, 總面積 / 4) 的數字；

如果是 DFS 則隨機一個 Math.min(剩余面積, 總面積 / 10) 的數字；

從邊界數組中取一個坐標，并從合法接壤坐標中取一個坐標出來；

以第 2 步取出的坐標為起點，使用第 1 步指定的方法生成第 1 步指定的面積的單連通區域；

如果生成面積仍小于指定面積，則回到第 1 步繼續循環，否則返回當前結果。

依舊是給出 JSFiddle 的預覽。

或者也可以直接看效果圖：

50x50 填充 800 喪病區域

50x50 填充 800 喪病區域

注意：這里只給出思路，具體配比和詳細流程大家可以繼續優化。

最后，這里給出幾張 10x10 填 50 的效果圖放一起對比一下。

以及，幾張 50x50 填充 800 面積的效果圖對比。

之所以多出一節來，是因為我在寫回答以及這篇文章的時候腦抽了一下，迷迷糊糊想成了連通區域，感謝評論區童鞋的提醒。實際上單連通區域要稍微復雜一些。

在拓撲學中，單連通是拓撲空間的一種性質。直觀地說，單連通空間中所有閉曲線都能連續地搜索至一點。此性質可以由空間的基本群刻畫。

這個空間不是單連通的，它有三個洞

——單連通@Wikipedia

對于非周期性的區域來說，生成一個單連通區域只要在上面的方法里面加點料就可以了。即在一個位置填充的時候，判斷一下將它填充進去之后是否會出現所謂的「洞」。而這一點在非周期性區域中，由于在填充當前坐標前，已存在的區域已經是一個單連通區域，所以枚舉一下幾種情況即可排除非單連通區域的情況：

新加的坐標其上下都有填充，但其左右為空；或者左右都有填充，但其上下為空；

新加的坐標只有一面相鄰有填充，但該面對面的邊所對應的兩個角對過去至少有一個角與其它坐標共享頂點；

新加的坐標同一個頂點的兩條邊有接壤，且其對角頂點對過去的坐標與其共享頂點。

而對于周期性的區域來說，暫時我還沒想到很好的辦法。

對于情況一而言，如果處于對面的兩接壤坐標都有填充，且再多一個接壤面的話，原小區域內只有可能是「匚」型，那么填充進去只會形成一個 2x3 的實心區域，而如果只有處于對面的兩個接壤坐標有填充的話，說明原小區域有兩個面對面隔空的區域，它們形成單連通區域的大前提就是從其它地方繞出去將它們連起來，若這個時候將它們閉合的話，勢必會形成一個空洞，如下圖所示：

對于情況二而言，如果只有一面有填充，但是對面的頂點有共享的話，可以類比為情況一，舉例如下：

對于情況三而言，其實就是情況二加一條邊有填充，如果在情況二的情況下，在上圖“原”的區域下方的空若已有填充，那么在“新”的位置填充進去，就形不成空洞了。畢竟如果“空”的位置已有填充的話，若先前狀態生成沒有洞的連通區域，則“空”下方也必定不是一個空洞的區域。

在解析完三種情況后，算法就明朗起來——在上面的 DFS 算法每次執行填充操作的時候，都判斷一下當前填充是否符合剛才列舉的三種情況，若符合，則不填充該點。

所以只需對 DFS 的那個代碼做一下修改就好了，首先把狀態還原兩行代碼刪掉，然后在之前

if (newX < 0 || newX >= this.length || newY < 0 || newY >= this.length) continue;

這句代碼之下加一個條件判斷就好了：

if(this.willBreak(newX, newY)) {
    continue;
}

剩下的就是去實現 this.willBreak() 函數：

class Filler {
    ...
    
    willBreak(x, y) {
        // 九宮格除自己以外的其它格狀態
        let u = false, d = false, l = false, r = false;
        let lu = false, ld = false, ru = false, rd = false;
        if(x - 1 >= 0 && this.map[x - 1][y] === "x") u = true;
        if(x + 1 < this.length && this.map[x + 1][y] === "x") d = true;
        if(y - 1 >= 0 && this.map[x][y - 1] === "x") l = true;
        if(y + 1 < this.length && this.map[x][y + 1] === "x") r = true;
        if(x - 1 >= 0 && y - 1 >= 0 && this.map[x - 1][y - 1] === "x") lu = true;
        if(x - 1 >= 0 && y + 1 < this.length && this.map[x - 1][y + 1] === "x") ru = true;
        if(x + 1 < this.length && y - 1 >= 0 && this.map[x + 1][y - 1] === "x") ld = true;
        if(x + 1 < this.length && y + 1 < this.length && this.map[x + 1][y + 1] === "x") rd = true;
        
        // 情況 1
        if((l & r) ^ (u & d)) return true;
        
        // 情況 2
        if(l + r + u + d === 1) {
            if(l && (ru || rd)) return true;
            if(r && (lu || ld)) return true;
            if(u && (ld || rd)) return true;
            if(d && (lu || ru)) return true;
        }
        
        // 情況 3
        if(l + r + u + d === 2) {
            // 情況 1 已經被 return 了，所以相加為 2 的肯定是共享頂點
            if(l && u && rd) return true;
            if(l && d && ru) return true;
            if(r && u && ld) return true;
            if(r && d && lu) return true;
        }
        
        return false;
    }
}

進 JSFiddle 看完整代碼。

然后是 50x50 填充 800 的效果：

以及 10x10 填充 50：

注意：左下角的洞看起來是洞，實際上是處于邊界了，而填充區域無法與邊界合成閉合區域，實際上將地圖往外想想空一格就可以知道它并不是一個洞了。當然如果讀者執意不允許這種情況發生，那么只需要在 willBreak() 函數判斷的時候做點手腳就可以了，至于怎么做手腳大家自己想吧。

這種情況生成的地圖比較像迷宮，哪怕是針對「胖胖的區域」做這個改進，JSFiddle 出來的也是下面的效果：

所以呢，繼續優化——我們知道有三種情況是會生成非單連通區域的，所以當我們探測到這種情況的時候，去 BFS 它內外區域，看看究竟是哪個區域被封閉出一個空洞來，探測出來之后再看看我們目前還需要填充的區域面積跟這個空洞的面積是否夠用，若夠用則將空洞補起來，不夠用則當前一步重新來過——即再隨機一個坐標看看行不行。

思想說出來了，具體的實現還是看看我寫在 JSFiddle 里面的代碼吧。

50x50 填充 800 的效果如下：

這么一來，我們很容易能跟 DFS 的算法結合起來，即之前說過的更喪病的算法。結合方法很簡單，分別把改進過的 DFS 和胖胖區域的算法一起融合進之前喪病算法的代碼中就好了。老樣子我還是把代碼更新到了 JSFiddle 里面。大家看看 50x50 填充 800 的效果吧：

最后，由于一開始文章寫的概念性錯誤給大家帶來的不變表示非常抱歉，好在最后我還是補全了一下文章。

本文主要還是講了，如何隨機生成一個指定面積的單連通區域。從一開始拍腦袋就能想到 DFS 開始，延伸到胖胖的區域，然后從個人認為「圖不好看」開始，想辦法如何結合一下兩種算法使其變得更自然。

針對同一件事的算法們并非一成不變或者不可結合的。不是說該 DFS 就只能 DFS，該 for 就只能 for，稍微結合一下也許食用效果更佳哦。

哦對了，在這之前還有一個例子就是我在三年多前寫的主題色提取的文章《圖片主題色提取算法小結》，其中就講到我最后的方法就是結合了八叉樹算法和最小差值法，使其在提取比較貼近的顏色同時又能夠規范化提取出來的顏色。

總之就是多想想，與諸君共勉。