三維網格尋路演算法

㈠ 如何使用Unity3D做游戲中的尋路導航

現在的大部分mmo游戲都有了自動尋路功能。點擊場景上的一個位置，角色就會自動尋路過去。中間可能會有很多的障礙物，角色會自動繞過障礙物，最終達到終點。使用Unity來開發手游，自動尋路可以有很多種實現方式。
最近，一名海外開發者在博客中分享了自己用Unity引擎重做此前研發的Flash游戲尋路導航的心得，希望可以給大家帶來幫助：
大家好，最近我一直都在忙於把2006年的一款Flash游戲用Unity引擎重做出來，盡管我們在《Arrival in Hell》這個項目已經工作了一年多，但這里我希望從頭開始來寫開發者博客，因為這樣才能讓讀者們有比較完整的印象。
如果你們不太熟悉這款游戲的話，我這里做幾句話的介紹，我們在對2006年我和朋友Eardo Mojica以及Richard Rout三人研發的一款Flash游戲進行重做，這是一款點擊式操作的冒險游戲，我們將用Unity引擎進行重做。我做編程和研發游戲已經有十年左右的經驗，但這是我使用Unity引擎做的首款游戲。
在其他事情之前，我首先想要說的就是玩家角色的移動，由於這款游戲現在是真正的3D，因此玩家角色需要在3D空間里尋路。幸運的是，Unity引擎已經有了一些不錯的內置尋路功能，你只要打開窗口-導航（Navigation），選擇你想要使用的物體並且放到路徑中，然後把他們標記為『導航靜態（Navigation static）』這就會告訴Unity這些物體是靜態的（非移動），在尋路的時候應該被考慮進去。

把物體設置為『導航靜態』
這里我想要說一說這個功能有多麼強大。過去，我和大多數的游戲開發者一樣，都必須打造自己的尋路系統，我之前就做過一個A*tile和基於節點的尋路系統，在兩種情況下，特別是基於節點系統的尋路所產生的walls讓人非常頭痛。在基於節點的尋路系統中，你必須手動地把AI使用的點在兩者之間進行導航。Unity不僅做導航功能，還使用了導航網格（Navigation meshes），這比手動放置節點更有效率而且更流暢。更重要的是，你還可以一鍵重新計算整個導航網格，徹底擺脫了手動修改導航節點的做法。

我用基於節點系統做的失敗的尋路系統之一
在把靜態物體加入了導航網格之後，你可以選擇一系列的設定然後點擊bake按鈕，比如在考慮加入一堵牆之前確定坡有多陡以及台階應該多高。這樣你就可以獲得可以預覽的視圖。值得注意的一件事是，不要僅僅因為物體存在在場景中就意味著它是導航網格的一部分。比如說在這款游戲中，我不在乎玩家們是否會踩到瓦礫，所以我並沒有把任何瓦礫標識為導航靜態，這加快了當行網格的生成速度。

《Arrival in Hell》中其實是有數值的
在導航網格生成之後，我簡單地給玩家模型增加了一個NavMeshAgent組件，這款游戲現在就可以進行尋路了，唯一剩下的就是增加滑鼠輸入控制NavMeshAgent的目的地。

用NavMesh做的bake

NavMeshAgent設定
為了告訴NavMeshAgent導航我做了以下指令：
1.注意聽取滑鼠輸入
2.把滑鼠放進屏幕空間
3.把屏幕空間轉變成來自攝像頭的一束光
4.在光達到地面的時候把它移除
5.把NavMeshAgent的目的地設定到地板的對應位置。
C#代碼是這樣的：

可視化視圖下的目的地與路徑
這就解決了我這款游戲的大多數導航需求，唯一的例外就是導航網格由於游戲內的一些活動而發生改變的時候。比如第一個房間的們最開始是關閉的，後來當它打開的時候，當行網格需要更新反映此次變化，允許玩家從新開的們中走過去。我並沒有在游戲運行的時候rebake完整的靜態導航網格，而是使用了NavMeshObstacle組件，該組件可以讓你把尋路過程中的動態物體加進去，如果物體移動，Unity的尋路演算法就會根據實際情況而更新。

