網格尋路演算法

㈠ unity2d 做橫版平台游戲有什麼好的尋路演算法或插件

並沒一種尋路適合所有場合，選擇都是基於需求而定的。

1. A* 演算法與貪婪演算法不一樣，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。
A*是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
與啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
使用的地方：
a. 策略游戲的策略搜索
b. 方塊格子源殲肆雹轎游戲中的格子尋路

2. Unity 自帶的導航網格系統
Unity 內置了NavMesh導航網格改告系統，一般來說導航網格演算法大多是「拐角點演算法」。
效率是比較高的，但是不保證最優解演算法。
使用的地方：
a.游戲場景的怪物尋路
b.動態規避障礙

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

機器人家上了解到，在二維二值地圖（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屬於在動態環境下為躲避動態障礙物、考慮機器人動力學模型設計的規劃演算法。

㈢ 3D空間尋路

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

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

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

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

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

㈣ 凸面多邊形尋路演算法

凸多邊形是一個內部為凸集的簡單多邊形。凸多邊形（Convex Polygon）指如果把一個多邊形的所有邊中，任意一條邊向兩方無限延長成為一直線時，其他各邊都在此直線的同旁，那麼這個多邊形就叫做凸多邊形，其內角應該全不是鈍角，任意兩個頂點間的線段蔽晌位於多邊形的內部或邊上。

凸面多邊形一條邊上的任意一點到另外一條邊上的任意一點總是可達的。

http://blog.csdn.net/qq_35644234/article/details/60875818

地圖網格就是一個凸面多邊形的集合
如果可視化就是這樣

三維向量(Vector3)：

頂點(Vertex)：

邊(Edge)：

凸面(Convex)：

網格(Mesh)：

UML:

1.數據預處理
2.通過floyd演算法生成P矩陣
3.利用P矩陣求出路徑列表
4.優化路徑
5.輸出

1.遍歷Mesh中每個Convex，生成多邊形所有的邊
2.將每條邊進行切割生成對應的點
3.將位於同一個Convex的點之間建立連通關系並計算權值（通過距離）

1.初始化floyd演算法需要的D矩陣和P矩陣
2.通過之前的連通圖執行floyd演算法
3.生成P矩陣

1.輸入起點from，終點to
2.在P矩陣中查找P[from][to]查詢下一步的節點next
3.將查詢到的結果記錄下來，並讓from = next
4.循環以上操作獲得路徑列表

未優化的路徑：
[圖片上傳失敗...(image-6fc23e-1538123978488)]
優化後的路徑：
[圖片上傳失敗...(image-796ae3-1538123978488)]
1.優化後經過的節點數更少
2.優化後路徑更自然
3.優化後路遲頃徑更短

首先我們挨個判斷每個點是否需要保留。這里通過一種基於視點范圍的方法來判斷，
我們首先令from點為視點（viewPosition）（及路徑中的第一個點），
那麼第二個點則為cur點，
我們令cur所在edge的兩端點到視點的向量為最小左視野（minLegLeft）和最小右視野（minLegRight）。

現在將cur賦值為第三個點，
我們令cur所在edge的兩端點到視點的向量為左視野（legLeft）和右視野（legRight）。
如果cur到viewPosition的向量沒有在最小視野當中，證明cur是不可達的，
那麼此時最小左視野所在邊上的路徑點就叫做拐點。
我們首先調整拐點位置，將拐點加入優化後的路徑表中，並將拐點作為viewPosition重新進行上述循環。
如果legLeft在minLegLeft右邊那麼我們令minLegLeft = legLeft
如果legRight在minLegLeft左邊那麼我們令minLegRight = legRight

調整拐點位置是為了使路徑更自然，所以我們應該讓視點到拐點與下一個到拐點的向量的夾角變小。
如果此時拐點到下一點的連線在最小宏旦鋒左視野左邊則拐點往左移，反之往右移。

㈤ 誰能介紹一下JPS尋路演算法的思想

這是一個近年來發現的高效尋路演算法。不過有一個限制就是只能在規則的網格地圖上尋路，而且圖上的點或邊不能帶權重，也就是不能有復雜的地形，只支持平坦和障礙兩種地形。

