Unity实现BStar寻路欢迎了解BStar寻路算法想象空间BStar寻路的优势BStar寻路的劣势路径优化的方案空间优化的方案

89 阅读 0 评论 59 点赞

我是靠谱客的博主朴实指甲油，这篇文章主要介绍Unity实现BStar寻路欢迎了解BStar寻路算法想象空间BStar寻路的优势BStar寻路的劣势路径优化的方案空间优化的方案，现在分享给大家，希望可以做个参考。

BStarFindPath

欢迎了解BStar寻路算法
想象空间
BStar寻路的优势
BStar寻路的劣势
路径优化的方案
空间优化的方案

欢迎了解BStar寻路算法

BStar算法归于人工智能或人工生命一类，是让对象呈现出拥有生命一般，朝着目标点移动并绕开障碍物，如果目标点被障碍物包围则停留在附近点。

想象空间

可以将BStar寻路想象成一个朝目标前进的贪吃蛇，如果遇到障碍就会分裂成2条贪吃蛇，一左一右绕开障碍，绕开障碍后继续向目标点移动，只要有一条蛇到达目标点即寻路结束。

这里我们需要三类蛇来满足我们的设计需求：

自由蛇（向目标点前进，遇到障碍会分裂成左转蛇和右转蛇）
左转蛇（只考虑绕着障碍左转，一直到绕出障碍变成自由蛇或者遇到已经绕过的路消失）
右转蛇（只考虑绕着障碍右转，一直到绕出障碍变成自由蛇或者遇到已经绕过的路消失）

可以想象在复杂的地形下，会出现很多蛇，最终先到终点的蛇就是我们要找的路径。

下图只有自由蛇（2N - 10N） N代表自由蛇
在这里插入图片描述
下图开始是自由蛇（2N-5N）撞墙后变成了左转蛇和右转蛇绕开障碍，绕开后变成自由蛇奔向终点。

BStar寻路的优势

目标点在封闭空间内时，BStar效率优势明显
在这里插入图片描述
目标点在需要绕路的空间内时，BStar效率优势明显

BStar寻路的劣势

贴近障碍走的问题严重，特别喜欢贴墙走。上文提到BStar算法归于人工智能或人工生命一类在此处可见一斑，大家仔细观察生活中很多人虽然绕路也是喜欢贴墙走的。

仔细观察灰色部分BStar的原始寻路数据，不难发现贴着墙走的问题严重。
在这里插入图片描述
大局观的缺失，因为BStar寻到的不是最优解

路径优化的方案

1、对寻得的原始路径进行smooth处理，提取其中的可行关键点以减少贴墙的问题

下图中黄色的点为关键路径点
在这里插入图片描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
        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;
                    }
                }
            }
        }

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    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)); }
        }
    }
    
	................
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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)); }
        }
    }
    
	................
}