最快的尋路計算方法

Ⅰ 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

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*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

Ⅱ 星際爭霸2的尋路演算法思路是怎樣的

首先地圖整體開始前，會用多層可達矩陣演算法，算出路徑關鍵點
2，創建關鍵節點可達矩陣
3，再每個兵當前位置對關鍵節點進行路徑計算
這樣可以最小化資源佔用就可以完成路徑計算了，高數的離散數學，挺容易解的

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

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列表
?

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

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)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。
}

Ⅳ 從原點出發，遍歷50個點，再回到原點的最短路徑，求matlab程序

據 Drew 所知最短路經演算法現在重要的應用有計算機網路路由演算法，機器人探路，交通路線導航，人工智慧，游戲設計等等。美國火星探測器核心的尋路演算法就是採用的D*（D Star）演算法。

最短路經計算分靜態最短路計算和動態最短路計算。

靜態路徑最短路徑演算法是外界環境不變，計算最短路徑。主要有Dijkstra演算法，A*（A Star）演算法。

動態路徑最短路是外界環境不斷發生變化，即不能計算預測的情況下計算最短路。如在游戲中敵人或障礙物不斷移動的情況下。典型的有D*演算法。這是Drew程序實現的10000個節點的隨機路網三條互不相交最短路真實路網計算K條路徑示例：節點5696到節點3006，三條最快速路，可以看出路徑基本上走環線或主幹路。黑線為第一條，蘭線為第二條，紅線為第三條。約束條件系數為1.2。共享部分路段。 顯示計算部分完全由Drew自己開發的程序完成。 參見 K條路演算法測試程序

Dijkstra演算法求最短路徑：

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

這是在drew 程序中4000個節點的隨機路網上Dijkstra演算法搜索最短路的演示，黑色圓圈表示經過遍歷計算過的點由圖中可以看到Dijkstra演算法從起始點開始向周圍層層計算擴展，在計算大量節點後，到達目標點。所以速度慢效率低。

提高Dijkstra搜索速度的方法很多，據Drew所知，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

推薦網頁：http://www.cs.ecnu.e.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm

簡明扼要介紹Dijkstra演算法，有圖解顯示和源碼下載。

A*（A Star）演算法：啟發式（heuristic）演算法

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的大小，從最小路徑的節點向下進行。
}

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

機器人家上了解到，在二維二值地圖（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* 尋路演算法

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

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

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

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

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

Ⅸ 夢幻西遊 尋路演算法

[HOTKEY]A [NAME]壓鏢大大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至獅王洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 65 35 [SCRIPT]MOVETO 65 6 [SCRIPT]MOVETO 112 20 [SCRIPT]REM 進獅王洞 [SCRIPT]MOVEOUT 118 25 35 [SCRIPT]REM 到達大大王跟前 [SCRIPT]MOVETO 22 12

－－－－－－－－－－－－－－－－－－

[HOTKEY]B [NAME]壓鏢二大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至大象洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 52 78 [SCRIPT]MOVETO 20 82 [SCRIPT]REM 進大象洞 [SCRIPT]MOVEOUT 28 84 37 [SCRIPT]REM 到達二大王跟前 [SCRIPT]MOVETO 20 10

－－－－－－－－－－－－－－－－

[HOTKEY]C [NAME]壓鏢三大王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至獅陀嶺線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 20 55 [SCRIPT]REM 進獅陀嶺 [SCRIPT]MOVEOUT 6 49 34 [SCRIPT]REM 獅陀嶺至老雕洞線路 [SCRIPT]MOVETO 108 58 [SCRIPT]MOVETO 55 60 [SCRIPT]MOVETO 30 48 [SCRIPT]REM 進老雕洞 [SCRIPT]MOVEOUT 13 43 36 [SCRIPT]REM 到達三大王跟前 [SCRIPT]MOVETO 15 12

－－－－－－－－－－－－－－－－

