HPA與NavigationMesh相關資料

https://blog.csdn.net/tchenjiant/article/details/49510845

unity尋路——一勞永逸地解決尋路問題

譯者：trcj

原文：http://www.ai-blog.net/archives/000152.html

通常我都會盡量避免對業內游戲產品或開發者們評頭論足。

但這回我不得不破一次例。

我要討論一些關于尋路的問題。為了證明這些問題至今仍然存在，我本著娛樂的精神制作了這個視頻。

（譯注：原視頻缺失。）

所有片段都錄自對應游戲的最新版本。

正如你所看到的，我們在構建一個健壯的尋路系統上還有很長的路要走，這些方方面面的問題甚至存在于一些頂級產品中。

并不是說這是當今游戲的通病。因為時下許多游戲確實擁有高質量的尋路，而且視頻里的尋路大部分時間也表現良好。

但是仍有太多的游戲還在使用九十年代的方法。

（說明：為了錄制之便，視頻里出現的大多數游戲都屬于PC平臺角色扮演類型，因為當時我的電腦上就只安裝了這些游戲。事實上，這些問題不限于任何類型或平臺，甚至在主機平臺的游戲里也多有出現。）

就我所知，大多數游戲使用路徑點（waypoint graph）來實現尋路，它正是我們所碰到的這些問題的首因。

我認為路徑點這一做法已經過時。這篇文章將闡述路徑點的缺陷，同時通過五條主要論據介紹另一種更為可行的方法。

我曾經在八、九十年代使用過路徑點尋路，當時我們面對諸多苛刻的技術限制，不得不舍棄很多東西。

現如今我們身處一個億萬美元的產業之中。面對的平臺擁有多核處理器和與日俱增的海量內存，完全具備了實現一個合理的尋路系統的條件。

業內AI開發者中有一句話：“尋路已不是問題。”我們有針對各種尋路問題的各種解決辦法，只不過不常使用而已。

而我想說的是，沒有任何理由不一勞永逸地總結出一套放之四海而皆準的尋路方案。

為什么路徑點不適合用于尋路

讓我們來看看一個路徑點系統究竟是什么樣子。下面是魔獸世界里暴風城一隅。

圖1.?魔獸世界暴風城一隅

這是該區域典型的路徑點分布圖。

圖2.?同一區域的路徑點分布圖

現在我們介紹另一種實現方法，使用凸多邊形來表示AI單位可以移動的范圍。這種方式可以為AI提供大量的關于周圍世界的額外信息，賦予其極大的靈活性。

這種尋路網格（navigation mesh）看上去是這個樣子的：

圖3.?使用尋路網格來標識的同一個區域

現在，我們來逐一列舉路徑點尋路的五大缺陷。

1.?一些游戲需求的路徑點數目過大。

大型開放性區域通常需要散布大量的路徑點來實現豐富的移動效果。

如果使用尋路網格，數個多邊形足矣，且尋路更為快捷。

舉個例子。下圖展示了魔獸中的重鎮“哈蘭”。這是一大塊開放型區域，NPC漫-游其間。為了方便演示，我移除了鎮子中的旗幟、噴泉。

圖4.?哈蘭（略修改）

在路徑點系統中，我們需要放置眾多路徑點以覆蓋整個地區。即便如此，NPC仍會選擇到一些曲曲折折的路徑，除非我們繼續添加比下圖多得多的路徑點。

圖5.?覆遍路徑點的哈蘭

如果使用尋路網格，寥寥數個多邊形即可描述整片區域。

圖6.?尋路網格描述的哈蘭

尋路網格使我們免于遍歷眾多的路徑點，效率自然也提高很多。

2.?路徑點讓結果路徑呈現“鋸齒狀”的彎折。

路徑點把尋路單位限制在你創作的路徑圖中。這意味著單位始終沿著固定軌跡運動，并且幾乎永遠不會選擇由A到B的最短路徑，因為最優的直線路徑很少能與路徑圖吻合。

這將導致不自然的尋路，尋路單位走動時會在一段鋸齒狀的曲折路徑上忽左忽右。

以A至B取徑點為例。

圖7.?哈蘭的兩個路徑點

這是按照前述路徑點圖得出的取徑結果。

圖8.由A至B使用路徑點進行取徑

可以看出，AI單位沿著黃色的路徑行走時會經歷數次彎折。

理想情況下，在我們選好路徑后，可以做一些平滑處理，比如沿著路徑點構建出一條Catmull-Rom樣條曲線。

問題在于，路徑點網絡沒有任何線路以外的信息，很難安全可信地對路徑進行平滑調整。

