今天給大家?guī)淼氖敲詫m圖案的VEX生成方法，效果如下——

該方法全稱為深度優(yōu)先搜索算法（Deep-First-Search），簡稱DFS，是一種經(jīng)典的迷宮圖案生成算法?；舅悸啡缦拢?/p>

為了便于理解，我用下圖進(jìn)行簡單說明——

（1）比如給定一個(gè)點(diǎn)陣，選擇其中一個(gè)點(diǎn)作為起點(diǎn)，并標(biāo)記為“active”，找到和這個(gè)點(diǎn)相鄰的點(diǎn)作為下一步可能前進(jìn)的方向，稱之為“neighbors”；

（2）每前進(jìn)一步，之前的兩個(gè)點(diǎn)都被標(biāo)記為“visited”（已訪問過），后面再找鄰點(diǎn)時(shí)這些點(diǎn)就不在考慮范圍內(nèi)；

（3）由此依次連接點(diǎn)會(huì)得到一條路徑，直到找不到未被訪問過的相鄰點(diǎn)時(shí)，則沿著路徑逐點(diǎn)返回；

（4）當(dāng)某個(gè)點(diǎn)有新的未訪問鄰點(diǎn)出現(xiàn)時(shí)，將其標(biāo)記為新的“active”，繼續(xù)執(zhí)行以上過程；

（5）全部點(diǎn)都被“visited”后，將返回到最初的起點(diǎn)，搜索結(jié)束。

這個(gè)算法比之前學(xué)習(xí)的內(nèi)容看上去都要復(fù)雜一些，需要用group來對(duì)不同的點(diǎn)進(jìn)行標(biāo)記。網(wǎng)上的Houdini相關(guān)教程較少，理解起來也相對(duì)不易。這里我盡量不繞圈子，讓代碼更加簡單易讀。

下面進(jìn)入主題——

主要步驟用到四個(gè)節(jié)點(diǎn)，加上solver內(nèi)部的Attribute Wrangle，一共五個(gè)節(jié)點(diǎn)。

前兩個(gè)節(jié)點(diǎn)用來得到如下點(diǎn)陣，你也可以用別的方法。

然后需要進(jìn)行一些設(shè)置，至于設(shè)置哪些內(nèi)容，需要我們先對(duì)整個(gè)流程充分理解后才好對(duì)癥下藥。所以我們先多啰嗦幾句，幫大家進(jìn)入狀態(tài)：

首先，我得有一個(gè)起點(diǎn)，這個(gè)好辦，直接選一個(gè)點(diǎn)編號(hào)就可以，比如0號(hào)。

然后是找它的鄰居，對(duì)于網(wǎng)格模型，可以用neighbours函數(shù)。但這里是一堆點(diǎn)，需要用nearpoints函數(shù)。

具體用solver解算時(shí)，不是每個(gè)點(diǎn)都要找鄰居，只有當(dāng)前處于“active”狀態(tài)的點(diǎn)需要。所以得設(shè)置一個(gè)能區(qū)分點(diǎn)是否“active”的判斷條件。

再者就是，找鄰居時(shí)已經(jīng)找過的就不要再找了，所以還得有一個(gè)區(qū)分點(diǎn)是否被找過的判斷條件，這里稱之為“visited”。

下面開始具體設(shè)置，添加一個(gè)Point Wrangle節(jié)點(diǎn)，可取名為“set_group”。這里直接取0號(hào)點(diǎn)作為起點(diǎn)，通過設(shè)置組的方法來決定其狀態(tài)。如果是active（活躍）或visited（已訪問），值為1；反之，如果是inactive（不活躍）或unvisited（未訪問），值為0。雙斜杠后面是說明性語句，不參與VEX腳本運(yùn)行（黃色語句）。

設(shè)置點(diǎn)組可以用函數(shù)setpointgroup進(jìn)行，“active”和“visited”是組名稱，最后面的1和0可用于判斷點(diǎn)的狀態(tài)。有時(shí)候最后還會(huì)加“set”，此處省略。

設(shè)置完成后可在Geometry Spreadsheet窗口查看——

下面我們直接添加solver節(jié)點(diǎn)，其余設(shè)置用到時(shí)再回過頭來補(bǔ)充。

雙擊進(jìn)入solver節(jié)點(diǎn)內(nèi)部，用一個(gè)Point Wrangle節(jié)點(diǎn)來生成迷宮。從solver節(jié)點(diǎn)中的Prev_Frame節(jié)點(diǎn)名稱可知，這是一個(gè)和幀數(shù)有關(guān)的動(dòng)力學(xué)解算器。上一幀的結(jié)果會(huì)作為下一幀的輸入。每一幀我們對(duì)當(dāng)前的點(diǎn)進(jìn)行判斷，找到處于“active”狀態(tài)的點(diǎn)，然后搜尋其鄰點(diǎn)。使用if語句作為判斷條件：

if(@group_active == 1){

}

@group_active是一種固定寫法，表示訪問組屬性（使用函數(shù)inpointgroup也可以，具體可查看幫助文檔）。還有一種方法是直接在節(jié)點(diǎn)的Group選項(xiàng)中選擇active。正常情況下，所有點(diǎn)當(dāng)中只有一個(gè)處于active狀態(tài)。

然后搜尋這個(gè)active點(diǎn)的鄰點(diǎn)。如果直接用nearpoints函數(shù)的話，存在兩個(gè)問題：

（1）自身也會(huì)被搜索到；

（2）無法判別搜索到的點(diǎn)是否被訪問過（visited）。

據(jù)此，我們可以自定義一個(gè)搜索函數(shù)，如nearPts：

function int[ ] nearPts(int index){

}

