另类寻路算法——B*算法浅谈

# 1. 前言 ### 我相信绝大多数人是被名字吸引进来的 大多数人内心感受：什么？！居然除了 A\* 之外还有一个叫 B\* 的算法！？ 是的你没看错，本算法就叫 B\* ，比 A\* 更为快速的寻路算法，一般来说前者耗时通常比后者少十来倍，效率极高，因此通常被选作游戏中怪物寻路的算法。 ### 但是要注意了！（重要内容） B\* 是个启发式算法，而且没有很便捷的方法对其进行适当调整，而得到最优解（A\* 可以改变其评估函数来保证最优解），所以千万别在 OI 竞赛中使用，否则会死得非常难看。 至于为什么，接下来的内容会详细讲解，我们马上进入正题吧。 \[ A\* 内容请见 去年五月 [#166 \[Thomasguo666 \] A\* 算法浅谈](https://www.luogu.org/blog/juruoforever/qian-tan-astar) \] # 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++ $ 语言对此算法的实现： ```cpp #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 方向走了，先判断一下左右前方是否有障碍，如果有，加入向左向右的新分支就行了。 ```cpp 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 是新加进来的函数，这样定义。 ```cpp short TL(short dire)//左转 {return (dire==0 ? 3 : dire-1);} short TR(short dire)//右转 {return (dire==3 ? 0 : dire+1);} ``` 测试结果：  ~~蟑螂逃出了怪圈~~ ~~玩家也不能再皮了~~ 同时也解决了其它一些情况的 bug…… ## 2. “展平”优化 假如出现以下情况：  可以发现很明显在凹自行障碍物内就可以抄近道走，但是由于它要贴着墙跑，并没有让它意识到可以走捷径。 所以可以加特判，当它完全可以从身边的格子直接过来的时候，更新步数。 ```cpp 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 初始化代码： ```cpp for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++) mem[i][j]=INT_MAX; ``` 注意棋盘外一圈也要赋值一下。 每次进入搜索位置的时候也要更新答案一下: ```cpp 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，可以另开数组进行标记，或者把每一个格子写成 ```cpp struct msg { int val; bool pass;//谁经过了 }; ``` 类似的结构体。 这样可以进一步优化代码效率与解的“优秀程度”，但是空间占用要变成双倍的，写起来也比较烦。 ------------ ## 4. 总结 总的来说，B\* 还是个有很大修改空间的算法，但是它带来的寻找路径的思路是有借鉴意义的。 也有越来越多的算法开始通过观察大自然而获得启发，这也是人工智能算法的雏形…… ### 我们这次学了： ### B\* 算法流程 1. 径直方向没有障碍物，径直向 E 走去。 2. 碰到障碍物，以障碍物格子为界，沿着障碍物边缘分别行走形成分支以搜索。 3. 走到终点，输出答案。 ### 几个拯救 B\* 的优化 1. 进入狭长区域前设置新搜索分支 以防找不到路径 2. 从相邻格子上更新答案 以使答案更加优化 3. 从起点和终点双向搜索 以提升效率并进一步优化答案 本文章内容到此结束，感谢大家阅读。