導航路徑會根據NavMeshObstacle的變化而自動發生改變

可視化視圖
所以，游戲尋路導航就這么做好了，這就是《Arrival in Hell》游戲中的導航工作原理，這一些只需要Unity內自帶的導航功能就可以完成了。

㈡ 有哪些應用於移動機器人路徑規劃的演算法

機器人家上了解到，在二維二值地圖（FREE or OCCUPIED）場景下進行路徑規劃的方法。我看之前有同學在回答的時候配上了這幅圖：

這幅圖上的演算法羅列的還是很全面的，體現了各個演算法的出生順序。但是並不能很好的對他們進行一個本質的分類。剛剛那位同學說的graph-based和sampling-based的分類方法我感覺有點概念重疊不能夠對規劃演算法進行這樣的分類，下面通過自己這一年多的研究和實踐對規劃演算法進行一個簡單的分類：

這幅圖上的演算法羅列的還是很全面的，體現了各個演算法的出生順序。但是並不能很好的對他們進行一個本質的分類。剛剛那位同學說的graph-based和sampling-based的分類方法我感覺有點概念重疊不能夠對規劃演算法進行這樣的分類，下面通過自己這一年多的研究和實踐對規劃演算法進行一個簡單的分類：

兩大類：
1. 完備的（complete)
2. 基於采樣的（sampling-based）又稱為概率完備的

一 完備的規劃演算法

A*演算法

所謂完備就是要達到一個systematic的標准，即：如果在起始點和目標點間有路徑解存在那麼一定可以得到解，如果得不到解那麼一定說明沒有解存在。
這一大類演算法在移動機器人領域通常直接在occupancy grid網格地圖上進行規劃（可以簡單理解成二值地圖的像素矩陣）以深度優先尋路演算法、廣度優先尋路演算法、Dijkstra(迪傑斯特拉)演算法為始祖，以A*演算法(Dijstra演算法上以減少計算量為目的加上了一個啟發式代價)最為常用，近期的Theta*演算法是在A*演算法的基礎上增加了line-of-sight優化使得規劃出來的路徑不完全依賴於單步的柵格形狀（答主以為這個演算法意義不大，不就是規劃了一條路徑再簡單平滑了一下么）。
完備的演算法的優勢在與它對於解的捕獲能力是完全的，但是由此產生的缺點就是演算法復雜度較大。這種缺點在二維小尺度柵格地圖上並不明顯，但是在大尺度，尤其是多維度規劃問題上，比如機械臂、蛇形機器人的規劃問題將帶來巨大的計算代價。這樣也直接促使了第二大類演算法的產生。

二 基於采樣的規劃演算法

RRT-connect演算法
這種演算法一般是不直接在grid地圖進行最小柵格解析度的規劃，它們採用在地圖上隨機撒一定密度的粒子來抽象實際地圖輔助規劃。如PRM演算法及其變種就是在原始地圖上進行撒點，抽取roadmap在這樣一個拓撲地圖上進行規劃；RRT以及其優秀的變種RRT-connect則是在地圖上每步隨機撒一個點，迭代生長樹的方式，連接起止點為目的，最後在連接的圖上進行規劃。這些基於采樣的演算法速度較快，但是生成的路徑代價（可理解為長度）較完備的演算法高，而且會產生「有解求不出」的情況（PRM的逢Narrow space卒的情況）。這樣的演算法一般在高維度的規劃問題中廣泛運用。