試想一下在線路之外如何創建出一條平滑路徑，而保證這條新路徑不會引導你摔下索橋。

你或許會尋思是否有其他方法可循，不幸的是，在路徑點的體制下，沒有。如果我們冒險偏離路線哪怕一點，都有可能釀成墜崖或撞墻的慘劇。我們像路徑點圖一樣對路線之外的東西一無所知。

所以安全起見，我們只好采用最悲觀的策略，老老實實待在路線中。

如果使用尋路網格，取徑結果則會大為不同：

圖9.?在尋路網格中由AB漫-游

因為能夠通過尋路網格得知尋路單位的安全活動范圍，我們得以以任意方式調整取徑結果，只要保證在網格之內即可。

（“哦，”你可能會說，“但是我可以在路徑點圖中開啟更多的連接來達到平滑目的！如果需要NPC直行，我會打開鎮中所有節點之間的連接。”

“但是這會導致數據指數級的爆炸，”我回應…“在這個例子里或許額外40或50連接已經足夠。但是隨著區域增大，你需要應付的節點間的連接數會直逼O(N^2)。”

“好吧，”你又說，“那樣的話，我就把相鄰三點圍成的區域標記為‘開放’，這樣AI就可以在這塊區域中自由行動啦。”

“這正是一個多邊形…而你剛創建了一個尋路網格，”我提醒道）。

尋路網格包含活動范圍的精確大小，這意味著可以隨意使用樣條曲線平滑我們的路徑，唯一要注意的就是保持曲線在網格內。

回到暴風城一例，下圖分別展示了路徑點取徑（紅色）和經過平滑處理的尋路網格取徑（藍色）結果。

圖10.?路徑點取徑（紅色）及經平滑處理的尋路網格取徑（藍色）

3.?路徑點取徑不允許路徑修正，這使得動態避開障礙物變得極其困難。

路徑點圖缺少路線之外的數據，即便對于偏離分毫的區域也無法給出參考信息。

這意味著你不大可能通過修改路徑來動態避開障礙物。

想象一個擱置在暴風城石橋上的沉重大木箱。

使用路徑點尋路，我們將束手無策。如果箱子橫在路線上，我們完全不知道從左邊還是右邊繞開它，如果箱子完全擋住了去路，我們也不知道是否應該改道。我們只能猜，盼望不要落入水中。

圖11.?難以移動的大箱子橫在橋當中

如果使用尋路網格，事情就好辦多了。參照網格提供的活動范圍，我們對箱子進行碰撞檢測，調整路徑繞過障礙，并可以始終保持在網格的安全區域中。

圖12.?繞過箱子行進

當然，你也可以在路徑點圖中新加路徑點來解決問題，直到你的路徑點像野草一樣稠密（而你的尋路性能像蜜糖一樣粘滯）。

不知你意下如何，我倒是寧可在大多邊形里運行我的A*算法，也不愿在數以百計的路徑點中。

4.?路徑點不支持尋路參數不同的多個單位。

尋路點不支持尋路單位具有不同的高度、寬度、旋轉角度等尋路參數。這意味著你不能僅用一張統一的路徑圖來匹配游戲中所有的單位類型。

當說起AI尋路，一般我們會想到角色在游戲中漫-游。

但是AI系統需要控制多種尋路單位---坦克、飛機、輪船、氣墊船、摩托車、獸人、地精、龍、伐木巨人、浮空游蕩的生物、等等。很多時候，單位需要根據各自的大小、體型和運動參數來尋路。這些都需要尋路系統給予支持。

舉個例子。設想沙漠中有一座掩體，四周環繞沙袋。

圖13.?沙漠中的掩體

如果是一名士兵，他大可以沿著沙袋行走（下圖紅色箭頭）。

但如果是一輛裝甲坦克，就不得不與沙袋保持一定距離以避免碰撞（藍色箭頭）。

圖14.?士兵和坦克沿沙袋行進的路線

使用路徑點方法，你無法僅使用一張路徑圖同時處理兩種情況。你需要為坦克和士兵各建一張圖。如果加入一個摩托車單位，你還要再建一張。以后每加入一個不同單位你都得新建一張。

如果使用尋路網格，就簡單多了。

圖15.?覆蓋掩體外圍的尋路網格

注意上圖中沙袋彎角處兩個淺綠色拐點。假設士兵碰撞半徑為1米，坦克碰撞半徑為5米，僅使用同一個尋路網格我們也能容易地可以生成兩種規格的路徑。我們只需要計算一條順著沙袋外沿的路徑，然后移出來1米或5米即可。

