Minecraft 生物 AI 機(jī)制詳解（三）
在前兩篇專欄中，我們介紹了生物 AI 的兩套系統(tǒng)。在這篇專欄中，將會介紹整個生物 AI 系統(tǒng)中的最后一部分：尋路系統(tǒng)。
一. 生物與尋路系統(tǒng)
在所有實體中，只有生物（Mob）具有尋路系統(tǒng)。根據(jù)實體繼承樹，可以看出各種生物都使用了怎樣的尋路系統(tǒng)。
蝙蝠（直接繼承 AmbientCreature，此類直接繼承 Mob）不使用尋路系統(tǒng)，它們的飛行只考慮當(dāng)前點和終點，嘗試以直線飛行到終點，不計算中間經(jīng)過的路徑，所以它們根本不需要尋路系統(tǒng)。并且蝙蝠也沒有使用任何生物 AI 系統(tǒng)。
FlyingMob（子類為惡魂和幻翼）也不使用尋路系統(tǒng)，它們飛行時也只考慮當(dāng)前點和終點，而不計算中間路徑，因此不需要尋路系統(tǒng)。與蝙蝠不同的是，它們使用了目標(biāo)系統(tǒng)作為 AI 系統(tǒng)。
史萊姆和巖漿怪同樣不使用尋路系統(tǒng)，也不計算中間路徑。它們使用了目標(biāo)系統(tǒng)。
末影龍具有復(fù)雜的尋路系統(tǒng)和 AI 系統(tǒng)，在這篇專欄內(nèi)不會涉及。
其余所有生物都繼承于 PathfinderMob，使用接下來所介紹的尋路系統(tǒng)。
二. 路徑與路徑節(jié)點
路徑是決定生物移動的關(guān)鍵數(shù)據(jù)，也是尋路系統(tǒng)的計算結(jié)果。它具有下面這些字段：
target：路徑的目標(biāo)位置。
nodes：路徑節(jié)點列表。
reached：這條路徑是否能到達(dá)目標(biāo)位置。
distToTarget：目標(biāo)位置與路徑終點的曼哈頓距離。如果整條路經(jīng)不存在節(jié)點，則為單精度浮點數(shù)的最大值。
nextNodeIndex：下一個節(jié)點的位置。用于判斷當(dāng)前路徑的走動過程和判斷是否已經(jīng)走完這條路徑。
從字段定義中可以看出，路徑的目標(biāo)位置不一定是路徑節(jié)點列表的終點。這是因為一條路徑可以只需要到達(dá)目標(biāo)位置的附近，而不需要最后完全站在目標(biāo)點上。
路徑由一個個的路徑節(jié)點構(gòu)成，節(jié)點包含下面的屬性：
g（Yarn 名稱為 penalizedPathLength）：從路徑起點到本節(jié)點的尋路代價。
h（Yarn 名稱為 distanceToNearestTarget）：本節(jié)點的啟發(fā)函數(shù)值（Heuristic）。計算上是當(dāng)前節(jié)點與最近目標(biāo)位置的歐幾里得距離或它的1.5倍，下文會詳細(xì)解釋。
f（Yarn 名稱為 heapWeight）：本節(jié)點的綜合優(yōu)先級。計算上是節(jié)點在二叉堆內(nèi)的權(quán)重，此項由前兩項相加計算而來。為了節(jié)省計算資源，節(jié)點被存放到一個二叉堆（openSet）中，并且這個堆是一個小根堆。
x、y、z：節(jié)點的方塊位置。
closed：本節(jié)點是否“閉合”，也就是是否已經(jīng)計算過。
walkedDistance：從起點經(jīng)路徑到達(dá)此節(jié)點的距離。
costMalus：本節(jié)點的尋路代價。
type：本節(jié)點的方塊路徑類型。
cameFrom：本節(jié)點連接的上一個節(jié)點，主要用于重構(gòu)路徑。
heapIdx：節(jié)點在二叉堆中的序號，用于索引和檢查是否在二叉堆內(nèi)。如果在堆內(nèi)，則不小于0。
hash：節(jié)點的哈希值。
簡單介紹完這兩種數(shù)據(jù)結(jié)構(gòu)后，我們可以正式進(jìn)入尋路計算的部分了。
三. 方塊路徑類型與方塊尋路代價
世界上的方塊情況是非常復(fù)雜的，為了減少計算，MC 把方塊映射為了對應(yīng)的方塊路徑類型并賦予了這些方塊路徑類型的尋路代價。
方塊路徑類型在 BlockPathTypes 中定義，每個枚舉值都有其對應(yīng)的基礎(chǔ)尋路代價。
所有小于 0 的代價都代表生物不能跨越此方塊進(jìn)行尋路。有些生物會覆寫某些方塊路徑類型的代價，從而使生物可以跨越這些方塊。
方塊對應(yīng)的具體方塊路徑類型不僅由方塊決定，還由生物本身決定。生物計算方塊路徑類型的方法是 NodeEvaluator::getBlockPathType，而這個方法是一個抽象方法，共有 5 個實現(xiàn)。接下來我們會一一介紹。
WalkNodeEvaluator::getBlockPathType
首先我們來介紹地面節(jié)點標(biāo)記器，這個標(biāo)記器是絕大部分生物使用的標(biāo)記器。
上面這段代碼是方塊與方塊路徑類型的初步映射，從這里我們可以看出下面的映射關(guān)系：
如果方塊是空氣，則為 OPEN。
如果方塊是活版門/睡蓮/大型垂滴葉，則為 TRAPDOOR。
如果方塊是細(xì)雪，則為 POWDER_SNOW。
如果方塊是仙人掌或甜漿果，則為 DAMAGE_OTHER。
如果方塊是蜂蜜塊，則為 STICKY_HONEY。
如果方塊是可可果，則為 COCOA。
如果方塊是凋零玫瑰和滴水石錐，則為 DAMAGE_CAUTIOUS。
如果方塊是熔巖，則為 LAVA。
如果方塊是火/靈魂火/巖漿塊/點燃的（靈魂）營火/熔巖煉藥鍋，則為 DAMAGE_FIRE。
如果方塊是門，則有三種情況：開著的門 -> DOOR_OPEN；關(guān)著的木門 -> DOOR_WOOD_CLOSED；關(guān)著的鐵門 -> DOOR_IRON_CLOSED。
如果方塊是任何一種鐵軌，則為 RAIL。
如果方塊是樹葉，則為 LEAVES。
如果方塊是柵欄/墻/關(guān)著的柵欄門，則為 FENCE。
如果方塊不能地面尋路（絕大部分是碰撞箱完整方塊，也有一些不完整方塊比如鐵砧等也是不能地面尋路的方塊），則為 BLOCKED。
如果方塊是水，則為 WATER。
如果不屬于上面任何一種情況，為 OPEN。
初步確定方塊路徑類型后，還要再次檢查這個方塊下方和周圍的方塊以明確這個位置真正的方塊路徑類型。
可以看到一個方塊位置的方塊路徑類型是這樣計算的：
如果本方塊位置的初始方塊路徑類型不是 OPEN，則采用本方塊位置的初始方塊路徑類型作為最終的方塊路徑類型。
如果本方塊位置的初始方塊路徑類型是 OPEN，則要檢查下方方塊：
如果下方方塊是 OPEN/WATER/LAVA，則最終類型為 OPEN。
如果下方方塊是 DAMAGE_FIRE/DAMAGE_OTHER/STICKY_HONEY/DAMAGE_CAUTIOUS，則與下方方塊相同。
如果下方方塊是 POWDER_SNOW，則最終類型為 DANGER_POWDER_SNOW。
其他情況，為 WALKABLE，但是要參與下面的周圍方塊額外檢查。
如果本方塊位置為 WALKABLE，則要進(jìn)行周圍3x3x3方塊的額外檢查。檢查順序是從 XYZ 最小的點開始，按照 ZYX 分別增大到 XYZ 最大點，檢查到特殊情況就退出循環(huán)，如果沒有遇到特殊情況就保持為 WALKABLE。特殊情況有：
如果周圍方塊有仙人掌/甜漿果，則為 DANGER_OTHER。
如果周圍方塊有火/靈魂火/巖漿塊/點燃的（靈魂）營火/熔巖煉藥鍋，則為 DANGER_FIRE。
如果周圍方塊有水，則為 WATER_BORDER。
如果周圍方塊有凋零玫瑰和滴水石錐，則為 DAMAGE_CAUTIOUS。
由于生物本身具有大小，有些生物的寬度超過了 1 格，所以只計算一個方塊位置的路徑類型是不夠的。getBlockPathTypes 方法給出了當(dāng)前位置和生物可能接觸位置的路徑類型。
在得到這些方塊位置的路徑類型后，還需要針對生物的特性進(jìn)行路徑類型的轉(zhuǎn)換。
上面代碼的含義為：
如果生物可以打開門并且可以走過門，關(guān)著的木門會被轉(zhuǎn)變?yōu)?WALKABLE_DOOR。
如果生物不可以走過門，則門會變?yōu)?BLOCKED。
如果方塊位置上是鐵軌類方塊，并且生物對應(yīng)的方塊或它下面的方塊不是鐵軌類方塊時，鐵軌變?yōu)?UNPASSABLE_RAIL。
從這段代碼中可以看出，如果生物正站在鐵軌上，則所有的鐵軌都會被認(rèn)為可通過，而不是平常的不可通過。也就是說，這個可走過鐵軌的判定不是這個方塊周圍的方塊決定的，而是生物站的位置決定的。
最后，將代碼整合起來就得到了生物用于尋路計算的方塊路徑類型。
這段代碼可以看出：
如果方塊路徑類型集合內(nèi)含有 FENCE，則認(rèn)為這個方塊路徑類型就是 FENCE。UNPASSABLE_RAIL 同理。
嘗試找出擁有最大代價的方塊路徑類型作為最終路徑類型。如果路徑類型本身已經(jīng)不可尋路（代價小于 0），則直接返回這個路徑類型。
如果本方塊位置上的類型是 OPEN、最大代價為 0 并且生物本身寬度小于 1，則返回 OPEN。
否則返回找到的擁有最大代價的路徑類型。
FlyNodeEvaluator::getBlockPathType
這個類繼承 WalkNodeEvaluator，與 WalkNodeEvaluator 計算的不同在于最后一步中不考慮 UNPASSABLE_RAIL 的直接返回判定，并且返回 OPEN 時不需要生物本身寬度小于 1。
AmphibiousNodeEvaluator/FrogNodeEvaluator::getBlockPathType
繼承 WalkNodeEvaluator，代碼也與 WalkNodeEvaluator 相同。
SwimNodeEvaluator::getBlockPathType
這個類用于完全的水生生物的尋路。它的計算要比前面幾個更簡單。
可以看到，水生生物尋路只有 3 種類型：
如果方塊位置上實體范圍內(nèi)是空氣并且下方可水體尋路（通常是含水方塊），則為 BREACH。
如果方塊位置上實體范圍內(nèi)含有不含水方塊，則為 BLOCKED。
如果方塊位置上本身可以水體尋路，則為 WATER。
否則，為 BLOCKED。
如果生物本身不覆寫方塊路徑類型，則使用方塊路徑類型的基礎(chǔ)代價。生物覆寫方塊路徑類型由 setPathfindingMalus 方法決定。例如在監(jiān)守者中：
監(jiān)守者把 UNPASSABLE_RAIL 類型的代價調(diào)整到了 0，也就使得它可以跨越鐵軌尋路。其他類型的代價也同樣調(diào)低或者調(diào)整到 0 及以上，這使得它可以跨越比其他生物更多的方塊類型。
四. 生成路徑
介紹方塊路徑類型和代價后，我們可以正式講解生成路徑的過程。
生成路徑直接或間接使用了 PathNavigation::createPath，它有幾個基本參數(shù)（此處使用 Yarn Mapping）：
positions：尋路目標(biāo)列表。
range：尋路額外范圍，防止尋路時節(jié)點超出尋路空間。
useHeadPos：使用生物的頭部坐標(biāo)尋路而不是使用腳部。
distance：路徑終點與目標(biāo)的距離。如果路徑終點與目標(biāo)的曼哈頓距離小于此值，則認(rèn)為已經(jīng)到達(dá)終點。
followRange：最大尋路半徑，使用歐幾里得距離。如果路徑?jīng)]有到達(dá)任何目標(biāo)，并且終點已經(jīng)超出這個半徑，則路徑無效。
這 5 個基本參數(shù)控制了生物尋路的范圍和目標(biāo)，這個方法的具體代碼如下：
從上方代碼中，可以看出：
如果目標(biāo)為空，則直接返回空。
如果生物本身已經(jīng)低于建筑高度，也不進(jìn)行尋路。
如果尋路系統(tǒng)目前不能更新路徑，則返回空。
如果當(dāng)前正在執(zhí)行路徑，且生物還沒有根據(jù)路徑走到終點，如果之前的目標(biāo)與現(xiàn)在的目標(biāo)一致或含有之前的目標(biāo)，則返回之前的路徑進(jìn)行復(fù)用。
如果不滿足上面的情況，則開始一次尋路計算。
開始尋路計算，會先計算整個尋路空間的中心點，通常使用生物的腳部，也可以使用頭部。尋路空間的半徑由 range 和 followRange 相加得到，保證在尋路過程中不會出現(xiàn)路徑節(jié)點超出尋路空間而造成錯誤計算（如果尋路超出尋路空間，尋路空間外的世界會被認(rèn)為是平原空區(qū)塊）。之后會將參數(shù)傳入具體的 PathFinder 中具體計算路徑。如果路徑計算成功則設(shè)置當(dāng)前的目標(biāo)和路徑。
PathFinder 是尋路的核心類，它只用于生成路徑。被上方調(diào)用的方法代碼如下：
尋路開始時，PathFinder 清空 openSet、重置 NodeEvaluator，并計算尋路起始點。不同的節(jié)點標(biāo)記器會導(dǎo)致尋路起始點不同，以 WalkNodeEvaluator 舉例：
根據(jù)上方的代碼，可以看出：
如果生物可以站在某個流體上，并且生物就在這個流體內(nèi)，則起始點向上移動到流體表面。
如果生物可以主動浮起并且生物在水中，則起始點向上移動到水體表面。
如果生物在地面上，則使用腳部方塊位置。
如果生物位于空氣或者可尋路方塊中，則將起始點向下移動到最高不可地面尋路方塊的上方。
如果起始點無效（對應(yīng)方塊類型是 OPEN 或?qū)ぢ反鷥r為 -1 使得不可尋路），則尋找生物腳下周圍對應(yīng)高度的方塊，以找到的第一個有效點作為最終起始點。
如果前一個條件最終沒有找到起始點或原起始點本身有效，則返回該起始點。
找到起始點后，就可以根據(jù)這個起點開始下面的尋路計算。
MC 使用的尋路算法是 A* 算法，它的算法是計算一個權(quán)重 f，每次尋路時找到擁有最小 f 值的節(jié)點進(jìn)行嘗試。f 的定義如下：
其中 g 是目前節(jié)點到起點的加權(quán)距離，h 是目前節(jié)點到最近終點的距離。這三個值分別對應(yīng)了 Node 數(shù)據(jù)結(jié)構(gòu)的三個字段 f、g、h。
尋路算法的核心代碼位于 PathFinder::findPath 的一個重載方法，代碼如下：
根據(jù)上方的代碼，可以看出這個尋路算法的流程：
初始化起點，將起點節(jié)點的 g 設(shè)置為 0，h 設(shè)置為到最近目標(biāo)的歐幾里得距離。
重置 openSet，在 openSet 中放入起點。
設(shè)置邊界條件訪問節(jié)點最大數(shù)量，這個值通常是跟隨距離的 16 倍。
開始循環(huán)。
從二叉堆 openSet 中取出 f 值最小的節(jié)點，并閉合這個節(jié)點（防止二次訪問）。檢查節(jié)點是不是已經(jīng)處于某個目標(biāo)的可達(dá)范圍內(nèi)。如果是，將目標(biāo)的終點節(jié)點設(shè)置為本節(jié)點，并把可達(dá)目標(biāo)放入 reachedTargets。
如果 reachedTargets 不為空，結(jié)束循環(huán)。
如果節(jié)點與初始節(jié)點的歐幾里得距離超出了跟隨距離，則此節(jié)點無效，繼續(xù)循環(huán)。
計算節(jié)點旁邊的可達(dá)節(jié)點（鄰居）。對于每個鄰居，將它們的節(jié)點 walkedDistance 設(shè)置為本節(jié)點與鄰居距離和本節(jié)點 walkedDistance 的和。并計算到達(dá)鄰居的代價，即本節(jié)點的代價、節(jié)點間的距離和鄰居節(jié)點方塊路徑代價的總和。如果鄰居節(jié)點超出了跟隨距離，則鄰居節(jié)點無效；如果鄰居節(jié)點已經(jīng)被記錄在二叉堆中，而鄰居節(jié)點原先的 g 小于從現(xiàn)在節(jié)點計算的代價，則也不進(jìn)行接下來的鄰居節(jié)點更新。
如果鄰居節(jié)點滿足上一條所有條件，則將鄰居節(jié)點的 g 設(shè)置為當(dāng)前代價，將鄰居節(jié)點的來源節(jié)點設(shè)置為本節(jié)點，將鄰居節(jié)點的 h 設(shè)置為鄰居節(jié)點和最近目標(biāo)歐幾里得距離的 1.5 倍。更新各個目標(biāo)的最佳終點節(jié)點，計算鄰居節(jié)點的 f，如果鄰居節(jié)點已經(jīng)在 openSet 中，則修改堆內(nèi)權(quán)重，否則將鄰居節(jié)點放入二叉堆中。
循環(huán)結(jié)束后，如果有到達(dá)的目標(biāo)，則重建所有已到達(dá)目標(biāo)的路徑，并挑選節(jié)點數(shù)量最少的路徑作為最終路徑；如果沒有到達(dá)任何目標(biāo)，重建所有目標(biāo)的路徑，挑選距離目標(biāo)最近且節(jié)點數(shù)量最少的路徑作為最終路徑。
可以看到，啟發(fā)函數(shù)值 h 大于真實距離值 50%，這代表了這個尋路算法不一定能找到最優(yōu)解，但速度會更快。
鄰居節(jié)點的選擇取決于節(jié)點評估器，計算節(jié)點周圍 8 個位置是否可用。以地面節(jié)點評估器舉例，對于一個方向上的鄰居節(jié)點它是這樣計算的：
上面的代碼中，xyz 代表的是要進(jìn)行評估的鄰居位置；maxUp 是生物一次性能上升的最大高度，如果當(dāng)前路徑類型不是 STICKY_HONEY 并且節(jié)點上方方塊的路徑類型代價大于 0，則為 1 與生物 maxUpStep 的較大值，否則為 0；nowFloorLevel 是當(dāng)前節(jié)點位置的地面高度，如果方塊沒有碰撞箱則為 0，否則為碰撞箱高度；walkDir 是從當(dāng)前節(jié)點走向鄰居節(jié)點的方向，正方向的鄰居使用對應(yīng)的正方向，斜向的鄰居只使用南北方向；nowType 是當(dāng)前節(jié)點的路徑類型。這個方法的具體流程是這樣的：
如果當(dāng)前檢查節(jié)點的上表面高度與當(dāng)前地面高度的差大于生物能跳起的高度，直接返回 null。生物能跳起的高度為 1.125 與生物 maxUpStep 的較大值。
如果當(dāng)前檢查節(jié)點的尋路代價不小于 0，則設(shè)置為鄰居節(jié)點。
如果路徑類型是 FENCE、DOOR_WOOD_CLOSED 或 DOOR_IRON_CLOSED 這些有碰撞的路徑類型，并且生物到鄰居節(jié)點會被這些方塊的碰撞箱阻擋，則將鄰居節(jié)點設(shè)置為空。
生物被阻擋的條件是：節(jié)點的最小點與生物的最小點連線，測試生物在這條線上是否會與方塊碰撞箱碰撞（具體代碼 canReachWithoutCollision）。下圖給出了僵尸（寬度 0.6）和關(guān)閉的門的碰撞示例。
從這張圖中可以看出向北、西、南的射線都被門碰撞箱阻擋，所以這三個方向不能作為僵尸的有效鄰居節(jié)點。當(dāng)僵尸向東走動一點，就有可能使射線碰撞范圍離開門的碰撞箱，從而使北面也變?yōu)橛行?，但由于這個計算本身是實體碰撞箱在某些位置上進(jìn)行檢測，所以實際移動范圍比視覺上射線移動范圍要更大。如果門換了一個方向，比如說換為東側(cè)的門，這時候只有東面會被遮擋，其他三個方向都可以作為有效的節(jié)點。同時，因為這個計算是根據(jù)生物目前所在位置計算的，所以可能會造成一些尋路上的問題。
這個機(jī)制在 22w16a 時被修改為現(xiàn)在的行為，在此之前使用的是生物碰撞箱底面中心點，而不是最小點，并且在之前只有 FENCE 類型才有效。
如果上面計算出了不為空的鄰居節(jié)點，則判斷是否為 WALKABLE，對于兩棲類生物還會額外檢查是否為 WATER，如果通過，就返回這個鄰居節(jié)點。
如果鄰居節(jié)點現(xiàn)在為空，或者鄰居節(jié)點的代價小于 0（不可尋路），并且滿足下面所有條件：maxUp 大于 0（生物可以嘗試向上查找可尋路方塊）、生物可以跨越柵欄或鄰居節(jié)點的類型不是 FENCE、鄰居節(jié)點不是 UNPASSABLE_RAIL、TRAPDOOR 或 POWDER_SNOW，則檢查現(xiàn)在節(jié)點位置的上方方塊，遞歸查找。如果不滿足以上條件，鄰居節(jié)點設(shè)置為空。如果遞歸查找發(fā)現(xiàn)了合適的位置，并且不滿足下面任意一條條件：發(fā)現(xiàn)的節(jié)點類型是 OPEN 或者 WALKABLE，生物寬度小于 1，生物會與上升路徑中的方塊碰撞，鄰居節(jié)點就會被設(shè)置為查找到的位置，否則設(shè)置為空。
如果生物不是兩棲生物，也不會自動飄浮，如果路徑類型為 WATER，則嘗試向下查找，直到找到一個類型不是 WATER 的節(jié)點返回。如果查找超出了建筑下限，則進(jìn)入下一步。
如果路徑類型是 OPEN，則嘗試向下查找，查找的最大距離是生物可容許的最大下落高度。通常來說這個高度是 3，對于當(dāng)前有攻擊目標(biāo)的生物是
，其中 h 是當(dāng)前生命值，h_max 是最大生命值，d 是數(shù)字形式的難度，和平到困難分別代表了 0-3，如果計算出來的值小于 3，則認(rèn)為是 3。這個公式可以看出生物總是嘗試讓自己不會從能讓自己受傷到三分之一血量的地方向下落，難度也影響了生物最大容許的下落高度。如果查找高度已經(jīng)超過了容許下落高度，或查找到了建筑下限，則返回 BLOCKED 節(jié)點；如果找到了一個不是 OPEN 且代價不小于 0 的位置，則將鄰居節(jié)點設(shè)置為這個位置；否則返回 BLOCKED 節(jié)點。
如果當(dāng)前位置是路徑類型是 FENCE、DOOR_WOOD_CLOSED 或 DOOR_IRON_CLOSED，并且鄰居節(jié)點仍然為空，則返回已經(jīng)閉合的節(jié)點。
最后，返回計算得出的鄰居節(jié)點，無論是否為空。
獲得鄰居節(jié)點后，還要在判斷一次這些節(jié)點是否有效。直接相鄰的節(jié)點和對角相鄰的節(jié)點判斷不相同。
首先判斷直接相鄰的鄰居節(jié)點：
直接相鄰的鄰居節(jié)點必須是非空且非閉合的，并且要求鄰居節(jié)點本身的代價不小于 0 可尋路或本節(jié)點本身不可尋路。如果不滿足上面的條件，鄰居節(jié)點無效并不會被計算。
由于這個方法內(nèi)部允許了本節(jié)點不可尋路時會忽略鄰居節(jié)點是否不可尋路，所以會造成下面的結(jié)果：生物檢查下落時失敗是在容許下落的最低位置上放置 BLOCKED 路徑類型節(jié)點，而不是返回一個 null，這也就滿足了第一個條件：非空非閉合。如果生物起點就已經(jīng)是不可尋路的，即使下一個節(jié)點是 BLOCKED 生物也可以選擇這個節(jié)點。同樣，由于 BLOCKED 節(jié)點也不可尋路，它也會影響下一個節(jié)點的選取，如此循環(huán)，就讓生物可以下落的高度不斷疊加。
更一般的來說，如果起點不可尋路，那么之后的節(jié)點都可以是不可尋路的，直到遇到一個可尋路節(jié)點。
之后判斷對角相鄰的鄰居節(jié)點：
對角相鄰節(jié)點判斷更加嚴(yán)格，對角方向上與本節(jié)點直接相鄰的兩個直接鄰居節(jié)點也要被計算。如果這三個鄰居節(jié)點有一個為空或為 WALKABLE_DOOR，那么對角節(jié)點就無效。如果對角節(jié)點本身閉合，也無效。如果對角節(jié)點本身不可尋路，節(jié)點無效。如果兩個直接節(jié)點是 FENCE 并且生物本身寬度小于 0.5，則對角節(jié)點有效。兩個直接節(jié)點高度小于本節(jié)點或本身可尋路時，對角節(jié)點也有效。
五. 應(yīng)用路徑
現(xiàn)在我們已經(jīng)了解了路徑是怎么生成的了，那么這些路徑是怎么應(yīng)用的呢。
1. 生物行走
在各種 Goal 和 Behavior 中，如果生物需要走到什么地方，就會調(diào)用 PathNavigation::moveTo 方法。
絕大部分的走動尋路的到達(dá)半徑都是 1。在路徑創(chuàng)建后，如果生物是追蹤一個方塊位置尋路而沒有任何路徑可以到達(dá)，那么當(dāng)前路徑也會被打斷。如果新的路徑和當(dāng)前路徑不同，新的路徑會替換當(dāng)前的路徑。如果當(dāng)前路徑已經(jīng)結(jié)束（nextNodeIndex 大于等于節(jié)點數(shù)量），返回 false。接下來進(jìn)行路徑的二次處理，檢查路徑節(jié)點數(shù)量是否超過 0，設(shè)置當(dāng)前的阻擋檢查數(shù)據(jù)。路徑的二次處理如下：
路徑二次處理主要是處理煉藥鍋的相關(guān)行為，讓生物能正確的運動。在子類 GroundPathNavigation 中，還定義了躲避太陽的代碼。如果會躲避太陽的生物（骷髏類，僵尸不會躲避太陽）的路徑一部分的節(jié)點被太陽直射，則路徑被切斷。
在設(shè)置路徑后，生物就可以按照這個路徑每一刻計算怎么按照這個路徑行走。
在這里可以看出生物隨著路徑行走的邏輯：
如果路徑需要被重新計算（路徑上的方塊發(fā)生了變化，并且上一次重新計算的時間大于 20tick），則重新計算一次路徑。
檢查路徑是否不存在或者已經(jīng)結(jié)束，如果是，則不進(jìn)行下面的跟隨。
如果生物可以更新路徑（和前文創(chuàng)建路徑是一個檢查更新路徑的方法，對于地面尋路的生物來說，條件是在地面上/水中或本生物是乘客），則跟隨路徑；否則，檢查現(xiàn)在生物的位置是否高于下一個節(jié)點的路徑，并且下一個節(jié)點的路徑與現(xiàn)在生物的方塊位置相同，如果是，路徑節(jié)點前進(jìn)一次。
再次檢查生物路徑是否已經(jīng)結(jié)束，如果是，不進(jìn)行下面的移動。
找到生物的下一個行走位置，并使用 MoveControl 執(zhí)行對應(yīng)的移動。
跟隨路徑是檢查生物是否已經(jīng)到達(dá)路徑的下一個節(jié)點的方法，防止生物不知道現(xiàn)在在什么位置和下一個位置在哪里。
生物當(dāng)自身離下一個節(jié)點的水平方向上的切比雪夫距離小于一定值，且垂直差距不超過 1 格時會認(rèn)為自身已經(jīng)到達(dá)下一個節(jié)點。當(dāng)生物寬度大于 0.75 時，這個距離是生物本身寬度的一半，否則為 0.75 減去生物本身寬度的一半。以僵尸舉例，這個距離是 0.45。另一種到達(dá)下一個節(jié)點的方式是有限制的：下一個節(jié)點的類型不能是 DANGER_FIRE、DANGER_OTHER 或 WALKABLE_DOOR 且距離 2 格以內(nèi)，生物可以直接移動到下一個節(jié)點，或下下個節(jié)點中心的距離小于下一個節(jié)點中心的距離/到下一個節(jié)點中心距離小于 0.5 并滿足方向偏離超過 90 度。
檢查是否到達(dá)下一個節(jié)點后，生物還要進(jìn)行一次阻擋與超時檢測。阻擋與超時檢測是防止生物在無法到達(dá)的路徑上一直嘗試行走，造成其他 AI 行為停滯。
阻擋檢測每 100tick 執(zhí)行一次，檢測上次記錄的位置和現(xiàn)在的位置是否沒有太大的變化。如果是，則認(rèn)為生物已經(jīng)被不可跨越方塊阻擋，路徑被強(qiáng)制停止。
超時檢測的計時器超時極限為 3 倍當(dāng)前位置與下一個節(jié)點的位置的距離和速度的商。與阻擋檢測類似，一旦生物在指定時間內(nèi)沒有到達(dá)下一個節(jié)點，則認(rèn)為節(jié)點不可達(dá)，路徑失效。
2. 檢查有效路徑
在一些行為中，生物需要檢查自己是否能到達(dá)一個位置，這通常是一個行為的先決條件。檢查是否有一條有效的路徑需要直接調(diào)用上文已經(jīng)詳細(xì)說明的 PathNavigation::createPath，它的返回值代表了生物是否能成功找到有效路徑：
如果返回為空，則說明不存在任何可達(dá)路徑。
如果返回了 canReach 為 false 的路徑，則說明能找到一條接近目標(biāo)位置的路徑，但是卻沒有辦法達(dá)到目標(biāo)的到達(dá)半徑內(nèi)。
如果返回了 canReach 為 true 的路徑，說明能找到一條到達(dá)目標(biāo)到達(dá)半徑內(nèi)的路徑。
絕大多數(shù)行為只檢查能不能找到路徑，而不檢查可達(dá)性。檢查可達(dá)性的行為有：山羊的長跳和沖撞、村民繁殖、村民讓出工作站點和嗅探獸挖掘，這些行為要求生物必須能走到/不能走到（實際上可以不走）對應(yīng)位置才能執(zhí)行。
到這里專欄的長度已經(jīng)很長了，也基本說明了尋路系統(tǒng)的運作原理，比較詳細(xì)的說明了地面尋路。對于其它的尋路，代碼都和地面尋路相似，只是在鄰居節(jié)點挑選、方塊路徑類型判定上等有差異。
有錯誤可以在下方指出。
源代碼使用 Mojang Mapping，版本 1.19.4~23w14a，反編譯器 CFR 0.152。
自動化反編譯倉庫：Nickid2018/GitMCDecomp。
