PCG——程序化地形生成（1） - 落单的毛毛虫

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]所对应的closeint 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算法来计算顺序，将最先画的线段作为第一条线段（河），加入到队列，然后执行算法：

1. 从队列弹出一个线段
2. 遍历线段的每一个顶点
3. 将相邻且没有处理过的线段加入到队列
4. 返回第一步，直到处理完所有线段

这样线段就有了确定的顺序，先从第一条开始，然后与它相邻的第一条线段，第二条线段……，与它相邻的第一条线段的第一条线段，第二条线段……

具体实现如下：

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)

将太靠近的路线合并为一条，形成交汇。

• 平滑交叉口

将道路交叉口平滑，正常来讲，交叉口都是出现在相对平坦的路上。另外让交叉口附近的路变得平坦也方便道路生成的更实用和好看。

将位于河流的路线标记为桥梁，同时将桥梁前后的路线平滑（架桥之前肯定得把放墩子的地面铺平）。

将桥梁部分从路径中剔除，然后将HeightField沿着路径压平形成道路。

然后在桥梁的位置生成桥模型。

植被做的比较随意，把需要有植被的部分用mask标记，然后HeightField Scatter就行了。

树从土里长出，会让根部的土地微微凸起。

在随便撒点石头，石头跟树的分布不同，树可以长在斜坡上，石头通常都会在容易积水的凹陷位置。