圖16.?覆蓋掩體外圍的尋路網格

再舉一個例子。想象一名駕駛摩托車的士兵。不比徒步，摩托車很難在行駛時小角度轉彎。

下圖中，很明顯摩托車手可以從當前位置駛進上方的房間（紅線），卻很難拐進右側的過道中，因為角度刁鉆（橙線）。不論何種尋路，都需要解決這個問題。

圖17.?摩托車可以駛進上面房間（紅線）卻無法進入右邊（橙線）

如果使用尋路網格，仍然簡單。在尋路過程中我們只要留意轉彎角度及距離，剔出那些短距離小角度的路徑即可。

但使用路徑點尋路，則基本上不大可能。因為無法使用徒步士兵的路徑點，我們至少要為摩托車單獨新建一張路徑點圖。而這種做法無疑導致冗余。

5.?路徑點沒有足夠信息以支持AI除尋路以外的功能。

AI尋路其實不僅僅是為了漫-游，還需要從路徑信息中得知在世界中如何移動。

游戲角色需要向尋路系統頻繁查詢：是否可以移動到這里？那里又如何？

如今游戲日漸演變出靠動畫驅動的移動系統，開始允許動畫師們通過動作控制角色的移動。這意味著如果要知道播放某個動畫會產生什么后果，就需要知道動畫結束時角色的位置，同時需要知道該位置是否恰巧在一堵墻中，或是掉出了懸崖，又或是關卡設計師不想讓玩家進入的地方。

舉個例子。下圖中的劍客有四種位移：左右平移、后退、騰空20英尺后于8英尺開外落地。

圖18.?一個包含四種位移動作的劍客

為了確保這個劍客做動作時不會一頭扎進磚墻里，我需要預先根據碰撞網格，監測每個動作是否可行。

是的，你可以使用碰撞系統，它總能提供有用的信息，對于游戲世界中動態運動的物體，它通常也是知會AI相關信息的唯一辦法。

但是碰撞檢測代價高昂，如果你只關心靜態物體，使用尋路網格無疑更為快捷。

另外，盡管我可以使用碰撞檢測來計算角色和某點間是否有墻體遮擋，碰撞系統卻無法告訴我劍客落地的位置是否正處于關卡設計師設定的禁區…這些只有通過尋路網格來判斷。

如果上述內容仍不能讓你信服，下面就讓我通過一些關于路徑點和尋路網格的問答，來打消你的疑慮吧。

Q & A

在尋路網格上取徑是否會降低效率？

一點也不會。尋路網格其實也是一張圖（graph），正如路徑點圖一樣，它們的核心尋路過程也極為相似。不同之處在于尋路網格圖中每一個節點都關聯一個多邊形。

下圖展示了被圖結構關聯起來的多邊形。

圖19.?尋路網格的構架是一張圖（紅色）

A*算法始終運行在某個圖結構中，無論它是方格、路徑點圖還是尋路網格圖。

大多數情況下，尋路網格的性能和路徑點接近。在使用寥寥數個節點覆蓋一片區域時（例如圖6），尋路網格性能提升顯著。

尋路網格是否會耗費更多內存？

手法正確的話，不會。

尋路網格結構精簡。總的來說，相比用于供渲染的模型網格，尋路網格不足其數分之一。相比碰撞模型，尋路模型關心的面數更少（它忽略墻、頂棚和其他腳力不可及的區域），而且往往使用更大號的多邊形覆蓋給定區域。

最壞情況下，尋路網格在每個圖節點上使用的頂點數目也許會多于路徑點圖。但很多時候，如圖6的哈蘭，尋路網格要比路徑點簡潔許多。

大多數你展示的例子都出自角色扮演游戲。為什么沒看到第一人稱射擊游戲存在這類問題？

很多FPS游戲都存在這個問題，不過緣于該類游戲本身玩法，此類問題不易被定位。

-?大多數AI都不會存活太久，難以發現其尋路缺陷。

- AI通常在你進入視線后即停下射擊，尋路一般偏短。

-?許多單人FPS游戲中，AI少動，更傾向于原地朝你放槍。

-?當今許多FPS游戲提供AI隊友，它們擊斃敵方AI，不留任何長距離跑路的機會。

這里有一個半條命2的例子。通過一點小實驗，不難發現梯子上的衛兵被限制在梯子中間直上直下的一條路線上，始終尋找著照面時刻射殺你的機會。

（譯注：原視頻再次缺失。）

