游戲腳本0尋路演算法
㈠ unity2d 做橫版平台游戲有什麼好的尋路演算法或插件
並沒一種尋路適合所有場合，選擇都是基於需求而定的。
1. A* 演算法與貪婪演算法不一樣，貪婪演算法適合動態規劃，尋找局部最優解，不保證最優解。
A*是靜態網格中求解最短路最有效的方法。也是耗時的演算法，不宜尋路頻繁的場合。一般來說適合需求精確的場合。
與啟發式的搜索一樣，能夠根據改變網格密度、網格耗散來進行調整精確度。
使用的地方：
a. 策略游戲的策略搜索
b. 方塊格子源殲肆雹轎游戲中的格子尋路
2. Unity 自帶的導航網格系統
Unity 內置了NavMesh導航網格改告系統，一般來說導航網格演算法大多是「拐角點演算法」。
效率是比較高的，但是不保證最優解演算法。
使用的地方：
a.游戲場景的怪物尋路
b.動態規避障礙
㈡ 夢幻西遊自動尋路的尋路演算法怎麼算
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*演算法——啟發式路徑搜索
A*是一種路徑搜索演算法，比如為游戲中的角色規劃行動路徑。
A* 演算法的輸入是， 起點（初始狀態） 和 終點（目標狀態） ，以及兩點間 所有可能的路徑 ，以及涉及到的 中間節點（中間狀態） ，每兩個節點間的路徑的 代價 。
一般還需要某種 啟發函數 ，即從任意節點到終點的近似代價，啟發函數能夠非常快速的估算出該代價值。
輸出是從 起點到終點的最優路徑 ，即代價最小。同時，好的啟發函數將使得這一搜索運算盡可能高效，即搜索盡量少的節點/可能的路徑。
f(n)=g(n)+h(n)
f(n) 是從初始狀態經由狀態n到目標狀態的代價估計
g(n) 是在狀態空間中從初始狀態到狀態n的實際代價
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價
A*演算法是從起點開始，檢查所有可能的擴展點（它的相鄰點），對每個點計算g+h得到f，在所有可能的擴展點中，選擇f最小的那個點進行擴展，即計算該點的所有可能擴展點的f值，並將這些新的擴展點添加到擴展點列表（open list）。當然，忽略已經在列表中的點、已經考察過的點。
不斷從open list中選擇f值最小的點進行擴展，直到到達目標點（成功找到最優路徑），或者節點用完，路徑搜索失敗。
演算法步驟：
參考
A* 演算法步驟的詳細說明請參考 A*尋路演算法 ，它包含圖文案例清楚的解釋了A*演算法計算步驟的一些細節，本文不再詳細展開。
看一下上面參考文檔中的案例圖，最終搜索完成時，藍色邊框是close list中的節點，綠色邊框是open list中的節點，每個方格中三個數字，左上是f（=g+h），左下是g（已經過路徑的代價），右下是h（估計未經過路徑的代價）。藍色方格始終沿著f值最小的方向搜索前進，避免了對一些不好的路徑（f值較大）的搜索。（圖片來自 A*尋路演算法 ）
現在我們可以理解，A*演算法中啟發函數是最重要的，它有幾種情況：
1) h(n) = 0
一種極端情況，如果h(n)是0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑。但效率不高，因為得不到啟發。
2) h(n) < 真實代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就得越慢。越接近Dijkstra演算法。
3) h(n) = 真實代價
如果h(n)精確地等於從n移動到目標的代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（譯者：指讓h(n)精確地等於實際值）。只要提供完美的信息，A*會運行得很完美，認識這一點很好。
4) h(n) > 真實代價
如果h(n)有時比從n移動到目標的實際代價高，則A*不能保證找到一條最短路徑，但它運行得更快。
5) h(n) >> 真實代價
另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。
關於啟發函數h、Dijkstra演算法、BFS（最佳優先搜索）演算法、路徑規劃情況下啟發函數的選擇、演算法實現時List的數據結構、演算法變種等等更多問題，請參考： A*演算法
㈣ 製作游戲輔助：用按鍵精靈如何確定人物朝向
按鍵學院實戰班前段時間沸沸揚揚的講解著自動尋路教程。今天，咱也來跟大家分享分享，實戰班自動尋路思路之——確定人物朝向（箭頭的方向角度）。
不少網路游戲已經支持自動尋路，玩家只需要設定終點後，游戲人物即可自動尋路，但是碰到某些未自帶自動尋路功能的游戲，就呵呵呵了……
院刊今天跟大家分享兩款熱門游戲的人物朝向判定~~知道了人物朝向，再知道目標的朝向，不就知道怎麼自動尋路了嘛~
按鍵學院實戰班的07老師整理了自動尋路的三要素，給大家分享：
自動尋路一般需要確定三個要素：
確定路線
確定朝向
確定位置
確定了人物位置和物品位置，再確定了人物的朝向，與目標路線。將人物轉向目標就可以用腳本實現自動尋路的功能。
劍靈模式的地圖的尋路：游戲畫面右上角有小地圖，地圖中灰白色箭頭代表人物。
斜率：已知A、B點坐標，求直線AB的斜率。
斜率公式k=(y1-y2)/(x1-x2)，即兩個坐標縱坐標之差，除以兩個坐標橫坐標之差。
正切函數：正切函數是直角三角形中，對邊與鄰邊的比值。
在上圖中，即tanα=b/a=(y2-y1)/(x2-x1)。在按鍵精靈中為Tan函數。
通過公式對比，我們可以知道，直線AB的斜率，即角α的正切值
角度：已知角α的正切值，我們可以通過反三角函數公式，來計算這個角度的值。
α=arctan(k)。在按鍵精靈中為Atn函數。
反三角函數：即相對應的正弦、餘弦、正切、餘切為x的角。
如何實現箭頭角度計算：
從上面的三角函數知識拓展中，我們知道，要計算一個角度，可以通過計算該角度的正切值，再通過反三角函數來求這個角度。
那麼，在按鍵精靈的代碼中如何實現呢？
思路：
1.通過找圖找色命令，找到箭頭頂部A的坐標，以及箭頭底部中間B的坐標。
2.構建直角三角形。確定箭頭的指向的角度α。
3.通過斜率/正切函數，來計算角度α的正切值。
4.通過反三角函數，來得出角α的角度值。
代碼實現：
『在劍靈右上角的小地圖里找色/找圖，箭頭坐標存儲在(x1,y1)，箭尾坐標存儲在(x2,y2)
FindColor1200,0,1920,300,"箭頭顏色",x1,y1
Ifx1>0Andy1>0Then
EndIf
FindColor1200,0,1920,300,"箭尾顏色",x2,y2
Ifx1>0Andy1>0Then
EndIf
'計算斜率/正切值
斜率=(y1-y2)/(x1-x2)
'計算角度
角度=Atn(斜率)
當然，自動尋路並不是單一的方式，不同游戲的地圖不同，尋路的方式不同。但是運用到的數學知識和思路是共同的。當然，有些特定的地圖有更便捷的方式，例如最終幻想14的地圖。下一期的院刊，再跟大家分享另一些不同的地圖的尋路方式~~