其
思想就是跳過矩形平坦區域的大量對稱路徑，只尋找所謂的跳躍點，作為搜索的節點。這樣做的好處是裁剪了矩形區域內大量的節點，使open
list中的節點數相對較少。要知道，通常啟發式搜索演算法如A*，大量時間耗費在對open
list的操作上。實現得好的A*演算法會使用優先隊列，甚至HOT(heap on top）來對操作進行優化。但當open
list中的節點過多，這些操作還是會變得很昂貴。不過JPS有個缺點是每生成一個節點，也就是要找到一個跳躍點，相比較A*演算法，是比較昂貴的。幸好通
常來說，得到的收益更多些。所以，在適用的情況下，還是推薦使用JPS的。

具體的實現，主要有兩部分。第一部分，從open list中取一個最佳節點，然後從幾個特定方向展開搜索，把每個方向得到的跳躍點，加入open list里。第二部分，就是找到一個跳躍點。

對於起始點，可以向所有方向展開搜索。對於其他節點，要看父節點指向本節點的方向，向所有自然鄰居和被迫鄰居節點方向進行搜索。
例如下圖的例子，對於節點n和父節點p和障礙x，+是n的自然鄰居，也就是說從p到n到+是最佳路徑。如果x不是障礙，從p到n到-不是最佳路徑，因為從p到x到-最近。但是如果x是障礙，那麼從p到n到-就是最佳路徑了，所以這時候稱-為被迫鄰居。
- + +
x n +
p x -
以上是n和p對角的例子。還有種情況是n和p是直線：
x x -
p n +
x x -

搜
尋跳躍點是遞歸進行的。首先判斷一個節點是否是跳躍點。如果這個點有被迫鄰居，那麼這個節點就是跳躍點。第二種情況，如果這個節點是目的地節點那麼也當作
跳躍點。如果不是，那麼就遞歸地沿本來方向繼續搜尋下去。對於對角方向要額外多做兩步，即先對其相應的（左右兩個）直線方向進行搜索，如果找到跳躍點，就
把自身也當作跳躍點返回。如果直線沒找到，那麼就一樣繼續按對角方向遞歸尋找跳躍點，並返回那個跳躍點。

㈥ 演算法 & 數據結構——導航網格

這是之前寫的尋路演算法 《柵格導航尋路》

生成網格：
將區域用多邊形劃分，產生可用於尋路的網格信息。通前枯常多邊形的頂點都是有序的，這樣有利於演算法實現。其次雖然多邊形的大小不用一致，但使用大小相差不大的多邊形也有利於演算法實現。

搜索路徑：
通過任意一種尋路演算法，從網格信息中鎖定一組網格路徑，這組網格路徑就是導航網格，再通過這組導航網格確定一條最快的路徑。

本文使用相關演算法與數據結構：
網格生成演算法：德洛內三角剖分
鎖定導航網格演算法：A*
導航網格尋路演算法：拐角演算法

參考博文中是這樣描述的：

思路還算簡單。

運行效果：

內部有圓圈的三角形為可走區域，空白為不可走區域，紅圈表示被鎖定的導航網格，紅線是最優梁圓路徑。

GitHub 包含橡悔塌尋路&網格生成兩部分，附帶已編譯好的exe文件bin/目錄下

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

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

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

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

A Star一般使用場景：

• 策略游戲的策略搜索

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

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

Navigation一般使用場景：

• 游戲場景的怪物尋路

• 動態規避障礙

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

AStar的話，

㈧ mesh的map設置

Mesh Map是指根據已知點的位置和它們之間的連接關系，構建一個圖形結構或者地圖結構。在游帶困明戲中，Mesh Map通常會用於路徑規劃和碰撞檢測等方面，是非常重要的一種數據結構。以下是Mesh Map的設置步驟：

1. 創建一個MeshMap數據結構，並初始化所有節點。蠢告節點包括二維平面上的網格坐標和一個節點類型。

2. 對於每個節點，查找它與相鄰節點之間的連接關系，建立相應的邊。可以使用A*尋路演算法、Dijkstra演算法等方法來確定兩個節點之間的最短路徑。

3. 對於多個MeshMap，可以使用Merge演算法將各個MeshMap合並成一個更大的MeshMap。

4. 使用MeshMap進行路徑規劃，並且可以通過MeshMap上的節點來確定是否到達了目標位置。

5. 針對不同的游戲場景，需要對MeshMap進行尺侍不斷的優化，以確保其具有更高的效率和精度。例如，可以將MeshMap劃分為不同的區域，並為不同區域設置不同的參數