[HOTKEY]D [NAME]壓鏢牛魔王 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至牛魔寨線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]MOVETO 35 42 [SCRIPT]MOVETO 72 105 [SCRIPT]REM 進牛魔寨 [SCRIPT]MOVEOUT 54 116 38 [SCRIPT]REM 獅陀嶺至魔王居線路 [SCRIPT]MOVETO 35 65 [SCRIPT]MOVETO 78 65 [SCRIPT]MOVETO 88 70 [SCRIPT]REM 進魔王居 [SCRIPT]MOVEOUT 93 73 39 [SCRIPT]REM 到達牛魔王跟前 [SCRIPT]MOVETO 20 12

－－－－－－－－－－－－－－－－

[HOTKEY]E [NAME]壓鏢楊戩 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至天宮線路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 對話天將 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宮至靈宵寶殿線路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 進靈宵寶殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到達楊戩身旁 [SCRIPT]MOVETO 56 28

－－－－－－－－－－－－－－－－－

[HOTKEY]F [NAME]壓鏢李靖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 3 13 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 395 190 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至天宮線路 [SCRIPT]MOVETO 21 58 [SCRIPT]REM 對話天將 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 23 55 [SCRIPT]REM 天宮至靈宵寶殿線路 [SCRIPT]MOVETO 150 60 3 3 31 [SCRIPT]REM 進靈宵寶殿 [SCRIPT]MOVEOUT 144 64 32 [SCRIPT]REM 到達李靖身旁 [SCRIPT]MOVETO 32 36

－－－－－－－－－－－－－－－－－

[HOTKEY]G [NAME]壓鏢普提老祖 [CONTENT] [SCRIPT]BEGINMOVE FAST [SCRIPT]MOVETO 23 14 [SCRIPT]REM 出鏢局 [SCRIPT]MOVEOUT 2 12 5 [SCRIPT]REM 長安至大唐國境線路 [SCRIPT]MOVETO 500 135 [SCRIPT]MOVETO 505 190 [SCRIPT]MOVETO 390 195 [SCRIPT]MOVETO 282 138 [SCRIPT]MOVETO 125 60 [SCRIPT]MOVETO 30 20 [SCRIPT]REM 出長安 [SCRIPT]MOVEOUT 4 3 4 [SCRIPT]REM 大唐國境至大唐境外線路 [SCRIPT]MOVETO 300 88 [SCRIPT]MOVETO 255 30 [SCRIPT]MOVETO 120 43 [SCRIPT]MOVETO 23 72 [SCRIPT]REM 出大唐國境 [SCRIPT]MOVEOUT 8 86 44 [SCRIPT]REM 大唐國境至長壽郊外線路 [SCRIPT]MOVETO 622 83 [SCRIPT]MOVETO 600 65 [SCRIPT]MOVETO 575 78 [SCRIPT]MOVETO 539 102 [SCRIPT]MOVETO 525 66 [SCRIPT]MOVETO 578 28 [SCRIPT]MOVETO 560 3 [SCRIPT]MOVETO 405 10 [SCRIPT]MOVETO 330 48 [SCRIPT]MOVETO 338 82 [SCRIPT]MOVETO 318 86 [SCRIPT]MOVETO 285 83 [SCRIPT]MOVETO 282 45 [SCRIPT]MOVETO 264 20 [SCRIPT]MOVETO 200 20 [SCRIPT]MOVETO 82 48 [SCRIPT]MOVETO 55 15 [SCRIPT]REM 對話南瞻部洲土地 [SCRIPT]CLEAR TALKNPC [SCRIPT]TALKNPC 52 15 [SCRIPT]REM 長壽郊外至長壽村線路 [SCRIPT]MOVETO 45 30 [SCRIPT]MOVETO 60 65 [SCRIPT]MOVETO 125 90 [SCRIPT]MOVETO 150 152 [SCRIPT]REM 進長壽村 [SCRIPT]MOVEOUT 154 162 28 [SCRIPT]REM 長壽村至方寸山線路 [SCRIPT]MOVETO 132 166 [SCRIPT]MOVETO 102 195 [SCRIPT]REM 出長壽村 [SCRIPT]MOVEOUT 111 206 29 [SCRIPT]REM 方寸山至靈台宮線路 [SCRIPT]MOVETO 126 26 [SCRIPT]MOVETO 135 60 [SCRIPT]MOVETO 55 90 [SCRIPT]MOVETO 125 130 [SCRIPT]REM 進靈台宮 [SCRIPT]MOVEOUT 125 136 30 [SCRIPT]MOVETO 39 25
如果是這個腳本 請採納我的 謝謝