如果你取消遠程武器強制角色們近身肉搏---《光暈》里的星盟士兵，《先頭部隊》里的克隆殺手，或者《銀河戰士》里的浮游者---便會發現路徑點突然成為了一個極其不堪的選擇（這也是上述三個游戲使用尋路網格替代路徑點的原因之一）。

瞧，我理解你的意思，但是設計師們需要在游戲里放置掩體點、巡邏路徑等。這對我們游戲的AI來說必不可少。

當然！即便使用了尋路網格，你仍然可以這么做。

關鍵在于分離兩個系統。你使用一個（尋路網格）來實現尋路及漫-游，使用另一個（設計師放置的這些點）告訴AI如何與游戲世界交互。

尋路網格不應該成為你使用任何系統的障礙，它只是簡單地為豐富AI尋路提供了額外信息。

舉個例子。我們設置了巡邏路徑（紫色）讓衛兵在城鎮附近巡邏，為一個老家伙設置特殊的點讓他每天到護城河邊垂釣（紅色）。掩體點方便暴風城的法師和術士們做FPS式的決斗時尋找掩護。

圖20.?多種地標點（所有顏色）和尋路網格共存

好吧，但是放置尋路網格難道不會花費很多時間嗎？

整體來說，手動放置尋路網格的工作量不會比設置路徑點來的更繁重。兩種體制下，放置尋路信息的時間都遠遠小于游戲中測試它們的時間。

以我的經驗來說，放置一個中等規格的FPS關卡尋路網格需要花費1-3小時時間。

創建一個尋路網格編輯器相對比較簡單。你要實現的功能就是放置頂點到游戲世界中，選取并將他們組織成多邊形。你可以通過多邊形鄰邊共享的頂點來決定尋路網格之間的連通性。

同時，有一些中間件可以幫你完成構建尋路網格和實時尋路的工作，例如xaitment，?NavPower，PathEngine及Kynapse。這些解決方案都在日漸完善中。

如果我有一個爬樓梯的AI怎么辦？我們的設計師可不喜歡為樓梯上每個臺階鋪設一個尋路網格。

尋路網格只是標識了Ai可以行動的區域。它不能用于代替碰撞檢測模型---你的NPC仍然需要碰撞系統來支持游戲中的碰撞。

你只需一個大矩形覆蓋整個樓梯即可。

難道我不能給每個路徑點賦一個半徑信息，用圓來替代點？這樣我就可以知道那些區域可以走動。這是正他們在robotics里的做法…

這個方法在某些場合行得通，但是游戲中的大多數區域遍布彎彎角角的街道和建筑。圓形無法和這些空間契合得很好，在覆蓋該類型區域的便利性上較使用多邊形相去甚遠。

下方展示了在暴風城使用圓形擴展路徑點進行尋路的示意圖。

圖21.?路徑點擴展為圓

（小軼事：當我在《機甲戰士4：復仇》小組工作時，我們發現在戶外表現良好的圓形系統一旦應該用到城鎮中立刻不再適用。我們最終解決了這個問題，但是得到一個教訓：圓和城市水火不容！）

與此同時，留下邊角也是很重要的。在圖16的沙漠掩體一例中，我們使用尋路網格的邊角針對士兵和坦克不同的形體、大小和運動參數生成不同的路徑。圓圖不支持邊角，所以為不同單位創建不同路徑也會變得相當困難。

我的游戲已經有了碰撞模型，我能用它作為尋路網格嗎？

你可以試試，但這可不是個好主意。

碰撞模型被優化以便于碰撞、而非尋路。它往往包含比尋路需要的多得多的多邊形，因此你的尋路算法會變得很慢。

例如，一條鵝卵石街道上的碰撞模型也許有1000個多邊形，而只需一個尋路矩形。一個建筑頂棚的碰撞模型含50個多邊形，但根本不需要尋路網格（因為我們的角色或許永遠不會走上屋頂）。

同時，尋路網格的一部分優勢在于它不僅僅告訴你尋路單位可以移動的范圍；還告訴你設計師想讓他們在哪里移動。

如果你讓你的設計師手動創建尋路網格，他就可以標識某處“AI免進。這里拒絕任何單位進入，因為這個游戲設定如此。”這些信息是碰撞模型永遠給不了的。

上面所有的例子里尋路網格似乎都是到2D空間的投射。我如何處理道路穿過橋洞，何時能夠通過何時不能，或者多樓層建筑的情況？

尋路網格能優雅地解決這些問題。下面是魔獸世界沙塔斯尋路網格分布的樣子（簡便起見，我省略了橋遠側的部分網格）。

圖22.?沙塔斯，覆蓋橋上或穿行橋下的尋路網格

在尋路網格中，每個多邊形通常存儲有一個表示通行高度的參數。例如，穿行于橋下的多邊形被標識為7英尺，那么那些高于7英尺的單位將無法從橋洞通過。

對于多樓層建筑的情況，每個樓層有獨立的尋路網格，之間通過樓梯的尋路網格連接（當然，電梯略棘手）。

我不相信會有放之四海而皆準的辦法。不同的游戲需求不同的尋路之法。

如果你正制作一個純2D策略類游戲，那么一個基于方格的尋路算法更為合適，因為格子允許更快捷地訪問任意地塊。

否則，尋路網格真的是3D世界中解決尋路及地形物理的最佳方法。

我想在自己的游戲中實現尋路網格。有沒有資料可以幫助我理清如何生成網格，如何在其上尋路，以及如何在游戲中優化它們？

我所知道的資料如下：

"Simplified 3D Movement and Pathfinding Using Navigation Meshes" by Greg Snook (Game Programming Gems)

"Polygon Soup for the Programmer's Soul: 3D Pathfinding" by Greg Hjelstrom and Patrick Smith (GamaSutra.com)

"Building a Near-Optimal Navigation Mesh" by Paul Tozour (AI Game Programming Wisdom)

"Efficient Navigation Mesh Implementation" by John C. O'Neill (Journal of Game Development, March 2004)

"Search Space Representations" by Paul Tozour (AI Game Programming Wisdom 2)

"A Fast Approach To Navigation Meshes" by Stephen White and Christopher Christensen (Game Programming Gems 3)

"Choosing a Relationship Between Path-Finding and Collision" by Thomas Young (Game Programming Gems 3)

"Improving on Near-Optimality: More Techniques for Building Navigation Meshes" by Fredrik Farnstrom (AI Game Programming Wisdom 3)

"Smoothing a Navigation Mesh Path" by Geraint Johnson (AI Game Programming Wisdom 3)

"Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision" by Paul Marden and Forrest Smith (AI Game Programming Wisdom 4)

"Intrinsic Detail in Navigation Mesh Generation" by Colt McAnlis and James Stewart (AI Game Programming Wisdom 4)

"Navigation Mesh Generation: An Empirical Approach" by David Hamm (AI Game Programming Wisdom 4)

"Navigation Mesh Generation in Highly Dynamic Worlds" by Ramon Axelrod (AI Game Programming Wisdom 4)

"Crowds in a Polygon Soup: Next-Gen Path Planning" by David Miles (http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt)

注意：如果你有相關資料想在此列出，請郵件聯系我。

實際有多少游戲成功應用了尋路網格？

這里有一個名單：

光暈2

光暈3

先頭部隊

反恐精英：起源

銀河戰士

銀河戰士2：回聲

銀河戰士3：墮落

杰克與達斯特：舊世界的遺產

杰克2

杰克3

神秘海域：德雷克船長的寶藏

疤面煞星：掌握世界

…更多的例子枚不勝舉。

看起來所有扮酷的同學都用了這個。

好吧，它或許對你適用，但是我們之前所有的游戲使用的都是路徑點尋路，表現良好。

如大家所說，如果它還能用，就別去管它…而且你說的那些問題我們一個都還沒碰到哩。

目光放長遠點，想象一二十年以后的光景。

到那時，你認為你的游戲會不會包含眾多不同的AI控制的不同角色，各自又有不同的體型、大小、運動參數？

玩家們會不會想要和他們一樣聰明的AI伙伴？

你的游戲會不會比今天更龐大、更復雜、更具變化性？

你會不會同時擁有有數量眾多的AI角色---多到簡單的轉向和規避障礙已經不足以滿足AI間豐富高效的交互？

你的游戲會不會引入高仿真的物理系統，玩家們會不會隨心所欲地使用物理和AI角色打成一片？

玩家們可不可以把游戲世界改造得面目全非？

會不會有AI在多人游戲中完全替代真實玩家？

二十年后的游戲會是什么樣子我們無從得知，可以預見的是我們需要更高級的AI，虛擬角色們需要更多的數據來演繹環境，優化尋路，應對千變萬化的游戲世界。

http://www.ufgame.com/findaipath.html

https://github.com/SebLague/Pathfinding/tree/master/Episode%2002%20-%20grid

https://github.com/DevonCrawford/A-Pathfinding-Visualization

https://danny0ner.github.io/Pathfinding-Optimization/

尋路優化

