PCG——程序化地形生成（1）

前言

接觸了半年多Houdini，佛系研究了一下PCG(Procedural Content Generation)相關的技術，這真是個好東西，趕在年前寫個總結。Houdini 一款DCC軟件，功能又多又強（初學者，不敢瞎描述這款神器），基于節點的操作方式，非常適合PCG，也非常適合程序員，我覺得游戲客戶端至少要掌握一款DCC軟件，如果只能掌握一款DCC軟件那首選Houdini。PCG(Procedural Content Generation) 可以是程序化生成任何東西，這里主要研究程序化生成地形。

游戲中大場景越大，投入的人力，時間越多。如何通過程序來降本增效是一件很值得研究的事情。程序按照一系列規則執行，程序化就是建立一系列規則并實現。這跟流水線的道理是一樣的，把流水線的流程設計好，每個節點功能實現好，就可以自動化高效運作。但它跟傳統的人工相比也并非全是優勢，畢竟人工可以為所欲為，而程序只能根據規則執行，如果規則事無巨細則導致程序極其復雜，難以維護。簡而言之，程序化可以節省成本，快速迭代，快速產出，人工可以打磨細節，讓兩者保持平衡，相互協作是PCG需要慎重考慮的，平衡的好則朝九晚六，平衡的不好則996ICU。

這篇文章主要記錄我研究PCG的一些概述。

正文

本文包含了地形，河流，路網，植被生成。

地形生成

地形乃場景的基礎，我將地形分為平原，高地，山脈，通過線段勾勒形狀。

平原

通過線段勾勒出基本形狀，然后投影在HeightField上，再重映射高度，平滑邊緣讓其跟海面自然銜接。

平滑邊緣

重映射高度

高地

在平原上拔地而起的高地，高地的特征是：拔地而起，頂部平坦，有近乎垂直的斜坡。我希望遠看或某些角度看高地有一種高不可攀的感覺，但它始終有路徑可以從山腳抵達山頂（方便后續實現盤山路）。

高地的生成依舊通過線段勾勒出形狀，隨后將高地按層高切成若干層，層與層之間彼此連接，從邊緣計算出一條可經過所有層的路徑，這樣就能保證始終有一條路徑可以從山腳通往山頂。

分層

方法是，將高度除以層高得到層數，通過voronoifracture將平面分層，然后計算每一層跟周圍層的連接關系，這樣連接層數最少的必然在邊緣，可以將它作為上山的起點，從起點開始計算出一條經過所有層的路徑，路徑經過的層逐漸升高。

實現如下：

int first(int numprim)
{
    int count = 0;
    int pridx = 0;
    for (int i = 0; i != numprim; ++i)
    {
        int link_prims[] = prim(0, "link_prims", i);
        if (count == 0 || len(link_prims) < count)
        {
            count = len(link_prims);
            pridx = i;
        }
    }
    return pridx;
}

int has(int arr[]; int val)
{
    return find(arr, val) >= 0;
}

int handle_cell(int top; int trace[], close[], close_top[])
{
    int finish = 1;
    int close_beg = close_top[-1];
    int link_prims[] = prim(0, "link_prims", top);
    for (int i = 0; i != len(link_prims); ++i)
    {
        if (has(trace, link_prims[i])) { continue; }

        if (has(close[close_beg:], link_prims[i]))
        {
            continue;
        }

        append(close, link_prims[i]);
        append(trace, link_prims[i]);
        append(close_top, len(close));
        finish = 0;
        break;
    }
    return finish;
}

//  路徑記錄在trace
//  已知不可走路徑記錄在close
//  close_top跟trace一一對應, 記錄在close中的起始索引
//  即close[close_top[-1]: ]是trace[-1]所對應的close
int trace[];
int close[];
int close_top[];
append(trace,     first(@numprim));
append(close_top,               0);

for (; i@cell_count != len(trace); )
{
    int finish = handle_cell(trace[-1], trace, close, close_top);
    if (finish)
    {
        if (i@cell_count == len(trace))
        {
            break;
        }
        close = close[:close_top[-1]];
        pop(trace,     -1);
        pop(close_top, -1);
    }
}

