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)