一：客戶端navmesh 和 服務(wù)端A*算法的轉(zhuǎn)換

這是以前項(xiàng)目用到的C#版的navmesh。從那個開源的C++版本navmesh改過來的

timotimosky/-Navmesh_Csharp

public void Sync(){//判斷是否處于尋路//if (LocusPoints.Count < 2){return;}//獲取下一個路徑點(diǎn)//Vector3 nextPosition = LocusPoints[0];Vector3 nextPosition2 = LocusPoints[1];//如果兩者大于一個格子，則插點(diǎn)//if (Vector3.Distance(nextPosition ,nextPosition2) > 0.5f){// * 方向//Vector3 directionVector3 = nextPosition2 - nextPosition;//預(yù)測下一個路徑點(diǎn)//Vector3 targetVector3 = directionVector3.normalized * 0.5f + nextPosition;if (targetVector3.x == 0 && targetVector3.z == 0) LocusPoints.Insert(1, targetVector3);}//TODo：和服務(wù)端同步一次位置////記錄上一個出發(fā)點(diǎn)，用于平滑路徑NewLocusPointRotation = SelectedLightProjector.transform.rotation;NewLocusPointPosition = SelectedLightProjector.transform.position;NewLocusPointStartTime = Time.fixedTime;mFollowWayPointsState.begin = true;}

上面這段代碼，實(shí)際上就是每隔一定距離，就對Navmesh的路徑點(diǎn)進(jìn)行插點(diǎn)，然后轉(zhuǎn)換為A星的格子位置。

二: A*算法的障礙碰撞

一般的A*算法代碼是把所有障礙當(dāng)做一個格子。但某些時候有的物體大，有的物體小，碰撞范圍大小不一，那么需要動態(tài)傳遞參數(shù)

public bool CanReach(int x, int y) {///加入自身碰撞器后，需要判斷該點(diǎn)周圍 全無阻擋///for (int i=-selfBlock; i<=selfBlock; i++){for(int j=-selfBlock; j<=selfBlock; j++){if(MazeArray[x+i, y+j]<=0)return false;}}return true; }

三：客戶端navmesh 和 A*算法的混用

因?yàn)轫?xiàng)目的某些需求，使用單一的尋路方式，性能或者效果可能不好，那么可以混用幾種尋路方式。

兩種思路:

1.使用navmesh檢測靜態(tài)障礙，在這段代碼內(nèi)部，再使用A*專門檢測動態(tài)障礙，調(diào)整navmesh的路徑。

2. 因?yàn)橐恍┨厥庑枨?#xff0c;比如尋找NPC，使用navmesh檢測長范圍的尋路，在路徑的最后一段，使用A*檢測小范圍的障礙。

三：優(yōu)化特定需求的A*算法

1.平滑A型算法的路徑

2.A*算法的格子靜態(tài)合并、優(yōu)化A*算法的尋路性能

3. A*尋路向navmesh尋路的演進(jìn)（navmes設(shè)計思路）

4.A*工具化

平滑A型算法的路徑

如圖1

我使用一種簡單的情況來說明，假設(shè)在地圖上尋路，如果從A點(diǎn)（灰色格子）尋到X點(diǎn)，那么使用普通A*算法尋路出來可能是這樣的
現(xiàn)在格子很不規(guī)則，我們想使路徑平滑，一般采用的策略是數(shù)個角度差異較大的路徑點(diǎn)之間，通過插點(diǎn)，替換路徑點(diǎn)，來實(shí)現(xiàn)。
我們現(xiàn)在采用另一種方式，

步驟1：
先對所有路徑點(diǎn)循環(huán)，如果兩個頂點(diǎn)，比如B-C矢量為垂直/平行 于地圖起始的 1-2頂點(diǎn)矢量，則 B-C頂點(diǎn)合并。

圖片2

我們可以看到，B-C-D-E與1-2頂點(diǎn)矢量平行，所以可以合并為BCDE點(diǎn)，F-G點(diǎn)與1-2頂點(diǎn)矢量垂直，所以F-G合并為FG點(diǎn)。（這里要注意， ABCDE---F矢量 與ABCDE本身矢量不同，不能再合并。所以中斷合并，從F點(diǎn)重新判斷，F和G點(diǎn)合并了）

步驟2：
最后我們原本的路徑點(diǎn)為： A-B-C-D.....-Y-X 一共10多個路徑點(diǎn)， 合并后，為 ABCDE--FG---HOI---JKM---NOX 一共五個點(diǎn)，路徑點(diǎn)大大減少
雖說對行走效率有一定優(yōu)化，但人物按這個路徑點(diǎn)來行走，路線并沒有平滑。

