歡迎了解BStar尋路演算法

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

想象空間

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

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

1. 自由蛇（向目標點前進，遇到障礙會分裂成左轉蛇和右轉蛇）
2. 左轉蛇（只考慮繞著障礙左轉，一直到繞出障礙變成自由蛇或者遇到已經繞過的路消失）
3. 右轉蛇（只考慮繞著障礙右轉，一直到繞出障礙變成自由蛇或者遇到已經繞過的路消失）

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

下圖只有自由蛇 （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