尋路是許多游戲的重要資源，BFS，DJikstra或A *等基本算法在某些游戲中可以正常工作，但在某些情況下，特別是在大型地圖上，它們可能很慢，讓你的游戲暫停一會兒直到它找到路徑或減慢游戲速度。這使得它的優化變得如此重要，因為你希望你的程序或游戲盡可能快，以便將來可能擴展。

在本文檔中，您將找到A的快速解釋，對它的一些小優化，對從A算法派生的最常用優化的解釋以及實現HPA算法的指南。

提醒A *算法

A *算法旨在找到從單個起始到單個目標節點的路徑。該算法使用一個簡單的算法來計算您的路徑，該算法是目的地的距離。將已經行駛的和估計的距離加在一起，它首先擴展了最有希望的路徑。由于它幾乎檢查每條路徑以找到距離的路徑，我們可以說它找到的路徑幾乎總是最優的。

正如我們在圖像中看到的那樣，從白色中心廣場開始，A *搜索他周圍的方塊并沿著最近的方格到達目的地。當它找到目的地時，它返回每個方格的父節點之后的路徑，即它們從中擴展的方形的父節點。

這是我們在實現A *算法時所做的事情：

找到最接近您的位置的節點并將其聲明為start node并將其放在打開的列表中。

雖然打開列表中有節點：

從具有最小F分數的打開列表中選擇節點。把它放在關閉的清單上（你不想再考慮它）。

對于不在關閉列表中的每個鄰居（相鄰小區）。

將其父級設置為當前節點。

計算G得分（從起始節點到該鄰居的距離）并將其添加到打開列表中

通過將啟發式添加到G值來計算F得分。

基本尋路優化

我們有很多方法可以優化尋路，對其進行微小的改動。它們的變化將使它更快，但不如概念優化那么快，這將在后面解釋。此外，某些方法在某些情況下無法返回最佳搜索，但如果您的地圖是間隔較大的地圖而沒有很多障礙，則它們是一個很好的實現。如果我們想要更快地完成路徑尋找而不必對我們的算法進行大的更改，我們可以：?使用無序列表。我們每個循環必須做的事情之一是找到得分最低的節點。使用無序列表，我們不需要搜索該節點，因此它將位于第一個位置。

?使用貼圖或堆而不是列表也會加速算法。迭代時這種數據結構更快，因此當您需要搜索節點時它將非常有用。你可以使用無序的地圖和堆，所以第一個建議在這里也很有用。

?分離尋路。這意味著您的單位不需要一幀中的完整路徑，因為它們不會在該幀中通過它。您可以為路徑查找設置循環限制，因此如果找不到目標并到達目標，則保存它已關閉的最后一個節點，然后繼續下一幀的路徑。如果您的尋路循環限制太低，此方法可能會導致錯誤，因為如果找不到出路，它可能會在大的封閉區域上進行搜索。但是如果你確定你的地圖沒有冒這個風險并且你的循環限制是一個可接受的數字，它將幫助你尋找很多。

?節點中的變量is_open或is_close。您可以為節點創建一個變量，如果該節點位于打開或關閉的列表中，則該變量為true。有了這個，當你需要在列表中搜索一個節點時，你可以訪問它，看看它是否只在該列表上查找該變量，而不是查看它在整個列表中的位置。這會減少您在NxN圖塊地圖中打開的列表中的搜索，通過打開（N）打開（1）。

?在真實路徑尋找之前執行較低級別的尋路。您可以預先計算分離節點的地圖，并在需要查找路徑時首先使用該地圖。使用它，您將獲得到目的地的分離節點的路徑。當你有這個路徑時，你可以開始在分離的幀中使用從一個節點到另一個節點的路徑尋找，就像分離路徑尋找但沒有循環限制一樣，你將路徑到路徑的第一個低級節點，然后等待下一幀繼續到下一個節點的路徑，直到找到目的地。

概念尋路優化

我們將概念優化稱為優化，以改變尋路搜索節點的方式。路徑尋找節點搜索方式的每一個小變化都可以根據您的地圖分布或移動方式優化您的路徑尋找。請注意，路徑查找的某些概念優化將更好或更差，具體取決于地圖更改的位置或是否為靜態或取決于障礙物的位置。有一些很好的概念優化，但我們將討論其中兩個：HPA和JPS。

HPA

分層路徑尋找基于預處理到目的地的較低級別路徑尋找，較低級別將在群集中保留，其距離和彼此的最佳路徑是預先計算的。一旦我們進行了較低級別的尋路，我們將使用其預先計算的最佳路徑穿過每個群集并獲得到目的地的快速路徑。

