|
1. 前言 我相信绝大多数人是被名字吸引进来的大多数人内心感受：什么？！居然除了 A* 之外还有一个叫 B* 的算法！？ 是的你没看错，本算法就叫 B* ，比 A* 更为快速的寻路算法，一般来说前者耗时通常比后者少十来倍，效率极高，因此通常被选作游戏中怪物寻路的算法。 但是要注意了！（重要内容）B* 是个启发式算法，而且没有很便捷的方法对其进行适当调整，而得到最优解（A* 可以改变其评估函数来保证最优解），所以千万别在 OI 竞赛中使用，否则会死得非常难看。 至于为什么，接下来的内容会详细讲解，我们马上进入正题吧。 [ A* 内容请见 去年五月 #166 [Thomasguo666] A* 算法浅谈 ] 2. 算法介绍首先提一下本文章所谓的寻路问题：有 01 网格 (格子上只有数字 0 或 1) 寻找从网格 (S.x,S.y) 处走到 (E.x,E.y) 的较短路 每次只能走上下左右四个格子 不能到达数字为 1 的格子，不能走出网格
[ S 为起点，E 为终点，后面的文章就都这么称呼喽 ]
同学们很容易想到用 A* 瞬间通过，然而值得注意一点，题目要求的为较短路。 也就是说，我们不关心是否是最短路，只要是“较短路”就行了。使用 A* 虽然能得到最短路，但是算法效率与所找路径的“优秀程度”还得加以权衡。 B* 就是这么一个算法，它效率极高，而且可以给出一个“还算不错”的路径。 B* ( Branch Star 分支寻路算法)发明此算法的计算机学家是受到了自然界动物寻路的启发的。 B* 的大部分行动决策都是依据一个看上去就很不靠谱的“贪心”策略（不知道计算机界“贪心”含义的同学可以忽略这个词）： 朝着目标的位置径直走去就行了不用考虑任何障碍物因素，直接走过去就行了，撞到障碍物了再说。 但由于这个寻路问题的“径直走”和真实生活的“径直走”有所不同（因为不能斜着走），可以有许多定义。 下面给出几个例子：当 |S.x-E.x|>=|S.y-E.y| 时横着朝 E 走，反之则竖着朝 E 走。 当 S.x - E.x ≠ 0 时横着朝 E 走，反之则竖着朝 E 走。 用 Breshenham 算法，不在本次讨论范围以内。 函数解析式法，推导比较复杂。
为了代码实现方便，本文使用第一类定义做演示。  [ 如此行走……'#'为障碍物，'.'为空格子，'1'为经过的格子 ]
碰到障碍物了怎么办！？那就以障碍物格子（1 格子）为界，沿着障碍物边缘分别行走形成分支。  走着走着发现绕过障碍物了，就继续之前的“贪心策略”继续走。  直到走到终点即可。 总结一下流程没有遇到障碍物，“径直”向 E 走去。 碰到障碍物，以障碍物格子为界，沿着障碍物边缘分别行走形成分支以搜索。 走到终点，输出答案。
然后给出 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* 算法流程径直方向没有障碍物，径直向 E 走去。 碰到障碍物，以障碍物格子为界，沿着障碍物边缘分别行走形成分支以搜索。 走到终点，输出答案。
几个拯救 B* 的优化进入狭长区域前设置新搜索分支 以防找不到路径 从相邻格子上更新答案 以使答案更加优化 从起点和终点双向搜索 以提升效率并进一步优化答案
本文章内容到此结束，感谢大家阅读。
|