Ⅹ 野外尋路

1、平時參考地圖和指南針，同時積極觀察周圍的地形以及身邊的植物來判斷正確位置。

2、利用太陽

冬季日出位置是東偏南，日落位置是西偏南；夏季日出位置是東偏北，日落位置是西偏北；春分、秋分前後，日出正東，日落正西。

只要有太陽，就可以使用手錶來辨別方向。按24小時制讀出當時的時刻，將小時數除以二，將得到一個小時數。把手錶水平放在手上或者地上，讓手錶的這個時刻對准太陽所在的方位，這時手錶表面12點所指的方向是北方，6點所指的方向是南方。

立竿見影，在地上垂直樹立一根桿子，上午影子指向西北，下午影子指向東北，影子最短時是正中午，這時影子指向正北方。

3、利用星星

以北極星為目標。首先找勺狀的北斗七星，以勺丙上的兩顆星的間隔延長5倍，就能再此直線上找到北極星，北極星所在的方向就是正北方。

4、利用地物判斷方位。

獨立的大樹通常南面枝葉茂盛，樹皮光滑，北面樹枝稀疏樹皮粗糙。其南面，通常青草茂密，北面叫潮濕，長有青苔。

建築物和土堆等，北面積雪多融化慢，而土坑等凹陷地方則相反。

中國北方較大的廟宇，寶塔的正門和農村獨立的房屋的門窗多向南開放。

森林中空地的北部邊緣青草較茂密。樹樁斷面的年輪，一般南面間隔大，北面間隔小。

在中國北方草原，沙漠地區西北風較多，在草叢附近常形成許多雪龍，沙龍，其頭部大，尾部小，頭部所指的方向是西北。

草原上蒙古包的門多向南開放。樹葉稀疏一面為南，濃密一面為北
樹樁年輪濃密一面為北
別針沾上油脂放於水坑中，尖頭指北

1.獨株樹的陽面（即朝南方向）枝葉茂盛，而陰面（即朝北方向）枝葉較稀疏。

2.在密林中，岩石南面較干，而岩石北面較濕且有青苔。

3.桃樹、松樹分泌膠脂多在南面。

4.樹墩的年輪，朝南的一半較疏，而朝北的一半較密。

5.山溝或岩石等物體積雪難以融化的部位，總是在朝北的方向上。

6.螞蟻的洞穴多在大樹的南面，而且洞口朝南。

7.一些自然村落一般都是集中在山的南側，而且大門多數是朝南開的。一般古廟、古塔、祠堂等建築物都是坐北朝南的。

8.若是夜晚天空可看到的星星，只要找到北斗七星，沿著「勺柄」的延伸線可找到明亮的北極星，北極星的方向便是正北的方向。