三 其他規劃演算法
除了這兩類之外還有間接的規劃演算法：Experience-based（Experience Graph經驗圖演算法）演算法：基於經驗的規劃演算法，這是一種存儲之前規劃路徑，建立知識庫，依賴之進行規劃的方法，題主有興趣可以閱讀相關文獻。這種方法犧牲了一定的空間代價達到了速度與完備兼得的優勢。此外還有基於廣義Voronoi圖的方法進行的Fast-marching規劃，類似dijkstra規劃和勢場的融合，該方法能夠完備地規劃出位於道路中央，遠離障礙物的路徑。答主最近也在研究此類演算法相關的工作。

APF（人工勢場）演算法

至於D* 、勢場法、DWA(動態窗口法)、SR-PRM屬於在動態環境下為躲避動態障礙物、考慮機器人動力學模型設計的規劃演算法。

㈢ 有關A* 尋路演算法。 看了這個演算法 大致都明白。就是有點不大清楚。

1. B的G值是指從起點A開始，到達該點的最短距離，和B在不在最短路徑上沒有關系。

2. 不是遍歷所有路徑，而是所有點。對於m*n的矩陣， 遍歷所有點的復雜度是m*n（多項式復雜度），而遍歷所有路徑的復雜度是4的(m*n)次冪(每個點都有4個可能的方向)。從冪指數復雜度降低到多項式復雜度，這就是A*演算法的意義所在。

3. 最優路徑是要從終點一步步倒退回來。比如終點的G值是k，那麼最多需要4*k次查找，依然是多項式復雜度。但多數問題(對於純演算法題來說)只是需要知道到達終點的步驟，很少要你找出固定路徑的。

㈣ 夢幻西遊自動尋路的尋路演算法怎麼算

A*尋路演算法 A*（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
啟發式搜索其實有很多的演算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些演算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取「最佳節點」後舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由於舍棄了其他的節點，可能也把最好的
節點都舍棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
中都把當前的節點和以前的節點的估價值比較得到一個「最佳的節點」。這樣可以有效的防止「最佳節點」的丟失。那麼A*演算法又是一種什麼樣的演算法呢？其實A*演算法也是一種最
好優先的演算法。只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價
函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。哈。你懂了嗎？肯定沒懂。接著看。
舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是
。當然它是一種最臭的A*演算法。
再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計
算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}

㈤ A星尋路演算法和Unity自帶的尋路相比有什麼優勢

在理解Navigation的時候，首先要明確兩個知識點：

AStar：AStar是路點尋路演算法中的一種，同時AStar不屬於貪婪演算法，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。AStar是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。

性能和內存佔用率都還行，和啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。

A Star一般使用場景：

• 策略游戲的策略搜索

• 方塊格子游戲中的格子尋路

Navigation：網格尋路演算法，嚴格意義上它屬於」拐角點演算法」，效率是比較高的，但是不保證最優解演算法。Navigation相對來說消耗內存更大，性能的話還不錯。

Navigation一般使用場景：

• 游戲場景的怪物尋路

• 動態規避障礙

它們二者事件的實現方式和原理都不同。

AStar的話，

㈥ 3D空間尋路

A*演算法，無論你是2D的還是3D的，甚至是4D的，
只要增加方向向量就行了。

生成網格後，肯定可以查詢到每個點的旁邊一共有哪些點是可行走的，走過去需要多少代價。因此也不需要考慮空間結構，只要寫好查詢周邊點的函數就行了。

對已查詢到的點，進行行走代價的堆排序，取出頂點計算是否可到達目的，不能則查詢周圍點，加入堆中。然後繼續取頂點。

具體程序寫法要自己研究下。

A*演算法：http://ke..com/view/7850.htm

㈦ A*搜尋演算法的簡介

