📄 新建 文本文档 (2).txt
字号:
A**寻路算法简介
阅读本文以前，可能大家已经接触过A*算法，如果没有，那也没关系。想了解A*算法的更多内容，可以去http://articles.gameres.com/搜索A*，那里有足够的文章让您理解A*算法的基本思路。
一、A**算法的基本思想
参考A*算法的文章《A* Pathfinding for Beginners》，我同样使用这个例题作为开头：
0 1 2 3 4 5 6
0
图1.1
1
2
3
4
如图，绿色是起点，红色是终点，蓝色是障碍物，这样的地图可以在内存中表示成一个二维数组：
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
x1=1 y1=2
x2=5 y2=2
暂时限定不允许出界。允许横走、直走和斜走，求最短的到达目标的路径。A**算法的基本思路就是：首先求出每一点到达终点的最短路径的长度（下面简称值），然后本着总是往值更少的位置走的原则，则走过的一定是最短路径。
首先，我们设置Value数组，用于记录每点的值。在未计算之前，全部标志为-1，就得到如下的数组：
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
毫无疑问，终点离终点的距离是0，所以(5,2)的值可以置为0。因此值数组内容变成这样：
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
这样，又由于它周围的点距离终点的距离不会超过它离终点距离+1，因此值数组变成这样：
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 1 1 1
-1 -1 -1 -1 1 0 1
-1 -1 -1 -1 1 1 1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 2 2 2 2
-1 -1 -1 -1 1 1 1
-1 -1 -1 -1 1 0 1
-1 -1 -1 -1 1 1 1
-1 -1 -1 2 2 2 2
要注意到，(3,1)、(3,2)、(3,3)三个点，虽然在点(4,2)周围，但是由于这三个点不可到达，所以搜索时不应改变他们的值。
-1 -1 3 2 2 2 2
-1 -1 3 -1 1 1 1
-1 -1 -1 -1 1 0 1
-1 -1 3 -1 1 1 1
-1 -1 3 2 2 2 2
-1 4 3 2 2 2 2
-1 4 3 -1 1 1 1
-1 4 4 -1 1 0 1
-1 4 3 -1 1 1 1
-1 4 3 2 2 2 2
5 4 3 2 2 2 2
5 4 3 -1 1 1 1
5 4 4 -1 1 0 1
5 4 3 -1 1 1 1
5 4 3 2 2 2 2
这样，我们得到起点(1,2)到达目标需要4步，又由于(1,2)-(2,1)-(3,0)-(4,1)-(5,2)是一条值递减的路径，因此它也是从(1,2)点到达(5,2)点的最短路径。
换句话说，由于(1,2)点的值为4，(2,1)点的值为3，因此(1,2)点走到终点比(2,1)多需要一步，所以(1,2)点走向(2,1)点一定是更接近而不是更远离终点，这样走完全可以成为最短路径的一步。接下来每一步都保证值递减，也就是说经过了4步之后，到达的地点值一定为0，而地图上唯一值为0的位置就是终点，即4步后到达终点。
以上算法仍然属于广度优先算法，但它和经典广度优先算法的区别在于，经典广度优先算法运用结点的方式记录每个点的坐标，和走到这个点的父结点的坐标，而这个算法仅仅记录每点到终点的距离。当找到目标时，经典广度优先寻找终点结点的祖先结点并依次记录下来，而以上算法则不断在当前点周围寻找比当前点更接近终点的点，并且移动到该点。
：）当然，到目前为止，还没有看出我所谓A**算法有任何优势，但我可以用这样一种非广度优先方法来实现程序：
反复按顺序搜索整个数组，如果发现有已求值的点，它周围有未求值或者已知值但不如经过当前点的路线，则用新值覆盖下该点。知道找不到这样的点为止代码如下：
#define p(a,x,y) *(a+(x)+(y)*Width) //为了更直观
int Width,Height,Size; //宽、高、总大小
char *MAP; //储存地图信息的数组
int *Value; //储存搜索信息的数组
int x1,y1,x2,y2;
void WORK_TDZL1()
{
int i,j,
b; //用于标记
for (i=0;i<Size;i++)
*(Value+i)=-1; //搜索前把所有位置标志为-1
p(Value,x2,y2)=0; //把终点标记为0
b=1;
while (b)
{
b=0;
for (i=0;i<Width;i++)
for (j=0;j<Height;j++)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<8;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x--;break;
case 2:y++;break;
case 3:y--;break;
case 4:x++;y++;break;
case 5:x++;y--;break;
case 6:x--;y++;break;
case 7:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
}
if (p(Value,x1,y1)>-1) //输出结果
{
int x,y,k;
printf("Total %d step\n",p(Value,x1,y1));
i=x1;j=y1;
while ((i!=x2)||(j!=y2))
{
for (k=0;k<8;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x--;break;
case 2:y++;break;
case 3:y--;break;
case 4:x++;y++;break;
case 5:x++;y--;break;
case 6:x--;y++;break;
case 7:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if (p(Value,x,y)==p(Value,i,j)-1)
{
i=x;j=y;break;
}
}
//每次在这里取i和j的值
}
return;
}
printf("No answer!\n");
}
这段程序的意思是：首先，我们知道终点到终点的距离为0，然后不断扫描整幅地图，如果发现某点A的值已知，而它周围的某点B值未知且非障碍物，或者它B的值大于A的值+1，则将B的值设为A的值+1。因为A点可达，且B点非障碍物，因此B点一定可达并且值不会大于A点的值+1，因为由A点到B点为一可行策略。
然而，运行如上程序时我们会发现，它对付从左上到右下的路径非常在行，但是对于含由U型路径或回型路径甚至仅仅是从右下到左上的路径，它会变得非常缓慢。于是将程序优化如下：
void WORK_TDZL3()
{
int i,j,
b; //用于标记
for (i=0;i<Size;i++)
*(Value+i)=-1;
p(Value,x2,y2)=0;
b=1;
while (b)
{
b=0;
for (i=0;i<Width;i++)
for (j=0;j<Height;j++)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:y++;break;
case 1:x++;y++;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
for (i=0;i<Width;i++)
for (j=Height-1;j>=0;j--)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x++;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
for (i=Width-1;i>=0;i--)
for (j=0;j<Height;j++)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:x--;break;
case 1:x--;y++;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
for (i=Width-1;i>=0;i--)
for (j=Height-1;j>=0;j--)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:y--;break;
case 1:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
}
if (p(Value,x1,y1)>-1)
{
//输出结果
int x,y,k;
printf("Total %d step\n",p(Value,x1,y1));
i=x1;j=y1;
while ((i!=x2)||(j!=y2))
{
for (k=0;k<8;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x--;break;
case 2:y++;break;
case 3:y--;break;
case 4:x++;y++;break;
case 5:x++;y--;break;
case 6:x--;y++;break;
case 7:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if (p(Value,x,y)==p(Value,i,j)-1)
{
i=x;j=y;break;
}
}
//每次在这里取i和j的值
}
return;
}
printf("No answer!\n");
}
：）由于时间关系在此不再详述，测试程序、代码及测试数据将在近期上传，比A*算法究竟好上几百倍大家自己体会吧，这可是即时对战游戏设计者梦寐以求的算法哦。本算法的特点是不怕地图大，不怕回形路，另外，本算法还有一个最大好处，就是对目标的一次计算，地图上所有点到达目标的路径都可以很方便的求出。当然具体运用时还得修改不少地方，但相信我的这篇文章你对你有所帮助。
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -