1. 前言

我相信绝大多数人是被名字吸引进来的

大多数人内心感受：什么？！居然除了 A* 之外还有一个叫 B* 的算法！？

是的你没看错，本算法就叫 B* ，比 A* 更为快速的寻路算法，一般来说前者耗时通常比后者少十来倍，效率极高，因此通常被选作游戏中怪物寻路的算法。

但是要注意了！（重要内容）

B* 是个启发式算法，而且没有很便捷的方法对其进行适当调整，而得到最优解（A* 可以改变其评估函数来保证最优解），所以千万别在 OI 竞赛中使用，否则会死得非常难看。

至于为什么，接下来的内容会详细讲解，我们马上进入正题吧。

[ A* 内容请见 去年五月 #166 [Thomasguo666 ] A* 算法浅谈 ]

2. 算法介绍

首先提一下本文章所谓的寻路问题：

1. 有 01 网格 (格子上只有数字 0 或 1)

2. 寻找从网格 (S.x,S.y) 处走到 (E.x,E.y) 的较短路

3. 每次只能走上下左右四个格子

4. 不能到达数字为 1 的格子，不能走出网格

[ S 为起点，E 为终点，后面的文章就都这么称呼喽 ]

同学们很容易想到用 A* 瞬间通过，然而值得注意一点，题目要求的为较短路。

也就是说，我们不关心是否是最短路，只要是“较短路”就行了。使用 A* 虽然能得到最短路，但是算法效率与所找路径的“优秀程度”还得加以权衡。

B* 就是这么一个算法，它效率极高，而且可以给出一个“还算不错”的路径。

B* ( Branch Star 分支寻路算法)

发明此算法的计算机学家是受到了自然界动物寻路的启发的。

B* 的大部分行动决策都是依据一个看上去就很不靠谱的“贪心”策略（不知道计算机界“贪心”含义的同学可以忽略这个词）：

朝着目标的位置径直走去就行了

不用考虑任何障碍物因素，直接走过去就行了，撞到障碍物了再说。

但由于这个寻路问题的“径直走”和真实生活的“径直走”有所不同（因为不能斜着走），可以有许多定义。

下面给出几个例子：

1. 当 |S.x-E.x|>=|S.y-E.y| 时横着朝 E 走，反之则竖着朝 E 走。

2. 当 S.x - E.x ≠ 0 时横着朝 E 走，反之则竖着朝 E 走。

3. 用 Breshenham 算法，不在本次讨论范围以内。

4. 函数解析式法，推导比较复杂。

为了代码实现方便，本文使用第一类定义做演示。

[ 如此行走……"#"为障碍物，"."为空格子，"1"为经过的格子 ]

碰到障碍物了怎么办！？

那就以障碍物格子（1 格子）为界，沿着障碍物边缘分别行走形成分支。

走着走着发现绕过障碍物了，就继续之前的“贪心策略”继续走。

直到走到终点即可。

总结一下流程

1. 没有遇到障碍物，“径直”向 E 走去。

2. 碰到障碍物，以障碍物格子为界，沿着障碍物边缘分别行走形成分支以搜索。

3. 走到终点，输出答案。

然后给出 c++ 语言对此算法的实现：

#include<bits/stdc++.h>
using namespace std;

const bool showmap=0;//改为 1 可以逐步查看路径

const int SIZE=500;

const short direx[]={1,0,-1,0};
const short direy[]={0,1,0,-1};

struct Point
{
    int x,y,step;
    short WD,D;
    const bool operator == (Point ob)
    {return x==ob.x && y==ob.y;}
    void Scan () {scanf ("%d %d",&x,&y);}
    void Print() {printf("%d %d\n",x,y);}
    void Walk(short dire)
    {x+=direx[dire],y+=direy[dire];}
    Point Next(short dire)
    {return Point{x+direx[dire],y+direy[dire],step,WD};}
}start,end;

int n,m;
bool mapn[SIZE+5][SIZE+5],visit[SIZE+5][SIZE+5];
queue<Point> B_star;

void maprint(Point ob)//展示路径
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(mapn[i][j]) cout<<setw(3)<<"#";
            else if(Point{j,i}==ob) cout<<setw(3)<<ob.step;
            else if(Point{j,i}==end) cout<<setw(3)<<"E";
            else if(Point{j,i}==start) cout<<setw(3)<<"S";
            else if(visit[i][j]) cout<<setw(3)<<"1";
            else cout<<setw(3)<<".";
        printf("\n");
    }
}

bool NW(Point ob)//near the wall
{
    for(short i=0;i<4;i++)
    {
        Point rear=ob;
        rear.Walk(i);
        if(mapn[rear.y][rear.x]) return 1;
    }
    return 0;
}

bool Allowed(Point ob)
{return !mapn[ob.y][ob.x] && !visit[ob.y][ob.x];}

bool AtWall(Point ob)
{return mapn[ob.y][ob.x];}

short SD(Point ob)//straight dire
{
    if(abs(ob.x-end.x)>=abs(ob.y-end.y))
    {
        if(ob.x<end.x) return 0;
        if(ob.x>end.x) return 2;
    }
    if(ob.y<end.y) return 1;
    return 3;
}

int main()
{
    memset(mapn,1,sizeof mapn);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mapn[i][j];
    start.Scan(),start.step=0,start.WD=start.D=4;
    end.Scan();
    B_star.push(start);
    if(showmap) system("cls");
    while(!B_star.empty())
    {
        Point now=B_star.front();B_star.pop();
        if(now==end) {printf("B-star ans: %d\n",now.step);return 0;}
        if(!Allowed(now)) continue;
        visit[now.y][now.x]=1;
        if(showmap)
        {
            maprint(now);
            system("pause");
            system("cls");
        }
        /*
            0 右
            1 下
            2 左
            3 上 
        */
        if(abs(now.x-end.x)>=abs(now.y-end.y))
        {
            if(now.x<end.x && Allowed(now.Next(0)))//朝右走
            {
                Point rear=now.Next(0);
                rear.step++,rear.WD=rear.D=4;
                B_star.push(rear);
                continue;
            }
            if(now.x>end.x && Allowed(now.Next(2)))//朝左走
            {
                Point rear=now.Next(2);
                rear.step++,rear.WD=rear.D=4;
                B_star.push(rear);
                continue;
            }
        }
        else
        {
            if(now.y<end.y && Allowed(now.Next(1)))//朝下走 
            {
                Point rear=now.Next(1);
                rear.step++,rear.WD=rear.D=4;
                B_star.push(rear);
                continue;
            }
            if(now.y>end.y && Allowed(now.Next(3)))//朝上走 
            {
                Point rear=now.Next(3);
                rear.step++,rear.WD=rear.D=4;
                B_star.push(rear);
                continue;
            }
        }
        /*
            0 右
            1 下
            2 左
            3 上 
        */
        //不能径直走
         if(now.WD==4 && AtWall(now.Next(SD(now))))//第一次撞到墙2
         {
            if(SD(now)==0) //墙在右边
            {
                Point rear;
                rear=now.Next(1),rear.D=1,rear.step++,rear.WD=0,B_star.push(rear);
                rear=now.Next(3),rear.D=3,rear.step++,rear.WD=0,B_star.push(rear);
                continue;
            }
            if(SD(now)==1) //墙在下边
            {
                Point rear;
                rear=now.Next(0),rear.D=0,rear.step++,rear.WD=1,B_star.push(rear);
                rear=now.Next(2),rear.D=2,rear.step++,rear.WD=1,B_star.push(rear);
                continue;
            }
            if(SD(now)==2) //墙在左边
            {
                Point rear;
                rear=now.Next(1),rear.D=1,rear.step++,rear.WD=2,B_star.push(rear);
                rear=now.Next(3),rear.D=3,rear.step++,rear.WD=2,B_star.push(rear);
                continue;
            }
            if(SD(now)==3) //墙在上边
            {
                Point rear;
                rear=now.Next(0),rear.D=0,rear.step++,rear.WD=3,B_star.push(rear);
                rear=now.Next(2),rear.D=2,rear.step++,rear.WD=3,B_star.push(rear);
                continue;
            }
        }
        /*
            0 右
            1 下
            2 左
            3 上 
        */
        else//早就已经撞到墙了
        {
            if(now.WD==0)//墙在右边
            {
                if(!AtWall(now.Next(0)))//右边根本没墙
                {
                    if(now.D==1)//向下走
                    {
                        Point rear;
                        rear=now.Next(0),rear.D=0,rear.step++,rear.WD=3,B_star.push(rear);
                        continue;
                    }
                    if(now.D==3)
                    {
                        Point rear;
                        rear=now.Next(0),rear.D=0,rear.step++,rear.WD=1,B_star.push(rear);
                        continue;
                    }
                }
                //右边有墙，沿着 now.D 继续走
                if(!AtWall(now.Next(now.D)))//能继续走
                {
                    Point rear;
                    rear=now.Next(now.D),rear.D=now.D,rear.step++,rear.WD=0,B_star.push(rear);
                    continue;
                }
                //沿着这个方向不能再走了
                Point rear;
                rear=now.Next(2),rear.D=2,rear.step++,rear.WD=now.D,B_star.push(rear);
                continue;
            }
            if(now.WD==1)//墙在下边
            {
                if(!AtWall(now.Next(1)))//下边根本没墙
                {
                    if(now.D==0)//向右走
                    {
                        Point rear;
                        rear=now.Next(1),rear.D=1,rear.step++,rear.WD=2,B_star.push(rear);
                        continue;
                    }
                    if(now.D==2)//向左走 
                    {
                        Point rear;
                        rear=now.Next(1),rear.D=1,rear.step++,rear.WD=0,B_star.push(rear);
                        continue;
                    }
                }
                //下边有墙，沿着 now.D 继续走
                if(!AtWall(now.Next(now.D)))//能继续走
                {
                    Point rear;
                    rear=now.Next(now.D),rear.D=now.D,rear.step++,rear.WD=1,B_star.push(rear);
                    continue;
                }
                //沿着这个方向不能再走了
                Point rear;
                rear=now.Next(3),rear.D=3,rear.step++,rear.WD=now.D,B_star.push(rear);
                continue;
            }
            /*
                0 右
                1 下
                2 左
                3 上
            */
            if(now.WD==2)//墙在左边
            {
                if(!AtWall(now.Next(2)))//左边根本没墙
                {
                    if(now.D==1)//本来向下走
                    {
                        Point rear;
                        rear=now.Next(2),rear.D=2,rear.step++,rear.WD=3,B_star.push(rear);
                        continue;
                    }
                    if(now.D==3)
                    {
                        Point rear;
                        rear=now.Next(2),rear.D=2,rear.step++,rear.WD=1,B_star.push(rear);
                        continue;
                    }
                }
                //右边有墙，沿着 now.D 继续走
                if(!AtWall(now.Next(now.D)))//能继续走
                {
                    Point rear;
                    rear=now.Next(now.D),rear.D=now.D,rear.step++,rear.WD=2,B_star.push(rear);
                    continue;
                }
                //沿着这个方向不能再走了
                Point rear;
                rear=now.Next(0),rear.D=0,rear.step++,rear.WD=now.D,B_star.push(rear);
                continue;
            }
            if(now.WD==3)//墙在上边
            {
                if(!AtWall(now.Next(3)))//上边根本没墙
                {
                    if(now.D==0)//向右走
                    {
                        Point rear;
                        rear=now.Next(3),rear.D=3,rear.step++,rear.WD=2,B_star.push(rear);
                        continue;
                    }
                    if(now.D==2)//向左走 
                    {
                        Point rear;
                        rear=now.Next(3),rear.D=3,rear.step++,rear.WD=0,B_star.push(rear);
                        continue;
                    }
                }
                //下边有墙，沿着 now.D 继续走
                if(!AtWall(now.Next(now.D)))//能继续走
                {
                    Point rear;
                    rear=now.Next(now.D),rear.D=now.D,rear.step++,rear.WD=3,B_star.push(rear);
                    continue;
                }
                //沿着这个方向不能再走了
                Point rear;
                rear=now.Next(1),rear.D=1,rear.step++,rear.WD=now.D,B_star.push(rear);
                continue;
            }
            /*
                0 右
                1 下
                2 左
                3 上
            */
        }
    }
    printf("No way!\n");
    return 0;
}
/*
5 5
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0
1 3
5 3

17 17
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 7
17 7

7 7
0 0 0 0 0 0 0
0 0 1 1 1 1 0
0 0 1 0 0 1 0
0 0 1 0 0 1 0
0 0 1 0 0 1 0
0 0 1 1 1 1 0
0 0 0 0 0 0 0
1 4
5 4

5 7
0 0 0 0 0 0 0
0 0 1 1 1 1 0
0 0 0 0 0 1 0
0 0 1 1 1 1 0
0 0 0 0 0 0 0
1 3
7 3

7 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 0 1 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
3 7
3 1

6 7
0 0 0 0 0 0 0
0 0 1 1 1 1 0
0 0 0 0 0 1 0
0 0 0 0 0 1 0
0 0 1 1 1 1 0
0 0 0 0 0 0 0
1 3
7 3

6 7
0 0 0 0 0 0 0
0 0 1 1 0 1 1
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 1 1 1 1 1
0 0 0 0 0 0 0
1 3
7 3
*/

3. 拯救算法

[ 根据 B* 传统思路写出来的代码还是很有 bug 的 ]

许多同学看完之后的感觉很有可能是：“这不就是瞎搞吗？贪心策略明显错误，得不到最优解，数据出严一点被卡住了还说不定……这世界上真的会有人用 B* 吗！？”

还真有

此算法经常被用来做游戏中怪物的寻路算法。

大家都知道，计算最短路最重要其实是时间，如果怪物太多，计算机来不及计算，你的电脑就会出现卡顿，最先卡掉的就是你的显示帧数。

等你再回来的时候，很可能就已经

会导致游戏体验感极差，于是高效寻路算法就变成了当务之急。

B* 的效率一般认为是 A* 的几十上百倍，也就是说，计算机用 A* 计算一个怪物的时间代价可能就相当于 B* 计算 400 个怪物的代价。

当 A* 在计算一个怪物时，B* 已经计算了 400 个了！

虽然得不到最优路径，也蛮好了。

况且让怪物看起来傻一点也蛮好的

还有一种动物的行动也是基于 B* 的，那就是著名的

看见它基本就是沿着墙走的，可以算是沿着障碍物，而且据传言，蟑螂进入一个锐角区域后便无法后退，很有可能就要和这个世界说再见了……

蟑螂的这种缺陷似乎也对应了传统 B* 的一个缺陷。

可怜的蟑螂被卡住了

可怜的怪物被遛了

前方没路，回头的路又被标记为了“走过”，根据寻路最优原理，是不能再走了的。

于是屏幕上就出现了 "No way!"，然而很显然是有路的嘛！

1. 解决“锐角”问题

其实并不是十分棘手。问题的终极原因还是因为在“锐角”中朝一个方向走的时候，前面三个方向都被挡住了。

其实完全可以在前方还没有障碍物，但是左右前方有的时候设置“重生点”，相当于多了一个选择。实现的时候就相当于在队列里插入一个新的方向。

代码中，设在 now 位置时要往 ND 方向走了，先判断一下左右前方是否有障碍，如果有，加入向左向右的新分支就行了。

Point rear;
rear=now.Next(ND),rear.Walk(TL(ND));//左前
if(AtWall(rear)) rear=now.Next(TL(ND)),rear.step++,B_star.push(rear);
rear=now.Next(ND),rear.Walk(TR(ND));//右前
if(AtWall(rear)) rear=now.Next(TR(ND)),rear.step++,B_star.push(rear);

TL TR 是新加进来的函数，这样定义。

short TL(short dire)//左转
{return (dire==0 ? 3 : dire-1);}

short TR(short dire)//右转
{return (dire==3 ? 0 : dire+1);}