速度和精確度之間的選擇前不是靜態的。你可以基於CPU的速度、用於路徑搜索的時間片數、地圖上物體（units）的數量、物體的重要性、組（group）的大小、難度或者其他任何因素來進行動態的選擇。取得動態的折衷的一個方法是，建立一個啟發式函數用於假定通過一個網格空間的最小代價是1，然後建立一個代價函數（cost function）用於測量（scales）：
g』(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0，則改進後的代價函數的值總是1。這種情況下，地形代價被完全忽略，A*工作變成簡單地判斷一個網格可否通過。如果alpha是1，則最初的代價函數將起作用，然後你得到了A*的所有優點。你可以設置alpha的值為0到1的任意值。
你也可以考慮對啟發式函數的返回值做選擇：絕對最小代價或者期望最小代價。例如，如果你的地圖大部分地形是代價為2的草地，其它一些地方是代價為1的道路，那麼你可以考慮讓啟發式函數不考慮道路，而只返回2*距離。
速度和精確度之間的選擇並不是全局的。在地圖上的某些區域，精確度是重要的，你可以基於此進行動態選擇。例如，假設我們可能在某點停止重新計算路徑或者改變方向，則在接近當前位置的地方，選擇一條好的路徑則是更重要的，因此為何要對後續路徑的精確度感到厭煩？或者，對於在地圖上的一個安全區域，最短路徑也許並不十分重要，但是當從一個敵人的村莊逃跑時，安全和速度是最重要的。
在游戲中，路徑潛在地花費了許多存儲空間，特別是當路徑很長並且有很多物體需要尋路時。路徑壓縮，導航點和beacons通過把多個步驟保存為一個較小數據從而減少了空間需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.如果路徑仍然用了許多存儲空間，可以限制路徑長度，這就回到了經典的時間-空間折衷法：為了節省空間，信息可以被丟棄，稍後才重新計算它。

㈧ 三維點最短路徑尋路演算法求助

題目描述得不夠清楚啊，若干個點就是能作為中途點的那些點么？

如果所有的點都能作為中途點，當然走直徑，直接走A到B的直線。

否則，如果只有幾個，只能用啟發式或者廣度搜索吧，因為還有可能根本就沒有解。
如果中途點不多的話，可以直接從A出發，計算不超過L距離的那些中途點，然後以那些中途點為出發點，繼續計算不超過L距離的點（走過的點就不計入），直到遇到B為止。這種方法就是廣度搜索，在同一層距離最短的則為最短路徑。
如果中途點過多，無法這樣計算的話，限定范圍。

㈨ 游戲中的常用的尋路演算法有哪些

f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
?;) = g(n? 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
A*演算法
? h(n) = 從結點n到目的結點的耗費評估值，啟發函數
?，程序返回n
else 生成結點n的每一個後繼結點n;
foreach 結點n的後繼結點n;{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值，評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n?? 在演算法啟動時，Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點；稱為node_goal
創建起始結點；稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑;)
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ;) + h(n?? 包含我們還沒有處理到的結點
? g(n) = 從初始結點到結點n的耗費
?? 包含我們已經處理過的結點
，處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure （我們已經搜索了所有的結點?? 啟發式搜索
– 在搜索中涉及到三個函數
??? 我們最開始將起始結點放入到Open列表中
– Closed列表
?

㈩ unity導航網格里哪個函數是獲取路線的

在Unity3d中，我們一般常用的尋路演算法：
1.A*演算法插件
與貪婪演算法不一樣，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。A*是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
與啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
使用較好的地方：
a.策略游戲的策略搜索
b.方塊格子游戲中的格子尋路
2.U3D自帶的導航網格系統
U3D內置了NavMesh導航網格系統，一般來說導航網格演算法大多是「拐角點演算法」，具體大家可以去查下。效率是比較高的，但是不保證最優解演算法。
使用較好的地方：
a.游戲場景的怪物尋路
b.動態規避障礙
3.WayPoint尋路插件
速度最快，但相應來說表現也非常局限，它常常走「Z」型的軌跡，並不適合復雜場合的使用。例如它不能根據寬度、高度、路徑點耗散等來改變行進路徑。
使用較好的地方：
a.塔防怪物行進路徑
b.AI巡邏路線