int[ ]表示函數(shù)返回的類型是一個(gè)整型數(shù)組（void表示無返回值），( )內(nèi)是函數(shù)的變量，同樣要標(biāo)明數(shù)據(jù)類型。這里是根據(jù)點(diǎn)的編號(hào)來搜索，所以是整數(shù)型，變量名稱自行定義，如index。

先不加額外條件，直接用nearpoints函數(shù)搜索所有滿足條件的點(diǎn)。該函數(shù)需要兩個(gè)變量，一個(gè)是當(dāng)前點(diǎn)的坐標(biāo)pos，一個(gè)是最大搜索半徑maxdist。

pos可用point函數(shù)得到，maxdist只要比相鄰點(diǎn)間距稍大即可，可以直接用grid的參數(shù)計(jì)算（sizex/(row-1)）。VEX中可用ch*函數(shù)調(diào)用，見下圖——

nearpoints函數(shù)返回?cái)?shù)組后，對(duì)數(shù)組內(nèi)的點(diǎn)編號(hào)進(jìn)行條件篩選，滿足未被訪問過且不是點(diǎn)自身兩個(gè)條件，才是最終搜尋到的鄰點(diǎn)。這里我用的是foreach函數(shù)，對(duì)于nearPts數(shù)組中的每個(gè)數(shù)值nearPt進(jìn)行判斷，兩個(gè)判斷條件是并列關(guān)系，所以用&&（邏輯與）。

條件1：nearPt != index（不是點(diǎn)自身）；

條件2：inpointgroup(0, "visited", nearPt) == 0（未被訪問過）。

滿足條件的點(diǎn)用append函數(shù)添加到新的數(shù)組targets[ ]中，最后return targets。（照著寫的時(shí)候注意中英文輸入法和標(biāo)點(diǎn)符號(hào)不要弄錯(cuò)）

自定義函數(shù)寫完后我們可以測試一下，比如直接調(diào)用該函數(shù)：

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

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

對(duì)照視圖也可以看到，0號(hào)點(diǎn)的鄰點(diǎn)就是1號(hào)和10號(hào)點(diǎn)。

接下來是在鄰點(diǎn)中隨機(jī)找一個(gè)作為前進(jìn)的目標(biāo)點(diǎn)，使用rand函數(shù)。注意這里的寫法較長：

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

其實(shí)就是括號(hào)比較多，容易搞混而已。因?yàn)?span id="s0sssss00s" class="color-pink-03">rand函數(shù)返回值為0~1，對(duì)于不同長度的鄰點(diǎn)數(shù)組，可用fit01函數(shù)將其擴(kuò)展到0~n，然后取整。下一個(gè)目標(biāo)點(diǎn)的編號(hào)為：

int target = targets[randnum];

當(dāng)然，以上是在找到了鄰點(diǎn)的情況下才執(zhí)行的，所以要加判斷語句：

if ( len(targets) > 0 )

找到目標(biāo)點(diǎn)后active的狀態(tài)會(huì)傳遞到目標(biāo)點(diǎn)，作為下一次搜索的起點(diǎn)。因而組屬性要重新設(shè)置，如下所示——

然后在起點(diǎn)和目標(biāo)點(diǎn)之間連線：

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

還有一種情況是找不到未被訪問過的鄰點(diǎn)，即len(targets) == 0。這時(shí)就要沿著路徑逐點(diǎn)返回，尋找新的active點(diǎn)。所以我們得把走過的路徑記錄下來，做法是用一個(gè)數(shù)組記錄走過的點(diǎn)編號(hào)。

回到前面的set_group節(jié)點(diǎn)，定義一個(gè)stack[ ]數(shù)組，先儲(chǔ)存起始點(diǎn)編號(hào)0。為了方便調(diào)用，將其指定給detail屬性，函數(shù)寫法為：

setdetailattrib(0, "stack", stack);

有了這個(gè)儲(chǔ)存點(diǎn)路徑的數(shù)組，每次找到新的目標(biāo)點(diǎn)就可以添加進(jìn)去：

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

現(xiàn)在繼續(xù)討論沒找到目標(biāo)點(diǎn)時(shí)的情形。先用detail函數(shù)把儲(chǔ)存的stack屬性調(diào)出來。

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

然后沿原路返回，挨個(gè)點(diǎn)搜索鄰點(diǎn)，注意倒序的for循環(huán)條件寫法：

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

}

為什么從len(stack) - 2開始，大家自行思考。還是用自定義的nearPts函數(shù)來搜索，如果找到了新的鄰點(diǎn)，重新設(shè)置active點(diǎn)的位置。然后用break跳出循環(huán)。

最后maze_generation的全部代碼如下（不懂就仔細(xì)琢磨，直到搞懂為止）：

增加solver節(jié)點(diǎn)的Sub Steps可以讓每幀解算更多的步數(shù)。

由此我們就得到了迷宮的路徑，至于怎么在此基礎(chǔ)上做出周圍的墻，可以創(chuàng)建一個(gè)比當(dāng)前grid行列各增加1的網(wǎng)格，然后用判斷相交的節(jié)點(diǎn)intersection analysis。當(dāng)然，最好是剛開始直接用網(wǎng)格的primitive中心作為初始點(diǎn)陣，最后直接用原來的網(wǎng)格線與生成的迷宮線求交點(diǎn)即可。根據(jù)intersection?analysis節(jié)點(diǎn)得到的sourceprim屬性選擇性刪除原來的網(wǎng)格線，相當(dāng)于沿著迷宮行走路線打通了間隔的墻，形成通道。

這樣對(duì)于其他的網(wǎng)格應(yīng)該同樣奏效，感興趣的朋友可以自己嘗試在上述代碼基礎(chǔ)上加以改進(jìn)。今日分享到此為止，感謝閱讀，下回見~