测试结果：

蟑螂逃出了怪圈

玩家也不能再皮了

同时也解决了其它一些情况的 bug……

2. “展平”优化

假如出现以下情况：

可以发现很明显在凹自行障碍物内就可以抄近道走，但是由于它要贴着墙跑，并没有让它意识到可以走捷径。

所以可以加特判，当它完全可以从身边的格子直接过来的时候，更新步数。

for(short i=0;i<4;i++)
{
    Point rear=now;
    rear.Walk(i);
    if(mem[rear.y][rear.x]!=INT_MAX) now.step=min(now.step,mem[rear.y][rear.x]+1);
}

mem 是记录搜索到每一个格子的最小步数，初始值赋为 INT_MAX （足够大就行）。

鉴于 INT_MAX+1 会爆 int ，所以在周围格子是 INT_MAX 的情况下是万万不能赋过来的，需要特判一下。

下面是 mem 初始化代码：

for(int i=0;i<=n+1;i++)
    for(int j=0;j<=m+1;j++)
        mem[i][j]=INT_MAX;

注意棋盘外一圈也要赋值一下。

每次进入搜索位置的时候也要更新答案一下:

mem[now.y][now.x]=min(mem[now.y][now.x],now.step);

测试结果：

其实本质就是将相邻的回路变成比较直的路径，类似于展平衣服上的褶皱，姑且叫“展平优化”吧。

[ 有同学肯定要问那间隔稍微大一点的回路怎么办，就是相差了一个以上的格子是否要找到并进行优化，这么做会让代码量大幅度上升而且不太好写，目前就考虑相邻格子的优化吧 ]

3. 双向 B*

这个优化就比较鬼畜了，限于篇幅，这里就不展示写法了。

具体方法就是另开一个队列，从 E 点开始搜索，如果过程中碰见了起点队列更新过的 mem，说明起点可以到达这个地方，可以将

now.step + mem[now.y][now.x]-1

作为答案输出。

当然起点队列碰见了终点队列经过的格子也要这么干。

注意必需要有方法区分起点队列与终点队列更新过的 mem 还有 visit，可以另开数组进行标记，或者把每一个格子写成

struct msg
{
    int val;
    bool pass;//谁经过了
};

类似的结构体。

这样可以进一步优化代码效率与解的“优秀程度”，但是空间占用要变成双倍的，写起来也比较烦。

4. 总结

总的来说，B* 还是个有很大修改空间的算法，但是它带来的寻找路径的思路是有借鉴意义的。

也有越来越多的算法开始通过观察大自然而获得启发，这也是人工智能算法的雏形……

我们这次学了：

B* 算法流程

1. 径直方向没有障碍物，径直向 E 走去。

2. 碰到障碍物，以障碍物格子为界，沿着障碍物边缘分别行走形成分支以搜索。

3. 走到终点，输出答案。

几个拯救 B* 的优化

1. 进入狭长区域前设置新搜索分支 以防找不到路径

2. 从相邻格子上更新答案 以使答案更加优化

3. 从起点和终点双向搜索 以提升效率并进一步优化答案

本文章内容到此结束，感谢大家阅读。