for (int i = 0; i != len(trace); ++i)
{
    setprimattrib(0, "priority", trace[i], i);
}

如果把層作為一個整體升高，則會出現斷層，還需要將層與層的共邊修正形成類似斜坡。
思路是，計算每個點連接的層，如果連接層中有比當前層恰好高一級的層，則說明這個頂點需要向上抬升。

接下來將生成的mesh投影到HeightField，再平滑邊緣即可。

山脈

山脈依舊通過線段勾勒出形狀，再remesh，并計算每個點到邊緣的距離來控制高度，高度可以通過曲線控制，來達到越往中心越高的非線性高度。

風化

最后將地形風化，并將凹陷的地面補平，讓它有更多的平地。

填補凹陷

這一步可有可無，我覺得游戲中的地形要充足利用，平坦地面更適合二次開發。

水域生成

水域包含：海，河流，湖泊。

海

將HeightField轉化為Mesh，再將海平線以上的Prim刪除。

湖泊生成

用線段勾勒出湖泊，將湖泊覆蓋的地形壓低至湖泊最低高度形成湖岸，再將地形依據離岸邊的距離壓低至湖泊深度，形成漏斗形狀（通過曲線控制，并非一定是漏斗）

河流生成

用線段勾勒出河流，河流可以從一條河變成兩條河也可以從兩條河變成一條河，河流從高處流往低處，經過高低差較大的地形時形成瀑布，河流始終從湖泊流向湖泊或大海。

勾勒河流

用線段勾勒河流，線段可以連接匯合成一條亦可分裂成兩條。

確定流向

線段吸附在地面上，將線段末端更高的點作為河流源頭，并從源頭到末端將點下壓，確保每個點都不高于前一個點（源頭是第一個點），這樣就可以保證河流永遠都是從高處流向低處。

線段會彼此相鄰，比如A線段相鄰B線段，而B是A的分支，那么應該先將A執行上述步驟，再執行B，以此類推，通過BFS算法來計算順序，將最先畫的線段作為第一條線段（河），加入到隊列，然后執行算法：

從隊列彈出一個線段
遍歷線段的每一個頂點
將相鄰且沒有處理過的線段加入到隊列
返回第一步，直到處理完所有線段

這樣線段就有了確定的順序，先從第一條開始，然后與它相鄰的第一條線段，第二條線段……，與它相鄰的第一條線段的第一條線段，第二條線段……

具體實現如下：

int has(int prim_has[]; int pridx)
{
    return find( prim_has, pridx) >= 0;
}

void insert_prim(int pridxs[], prim_que[], prim_has[])
{
    for (int pridx : pridxs)
    {
        if (!has(prim_has, pridx))
        {
            append(prim_que, pridx);
            append(prim_has, pridx);
        }
    }
}

int downflow_pt(int ptidxs[]; vector global_pos[])
{
    int is_swap = 0;
    vector first = global_pos[ptidxs[ 0]];
    vector last  = global_pos[ptidxs[-1]];
    
    if (first.y < last.y)
    {
        ptidxs = reverse(ptidxs);
        vector temp = last;
        last = first;
        first = temp;
        is_swap = 1;
    }
    
    for (int i = 0; i != len(ptidxs); ++i)
    {
        vector pos = global_pos[ptidxs[i]];
        pos.y = min(first.y, pos.y);
        pos.y = max(last.y,  pos.y);
        global_pos[ptidxs[i]] = pos;
        first = pos;
    }
    return is_swap;
}

void handle_prim(int pridx; int prim_que[], prim_has[]; vector global_pos[])
{
    int prim_ps[] = primpoints(0, pridx);
    for (int i = 0; i != len(prim_ps); ++i)
    {
        int cross_count = neighbourcount(0, prim_ps[i]);
        if (cross_count > 2)
        {
            int point_prs[] = pointprims(0, prim_ps[i]);
            insert_prim(point_prs, prim_que, prim_has);
        }
    }
    if (downflow_pt(prim_ps, global_pos))
    {
        setprimgroup(0, "reverse", pridx, 1);
    }
    else
    {
        setprimgroup(0, "reverse", pridx, 0);
    }
}