正如我們在圖像中看到的那樣，網格在群集上劃分，并且此群集具有將它們連接到其他群集的出口。一旦我們連接它們，我們就會在正確的圖像中看到類似的東西，在那里我們可以看到到達另一個邊緣的成本。這種預先計算的成本在選擇最佳路徑方面非常有用。

現在，讓我們看一個我們在S中的例子，我們想要去G.這個算法很簡單，我們只用簇做一個正常的a *，一旦我們有了路徑，我們就用成本來自一個簇盡可能快地到下一個。

請記住，您可以使用自己的群集創建自己的網格，聽起來很明顯，但您可以根據地圖的分布創建網格。使用自己的網格，您可以使一些群集更大，其他群集適合房間或地圖的其他區域，這將阻止您在房間中進行較低級別的尋路，如果您可以在該房間中安裝群集而不是2,3那個房間或更多集群。

利弊：

每種優化在某些情況下都比其他優化更好，讓HPA預先計算距離和路徑在您的地圖始終更新的游戲中不會是最佳的，并且更改將使您的HPA再次重新計算路徑和距離，如果更改將需要一些時間相當可觀。您可以創建自己的網格這一事實是如此的神，因此它可以幫助您優化地圖的同意區域。對于沒有太多障礙的間隔地圖，HPA不是最佳選擇。這并不意味著它更糟糕，只是意味著其他優化如JPS在間隔區域獲勝。

JPS

跳轉點搜索算法的基礎是擴展基數的起始節點，以達到無法繼續擴展的區域。我們現在將解釋它，但如果你認為這很簡單，如果你可以用另一個節點訪問該位置并且迭代的節點較少，為什么還要將節點添加到列表中？

與HPA不同的是，使用JPS，您無需預先計算任何內容，只需花費更少的時間來迭代打開和關閉列表。我們需要知道，JPS利用網格的規律性，這意味著如果我們有不同成本的地圖的圖塊或區域，JPS會將它們作為統一成本網格，因為它看起來并不是所有節點所以它不相關。此外，通過利用規律性，不需要從每個圖塊的每個方向擴展，并且在開放和關閉列表上迭代許多節點，每個像A *這樣的單元格。僅掃描瓷磚就足以檢查附近是否有任何“有趣”，我們稱之為跳躍點。現在我們將處理解釋掃描過程，基本上我們如何擴展節點以及如何找到跳轉點。

在進入JPS的算法之前，讓我們來談談它的基礎，鄰居修剪：

節點x由其父節點展開，該節點用箭頭引用。正如我們所看到的，可以檢查所有節點在水平或對角線上進行搜索，如箭頭所示，而不必為節點x傳遞。這意味著我們可以使用父節點檢查所有這些節點，因此不需要x。現在讓我們談談什么是強迫鄰居：

強制鄰居是無法從節點X擴展的節點，正如我們在圖像中看到的那樣，如果我們按照灰色-圖塊上的箭頭，我們就無法到達突出顯示的節點。我們無法從另一個節點到達的節點稱為強制鄰居。請記住，正在擴展的節點始終位于障礙物旁邊，后面的磁貼將成為強制鄰居。

JPS算法解釋

我們從p（x）開始并開始在水平方向擴展節點。我們發現p（x）上方的區塊被阻塞，因此我們找到第一個強制鄰居X.我們停止擴展p（x）并開始擴展x。我們水平擴展X，因此它找到了Y.Y在它上面有一個被阻擋的區塊，所以我們將Y標記為強制鄰居，并且我們將無法將Z作為鄰居標記為Z.?在這種情況下有兩種可能性。當我們發現Y上方有一個阻塞的區塊時，我們只將Z作為強制鄰居并繼續擴展Z，但是如果我們也添加Y，我們有一條直接路徑，我們不必在X和之間進行尋路。 Z，因為這是我們不想做的事情。算法一直以這種方式繼續。您可以先按順序進行搜索。首先進行水平搜索，然后是垂直搜索，然后是對角線，這是正常的，

讓我們使用對角線搜索來看這個JPS。我們從旁邊的p（x）阻塞區塊開始，我們接下來要做的是將X作為強制鄰居。我們在垂直方向擴展p（x）但我們沒有找到任何有趣的東西，所以我們傳遞給下一個鄰居。我們開始擴展X，而我們擴展它時我們遇到與p（x）相同的問題我們有一個障礙物向下X所以我們添加一個強制鄰居W，我們繼續擴展X.如果我們繼續擴展X對角線，我們將發現當我們在Y中擴展時，我們發現目標Z，所以我們將兩者都添加為強制鄰居，這樣我們就可以獲得一條簡單的路徑，并且我們創建了路徑，因為我們找到了目標。

