BStarFindPath

• 歡迎了解BStar尋路算法
• 想象空間
• BStar尋路的優勢
• BStar尋路的劣勢
• 路徑優化的方案
• 空間優化的方案

歡迎了解BStar尋路算法

BStar算法歸于人工智能或人工生命一類，是讓對象呈現出擁有生命一般，朝著目標點移動并繞開障礙物，如果目標點被障礙物包圍則停留在附近點。

想象空間

可以將BStar尋路想象成一個朝目標前進的貪吃蛇，如果遇到障礙就會分裂成2條貪吃蛇，一左一右繞開障礙，繞開障礙后繼續向目標點移動，只要有一條蛇到達目標點即尋路結束。

這里我們需要三類蛇來滿足我們的設計需求：

自由蛇（向目標點前進，遇到障礙會分裂成左轉蛇和右轉蛇）

左轉蛇（只考慮繞著障礙左轉，一直到繞出障礙變成自由蛇或者遇到已經繞過的路消失）

右轉蛇（只考慮繞著障礙右轉，一直到繞出障礙變成自由蛇或者遇到已經繞過的路消失）

可以想象在復雜的地形下，會出現很多蛇，最終先到終點的蛇就是我們要找的路徑。

下圖只有自由蛇 （2N - 10N） N代表自由蛇

下圖開始是自由蛇（2N-5N）撞墻后變成了左轉蛇和右轉蛇繞開障礙，繞開后變成自由蛇奔向終點。

BStar尋路的優勢

目標點在封閉空間內時，BStar效率優勢明顯

目標點在需要繞路的空間內時，BStar效率優勢明顯

BStar尋路的劣勢

貼近障礙走的問題嚴重，特別喜歡貼墻走。上文提到BStar算法歸于人工智能或人工生命一類在此處可見一斑，大家仔細觀察生活中很多人雖然繞路也是喜歡貼墻走的。

仔細觀察灰色部分BStar的原始尋路數據，不難發現貼著墻走的問題嚴重。

大局觀的缺失，因為BStar尋到的不是最優解

路徑優化的方案

1、對尋得的原始路徑進行smooth處理，提取其中的可行關鍵點以減少貼墻的問題

下圖中黃色的點為關鍵路徑點

if (bstar_finded_src_way.Count >= 2){WayNode a = bstar_finded_src_way[L];pricallback_finded_one_way.path_way.Add(a);while (find_next == 1){find_next = 0;for (int j = L + 17; j > L; j--){if (j >= bstar_finded_src_way.Count) continue;WayNode b = bstar_finded_src_way[j];if (CheckPathLine(a, b) == true){a = b;L = j;find_next = 1;pricallback_finded_one_way.path_way.Add(a);break;}}}} public void SmoothPath(){//Husunren 再次優化路徑smooth處理，計算可達性，去掉中間的點int L = 0, ans = 0; //Husunren 這里的ans是為了迭代過深造成的性能問題的優化while (L + 2 < path_way.Count){WayNode a = path_way[L];WayNode b = path_way[L + 1];WayNode c = path_way[L + 2];if (ans < 7 && BStarPath.CheckOtherAnglePathLine(a, c) == true){path_way.Remove(b);ans++;}else{L++;ans = 0;}}}

2、對于BStar尋路沒有大局觀的優化，可以加入途徑點的概念，上層先進行一次大致位置的尋路，再由BStar來負責細致的尋路。
下圖是1000,000個格子的大世界尋路，先進行一次洲的尋路計算出路徑點，再由BStar進行點到點之間的尋路

大家可以看到在1000x1000的地圖中，從左上尋路到右下，耗時是2ms左右，證明了BStar尋路性能的優越。

空間優化的方案

在格子數量過多的情況下，我們需要對尋路的數據進行壓縮以達到比較合理的空間利用。
這里我采用了位壓里處理。將1,000,000個格子的數據壓到4mb的內存中，以減少內存的浪費。

public struct BPathCell {public int Reset_data;const int ResetData_Road_LT_Offset = 0;const int ResetData_Road_LT_Mask = 0x1 << ResetData_Road_LT_Offset;const int ResetData_Road_LB_Offset = 1;const int ResetData_Road_LB_Mask = 0x1 << ResetData_Road_LB_Offset;const int ResetData_Road_RB_Offset = 2;const int ResetData_Road_RB_Mask = 0x1 << ResetData_Road_RB_Offset;const int ResetData_Road_RT_Offset = 3;const int ResetData_Road_RT_Mask = 0x1 << ResetData_Road_RT_Offset;const int ResetData_BackDir_Offset = 12;const int ResetData_BackDir_Mask = 3 << ResetData_BackDir_Offset;public int back_dir{get{return ((Reset_data & ResetData_BackDir_Mask) >> ResetData_BackDir_Offset);}set{unchecked { Reset_data = ((Reset_data & ~ResetData_BackDir_Mask) | (value << ResetData_BackDir_Offset)); }}}const int ResetData_g_Offset = 16;const int ResetData_g_Mask = 0xFFFF << ResetData_g_Offset;public int g{get{return ((Reset_data & ResetData_g_Mask) >> ResetData_g_Offset);}set{unchecked { Reset_data = ((Reset_data & ~ResetData_g_Mask) | (value << ResetData_g_Offset)); }}}public int road_LT{get{return ((Reset_data & ResetData_Road_LT_Mask) >> ResetData_Road_LT_Offset);}set{unchecked { Reset_data = (int)((Reset_data & ~ResetData_Road_LT_Mask) | (value << ResetData_Road_LT_Offset)); }}}................ }

作者：胡孫仁
Author: HuSunren(FD.Creator) QQ: 75567044
email: aveking@qq.com aveking@163.com
Copyright ? 2020 tel: 18616334412

總結

以上是生活随笔為你收集整理的Unity实现BStar寻路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。