前言
接触了半年多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)
- 优化路线
将太靠近的路线合并为一条，形成交汇。
- 平滑交叉口
将道路交叉口平滑，正常来讲，交叉口都是出现在相对平坦的路上。另外让交叉口附近的路变得平坦也方便道路生成的更实用和好看。
-
标记桥梁
将位于河流的路线标记为桥梁，同时将桥梁前后的路线平滑（架桥之前肯定得把放墩子的地面铺平）。
-
生成道路
将桥梁部分从路径中剔除，然后将HeightField沿着路径压平形成道路。
然后在桥梁的位置生成桥模型。
植被生成
植被做的比较随意，把需要有植被的部分用mask标记，然后HeightField Scatter就行了。
树从土里长出，会让根部的土地微微凸起。
在随便撒点石头，石头跟树的分布不同，树可以长在斜坡上，石头通常都会在容易积水的凹陷位置。
完结