優點和缺點：

正如我們之前所說，在網格上有不同的成本對JPS不起作用，因此你有一個不同成本的網格，這不是你的最佳優化。由于地圖間距越大，您所擁有的跳躍點越少，迭代速度越快。您不需要預先處理任何內容，地圖可以改變您想要的方式，它不會影響JPS。

如果您不清楚JPS如何在這里工作，您可以通過網絡查看A *，Djikstra，JPS和其他工作人員。是一個有用的網站，可以在您看到他們進行搜索時了解他們的工作對象。PathFinding.js

尋路優化實施

現在，我們將解釋一個簡單的表單，使用節點映射優化您的尋路。此方法基于退出已關閉列表而不是迭代打開列表創建節點映射，我們將檢查節點是否已處于打開或關閉列表中。我們將從正常的Pathfinding開始。現在是設置地圖的時刻，現在我們將創建具有地圖大小的節點地圖。

現在，通過這個節點數組，我們可以通過輸入它在網格上的位置來訪問地圖中的每個節點，這在迭代時非常有用。有一次我們有節點映射，我們開始使用A *函數。我們要做的第一件事是用地圖填充節點的地圖，因此不會對它們進行評估，因為我們將使用std :: fill（第一項，最后一項，Node）;

*注意：size是地圖的寬度+高度。接下來我們要做的是為我們的開放列表創建一個priority_queue。正如我們之前所說的那樣，擁有優先級隊列會加快隊列的迭代速度，我們將始終在列表頂部放置得分最低的節點，這樣我們就不需要搜索它了。

如果你不知道比較是什么，它是一個簡單的結構，有一個運算符來比較節點的分數來組織它們。

下一步是創建一個FirstNode指針節點，該節點將信息保存在地圖中并將其推送到打開列表。我使用DistanceTo函數來計算啟發式距離。

注意* GetPathNode接收位置并返回節點映射的Pathnode的指針。

此時我們已準備好從while循環開始。我們將調整它以使用指向節點映射的指針并檢查它們是否已經處于打開或關閉列表中。

我們將當前設置為地圖中的最低得分節點，如果我們將其添加到關閉列表中，我們確實喜歡，但我們只將其設置為bool on_close為true。是時候找到鄰居，看看他們是否已經被添加到列表中。

現在我們創建一個指向item節點的temp，它將為我們提供一個指向地圖的指針，并檢查它的bool以查看它是否已經像關閉列表或打開列表中那樣被解決。這樣做我們擺脫了A *所面臨的最大問題，迭代列表以找到節點所在的id。其余的繼續像普通A *一樣，如果我們找到到該節點的較短路徑，我們只需將其父節點設置為當前節點。*注意：CalculateFopt是一個計算g和h的函數，并根據距離是對角線還是直線來設置它。我們要做的最后一件事是，當我們找到目的地時，回溯節點直到我們找到第一個節點。

我們可以通過回撥到該位置并將該位置更新為其父級直到它沒有父級來輕松完成。我們使用節點映射而不是列表完成了路徑查找！

##優化的結論我一直在嘗試在120x120路徑上制作最難的路徑，優化的路徑確實需要最多20 ms，而正常的A *確實需要~200-600 ms

你可以在github下載項目（頂部的鏈接），然后試一試！

參考文獻：

http://zerowidth.com/2013/05/05/jump-point-search-explained.html

http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter17_Pathfinding_Architecture_Optimizations.pdf

http://www.intelligence.tuc.gr/~robots/ARCHIVE/2015w/Projects/LAB51326924/jps.html

https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm-gamedev-5818

http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

https://qiao.github.io/PathFinding.js/visual/

https://github.com/Danny0ner/Pathfinding-Optimization

https://www.cs.upc.edu/~npelechano/Pelechano_HNAstar_prePrint.pdf

https://github.com/Rydra/HierarchicalPathfinder

https://github.com/hugoscurti/hierarchical-pathfinding

https://stackoverflow.com/questions/23743780/path-finding-with-multiple-levels

https://www.ocr.org.uk/administration/stage-4-results/calculating-a-level-a-star/

http://aigamedev.com/open/review/near-optimal-hierarchical-pathfinding/

https://en.wikipedia.org/wiki/Taxicab_geometry

https://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm--gamedev-5818

https://www.hiveworkshop.com/threads/terrain-based-pathfinding.234615/

https://www.gamedev.net/forums/topic/172880-warcraft-3-pathfinding/

https://www.hiveworkshop.com/threads/pathfinding-in-warcraft3.224712/

https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。