vector global_pos[];
for (int i = 0; i != @numpt; ++i)
{
    vector pos = point(0, "P", i);
    append(global_pos, pos);
}

int prim_que[];
int prim_has[];
append(prim_que, 0);
append(prim_has, 0);
for (; len(prim_que) != 0; )
{
    int top = pop(prim_que, 0);
    handle_prim(top, prim_que, prim_has, global_pos);
}

for (int i = 0; i != @numpt; ++i)
{
    setpointattrib(0, "P", i, global_pos[i]);
}

這一步之后，每一條線段都是從高處流往低處。

標記交叉口

點如果連接數超過2個表示該點是一個交叉口（只處理三岔口），然后將連接該點的3個方向線段都往遠推移。

生成瀑布

給定一個高度差閾值，如果點與上一個點的高度大于該閾值則形成瀑布，再給定一個長度，如果超出這個長度則是另一個瀑布，這樣來形成連續瀑布的效果（demo沒有呈現連續瀑布）。

避免重疊

接下來嘗試性生成河面，并將高度歸零，測試河面是否會重疊（急彎處會重疊），如果有重疊則將重疊部分的河面收窄。

生成交叉口

這一步生成交叉口河面，在前面已經確定了交叉點，這一步需要將交叉點跟與之相鄰的3個點提取總共4個點，將交叉點與其他3個點按順時針重新連接新的prim，并計算出每個頂點的法線，隨后將頂點向法線方向移動河面寬度，這樣既可跟河面縫合。

河面生成

將交叉口從線段中剔除，然后將Line CopyToPoints，再Skin既可。

另外PolyScalpel很好用，它可以用點將線段切開。

河道生成

首先將地面抬升至河面以上，確保地面能完全蓋住河面。

隨后下挖河道，距離線段越近則越深，線段上有河寬信息，所以可以得出河道寬度，可通過曲線控制下挖力度。

最后平滑河岸和河道底部。

生成路網

路的作用是連接，它可以連接兩個據點，也可以連接兩個村莊。

規劃道路

用線段勾勒出目的地和連通關系。

生成尋路地圖

將HeightField轉化為點陣，將不可尋路的點剔除，例如：海洋，湖泊，村莊等。

將位于河岸的點單獨提取，并連接成河岸線，然后并入原先得點陣中。
提取河岸線的思路是，先提取河岸點陣，然后讓其相互連通，隨后計算點到點的路徑，保留最長那條路徑。

接下來將點陣連接生成路線圖，可以給定一個高度閾值，如果相連高度差大于這個閾值則不連接，這樣就不會出現陡峭的路線。

接下來將河岸與河岸連接讓其可以跨河通行。思路是，遍歷每個河岸點，搜索附近一定距離的其他河岸點（不歸屬于同一個prim則表示其他河岸點）。

排除跟河岸不垂直的通行路線，用一張截圖來說明河岸通行的限制。

此時一個河岸點會連接對岸多個河岸點，這時候只要保留最短那條路徑既可。

接下來是最后一步，由于河岸點距離河岸非常近，它只適合移動到對岸，并不適合在同一個岸邊生成道路，所以還需要將河岸之間的連接切斷。

至此，地圖生成完畢，就可以用于尋路了。

生成路徑

尋路可以用findshortestpath節點，它的Custom Edge Cost屬性可以支持表達式，因此這里我讓它的垂直和拐彎的尋路開銷變大，這樣它就會優先平坦少轉向的路線，加上此前的高地生成邏輯，那么生成盤山路也不在話下。這兩個參數都可通過曲線控制，可以讓它的開銷非線性變化。

實現如下：

if($PT == $PTSTART, 0, ch("horizontal_factor") * chramp("horizontal_cost", 
    1 - max(0, dot(normalize(vector3($TX - $TX0,          0, $TZ - $TZ0)),
                   normalize(vector3($TX2 - $TX,          0, $TZ2 - $TZ)))), 0))
+
ch("vertical_factor") * chramp("vertical_cost",
    1 - max(0, dot(normalize(vector3($TX2 - $TX,          0, $TZ2 - $TZ)),
                   normalize(vector3($TX2 - $TX, $TY2 - $TY, $TZ2 - $TZ)))), 0)