利用太陽
在晴朗的白晝，根據日出、日落就可以很方便地知道東方和西方，也就可判斷方，但只能是大致的估計，較准確的測定有下列幾種方法：
1、手錶測向「時數折半對太陽，12指的是北方」，一般在上午9時至下午4時之間可以很快地辨別出方向，用時間的一半所指的方向對向太陽，12時刻度就是北方，如下午14:40的時間，其一半為7:20，把時針對向太陽，那麼12指的就是北方，或者是把表平置，時針指向太陽，時針與12時刻度平分線的反向延伸方向就是北方；或者置手錶，將一根小棍垂直立在手錶中央轉動手錶，使小棍的影子與時針重合，時與12時刻度之間的平分線即是北方。地球24小時自轉360度，故1小時為15度，而手錶轉一周360度為12小時，即較太陽快1倍，這樣可用手錶與太陽粗略測定方位。早晨6時太陽在東方，影子指向西方，將表盤時針6指向太陽，表盤上12便指向西方；如將表盤順轉90度，即將6除2為3，則3指向太陽，此時12便指北方；同樣在中午12時，太陽位於南方，將12除2為6，則6指向太陽，則12便指北方。依此法測定方向缺點是最好要考慮地方時差，以免出現方位的偏差，但不妨作為大概方位的簡易判斷。
必須注意：
（1）判定方向時，手錶應平置；
（2）在南、北緯20°30′之間地區的中午前後不宜使用，即以標准時的經線為准，每向東15°加1小時，向西15°減1小時。
2、日影測向為晴天，在地上豎立一木棍，木棍的影子隨太陽位置的變化而移動，這些影在中午最短，其末端的連線是一條直線，該直線的垂直線為南北方向。
在一張50×50cm的繪圖紙上繪制一系列同心圓，同心圓的半徑以1cm遞增，釘在平板上並水平固定好，將一根12-15cm長的細鋼針或針狀物垂直插在圓心上。當太陽位置變化時，影子的端點總會與同心圓相交，標繪出這些點，然後把同一個圓上的兩點直線相連，把這些直線的中點與圓心相連，這條連線就是南北方向線，圓弧頂的方向為北方。
3、夜間星體
當夜晚時，可根據北極星和南十字星來判斷方向。
1、北極星北極星位於正北天空，其出露高度角相當於當地緯度，據此可以很快找到北極星。通常根據北斗七星（大熊星座）或w星（仙後星座）確定。
北斗星為七顆較亮的星，形狀象一把勺子，將勺頭兩顆β向α連線並延伸約5倍處便是北極星。
當看不到北斗星時，可根據w星，即仙後星座尋找北極星。
仙後星座由五顆較亮的星組成，形狀象「w」字母，字母的開口方向約開口寬度的兩倍距離處是北極星。
2、南十字星
在北緯23°30′以南地區，夜間有時可見南十字星，由四顆較亮的星組成，形同「十」字，在其右下方，由γ向α兩星連線長度的四倍半處（無星）為正南方向。
4、地物和植物特徵
有時野外的一些地物和植物生長特徵是良好的方向標志，增加這方面的知識可以幫助你快速地辨別方向。
1、地物特徵
房屋：一般門向南開，我國北方較大的廟宇、寶塔的正門和農村獨立房屋的門窗多向南開。草原上蒙古包的門多向東南開。
廟宇：通常也是向南開門，尤其廟宇群中的主體建築；
突出地物：向北一側基部較潮濕並可能生長低矮的苔蘚植物。
建築物和土堆等，北面積雪多融化慢，而土坑等凹陷地方則相反。在我國北方草原、沙漠地區刮西北風多，在草原附近常形成許多雪龍、沙龍，其頭部大尾部小，頭部所指的方向是西北。

植物生長特徵
常言道：「萬物生長靠太陽」，掌握這一特徵後，即使在無太陽的陰天也可通過觀察判斷方向。如：大石塊、樹主幹南面的草生長的較旺盛，秋天南面的草也枯萎的較快；樹皮一般為南面的較光滑，北面的較粗糙，有的樹在其北面樹皮上有許多裂紋及疙瘩，這種現象在白樺樹上表現特明顯；松柏類及杉樹在樹幹上流出的膠脂南面的較北面多且易結成較大的塊；秋季里許多果樹朝南的果實結的較多，尤其以蘋果、紅棗、柿子、柑橘等為明顯，果實在成熟時也是朝南的先變色；長在石頭上的青苔喜陰濕，以北面為多旺；積雪的融化多是先融化朝南的一面；
一般陰坡，即北側山坡，低矮的蕨類和藤本植物比陽面更加發育。森林中空地的北部邊緣，青草較茂密。
單個植物的向陽面枝葉較茂盛，向北的陰地樹干則可能生長苔蘚。獨立的大樹通常南面枝葉茂盛，樹皮光滑；北面樹葉稀疏，樹皮粗糙。其南面，通常青草茂盛，北面較潮濕，長有青苔。
我國北方的許多樹木樹乾的斷面可見清晰的年輪，向南一側的年輪較為疏稀，向北一側則年輪較緊密。樹樁斷面的年輪紋，一般是南面間隔大，北面間隔小。
若在陰天迷了路，可以靠樹木或石頭上的苔蘚的生長狀態來獲知方位。在北半球以樹木而言，樹葉生長茂盛的一方即是南方。若切開樹木，年輪幅度較寬的一方濕長著苔蘚的一方即是北方
參考資料：http://..com/question/3238585.html?si=5