步驟3：
其實(shí)我們可以將ABCDE當(dāng)做一個大方塊，同樣的道理，所以這個尋路路徑變成了5個大方塊的尋路。
我們先將我們理想中的平滑路徑畫出來，現(xiàn)在看圖3

其實(shí)我們可以看到黃色路徑比較接近我們的想法。
但是黃色點(diǎn)，并不在我們的尋路結(jié)果內(nèi)，所以我們要將黃色點(diǎn)納入我們的五個大方塊里去，
于是成了圖3的樣子，我們用綠色格子將黃色部分納入。
我們可以發(fā)現(xiàn)，其實(shí)現(xiàn)在變成了3個更大的方塊（紅色圈內(nèi)）的尋路。我們把三個圈命名為 a b c.
5個大方塊朝3個更大方塊的演進(jìn)，實(shí)際上是將拐角磨平（比如FGH的拐角被納入第二個紅圈內(nèi)了）
實(shí)際上，就是判斷，當(dāng)矢量FG與下一個點(diǎn)H有拐角時，判斷FG與H點(diǎn)的斜上方所有點(diǎn)是否可走，如果可走，則FG與H點(diǎn)可以合并成一個大方塊。
則 我們計算把 a- b - c 三個長方形的公共點(diǎn)(如果有公共邊，則公共邊的中點(diǎn)為公共點(diǎn)，如果只有相鄰角，則角作為這個圈到下一個圈的路徑點(diǎn))作為必經(jīng)點(diǎn)
則新的路徑形成， a長方形終點(diǎn) - b長方形起 ---- c起點(diǎn)---x(x屬于C內(nèi)部)

其實(shí)，到這里為止，這已經(jīng)是一個簡化版的動態(tài)navmesh尋路算法。

navmesh也是多個區(qū)域塊行走。但不是使用矩形，而是使用三角形。
navmesh的三角形有一個嚴(yán)格規(guī)定，每個三角形的三個頂點(diǎn)所形成的圓形內(nèi)不能包含其他三角形的頂點(diǎn)（delaunay算法?http://baike.baidu.com/link?url=m1uEA28GLx-NjrhXlozvcJ03-hmXTIUMo03D99bf-4_nEF7Rsrd2h6F-Pq9HpVatIWlQNSOWfMmZs6jlLP5KkK）
這樣做有個好處，其實(shí)navmesh的實(shí)際路徑不是從一個三角型尋路到另一個三角型，本質(zhì)上是從一個圓到另一個圓，圓與圓之間有且只有一個交點(diǎn)，這樣保證了在很多情況下路徑比矩形尋路更短更平滑（長方形無法形成一個不包含其他長方形頂點(diǎn)的圓，所以相鄰矩形的內(nèi)部路徑之間的夾角更大）

所以如果我們把矩形拆分成三角型，更接近U3D自帶的navmesh算法。

U3D的navmesh烘焙，是讀取網(wǎng)格數(shù)據(jù)后，使用該delaunay算法直接生成三角型，剩余步驟相同。

A*算法的格子靜態(tài)合并
剛才是先進(jìn)行尋路，再進(jìn)行格子的動態(tài)合并，對效率影響很大，其實(shí)將上面的合并步驟拿出來，使用地圖格子之前，先對所有地圖格子進(jìn)行合并，然后生成一個很多矩形的新地圖格子。
即可達(dá)成格子的靜態(tài)合并。 然后使用中，直接使用這些格子進(jìn)行A*尋路，能大大提高效率。但是，靜態(tài)合并后，如果不單獨(dú)處理動態(tài)障礙，無法識別動態(tài)障礙，這也是NAVmesh的通病。

A*地圖格子生成工具化
簡單說，
1.將所有地圖上可行走區(qū)域設(shè)置為（walk層級），障礙的層級設(shè)置為nowalk
2.用攝像機(jī)對地圖循環(huán)掃描（每次掃描x坐標(biāo)+1，下一次y+1,輪流加坐標(biāo)），掃描到walk，xml上寫0，掃描到nowalk，xml上寫1.
（當(dāng)然，還可以有減速行走的沼澤，則xml可以寫2，以此類推，可以無限多地形。順便提一句，草叢視野的實(shí)現(xiàn)，比如可以將草叢部分設(shè)置為3，人物中心點(diǎn)處于草叢格子，則判斷人物進(jìn)入草叢。）

總結(jié)

以上是生活随笔為你收集整理的寻路算法1：A星寻路和navmesh寻路的技巧和优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。