Houdini学习笔记030_VEX生成迷宫

今天给大家带来的是迷宫图案的VEX生成方法，效果如下——

该方法全称为深度优先搜索算法（Deep-First-Search），简称DFS，是一种经典的迷宫图案生成算法。基本思路如下：

为了便于理解，我用下图进行简单说明——

（1）比如给定一个点阵，选择其中一个点作为起点，并标记为“active”，找到和这个点相邻的点作为下一步可能前进的方向，称之为“neighbors”；

（2）每前进一步，之前的两个点都被标记为“visited”（已访问过），后面再找邻点时这些点就不在考虑范围内；

（3）由此依次连接点会得到一条路径，直到找不到未被访问过的相邻点时，则沿着路径逐点返回；

（4）当某个点有新的未访问邻点出现时，将其标记为新的“active”，继续执行以上过程；

（5）全部点都被“visited”后，将返回到最初的起点，搜索结束。

这个算法比之前学习的内容看上去都要复杂一些，需要用group来对不同的点进行标记。网上的Houdini相关教程较少，理解起来也相对不易。这里我尽量不绕圈子，让代码更加简单易读。

下面进入主题——

主要步骤用到四个节点，加上solver内部的Attribute Wrangle，一共五个节点。

前两个节点用来得到如下点阵，你也可以用别的方法。

然后需要进行一些设置，至于设置哪些内容，需要我们先对整个流程充分理解后才好对症下药。所以我们先多啰嗦几句，帮大家进入状态：

首先，我得有一个起点，这个好办，直接选一个点编号就可以，比如0号。

然后是找它的邻居，对于网格模型，可以用neighbours函数。但这里是一堆点，需要用nearpoints函数。

具体用solver解算时，不是每个点都要找邻居，只有当前处于“active”状态的点需要。所以得设置一个能区分点是否“active”的判断条件。

再者就是，找邻居时已经找过的就不要再找了，所以还得有一个区分点是否被找过的判断条件，这里称之为“visited”。

下面开始具体设置，添加一个Point Wrangle节点，可取名为“set_group”。这里直接取0号点作为起点，通过设置组的方法来决定其状态。如果是active（活跃）或visited（已访问），值为1；反之，如果是inactive（不活跃）或unvisited（未访问），值为0。双斜杠后面是说明性语句，不参与VEX脚本运行（黄色语句）。

设置点组可以用函数setpointgroup进行，“active”和“visited”是组名称，最后面的1和0可用于判断点的状态。有时候最后还会加“set”，此处省略。

设置完成后可在Geometry Spreadsheet窗口查看——

下面我们直接添加solver节点，其余设置用到时再回过头来补充。

双击进入solver节点内部，用一个Point Wrangle节点来生成迷宫。从solver节点中的Prev_Frame节点名称可知，这是一个和帧数有关的动力学解算器。上一帧的结果会作为下一帧的输入。每一帧我们对当前的点进行判断，找到处于“active”状态的点，然后搜寻其邻点。使用if语句作为判断条件：

if(@group_active == 1){

}

@group_active是一种固定写法，表示访问组属性（使用函数inpointgroup也可以，具体可查看帮助文档）。还有一种方法是直接在节点的Group选项中选择active。正常情况下，所有点当中只有一个处于active状态。

然后搜寻这个active点的邻点。如果直接用nearpoints函数的话，存在两个问题：

（1）自身也会被搜索到；

（2）无法判别搜索到的点是否被访问过（visited）。

据此，我们可以自定义一个搜索函数，如nearPts：

function int[ ] nearPts(int index){

}

int[ ]表示函数返回的类型是一个整型数组（void表示无返回值），( )内是函数的变量，同样要标明数据类型。这里是根据点的编号来搜索，所以是整数型，变量名称自行定义，如index。

先不加额外条件，直接用nearpoints函数搜索所有满足条件的点。该函数需要两个变量，一个是当前点的坐标pos，一个是最大搜索半径maxdist。

pos可用point函数得到，maxdist只要比相邻点间距稍大即可，可以直接用grid的参数计算（sizex/(row-1)）。VEX中可用ch*函数调用，见下图——

nearpoints函数返回数组后，对数组内的点编号进行条件筛选，满足未被访问过且不是点自身两个条件，才是最终搜寻到的邻点。这里我用的是foreach函数，对于nearPts数组中的每个数值nearPt进行判断，两个判断条件是并列关系，所以用&&（逻辑与）。

条件1：nearPt != index（不是点自身）；

条件2：inpointgroup(0, "visited", nearPt) == 0（未被访问过）。

满足条件的点用append函数添加到新的数组targets[ ]中，最后return targets。（照着写的时候注意中英文输入法和标点符号不要弄错）

自定义函数写完后我们可以测试一下，比如直接调用该函数：

i[ ]@targets = nearPts(@ptnum);

在Geometry Spreadsheet窗口查看targets属性如下——

对照视图也可以看到，0号点的邻点就是1号和10号点。

接下来是在邻点中随机找一个作为前进的目标点，使用rand函数。注意这里的写法较长：

int randnum = int ( fit01 (rand (@Frame + chf("seed")), 0, len(targets) ) );

其实就是括号比较多，容易搞混而已。因为rand函数返回值为0~1，对于不同长度的邻点数组，可用fit01函数将其扩展到0~n，然后取整。下一个目标点的编号为：

int target = targets[randnum];

当然，以上是在找到了邻点的情况下才执行的，所以要加判断语句：

if ( len(targets) > 0 )

找到目标点后active的状态会传递到目标点，作为下一次搜索的起点。因而组属性要重新设置，如下所示——

然后在起点和目标点之间连线：

addprim(0, "polyline", @ptnum, target);

还有一种情况是找不到未被访问过的邻点，即len(targets) == 0。这时就要沿着路径逐点返回，寻找新的active点。所以我们得把走过的路径记录下来，做法是用一个数组记录走过的点编号。

回到前面的set_group节点，定义一个stack[ ]数组，先储存起始点编号0。为了方便调用，将其指定给detail属性，函数写法为：

setdetailattrib(0, "stack", stack);

有了这个储存点路径的数组，每次找到新的目标点就可以添加进去：

setdetailattrib(0, "stack", target, "append");

现在继续讨论没找到目标点时的情形。先用detail函数把储存的stack属性调出来。

int stack[ ] = detail(0, "stack");

然后沿原路返回，挨个点搜索邻点，注意倒序的for循环条件写法：

for(int i = len(stack) - 2; i >= 0; i--){

}

为什么从len(stack) - 2开始，大家自行思考。还是用自定义的nearPts函数来搜索，如果找到了新的邻点，重新设置active点的位置。然后用break跳出循环。

最后maze_generation的全部代码如下（不懂就仔细琢磨，直到搞懂为止）：

增加solver节点的Sub Steps可以让每帧解算更多的步数。

由此我们就得到了迷宫的路径，至于怎么在此基础上做出周围的墙，可以创建一个比当前grid行列各增加1的网格，然后用判断相交的节点intersection analysis。当然，最好是刚开始直接用网格的primitive中心作为初始点阵，最后直接用原来的网格线与生成的迷宫线求交点即可。根据intersection analysis节点得到的sourceprim属性选择性删除原来的网格线，相当于沿着迷宫行走路线打通了间隔的墙，形成通道。

这样对于其他的网格应该同样奏效，感兴趣的朋友可以自己尝试在上述代码基础上加以改进。今日分享到此为止，感谢阅读，下回见~