发信人: mrcloud()
整理人: skyice(2000-04-04 13:31:06), 站内信件
|
你回来啦，这些天好无聊啊。几个版主都不在.
我把两篇A*算法的文章放在这里,关于拼板我看绝对是用它了。
现在的位置是： 算法结构 | 游戏制作> 初识A*算法
资料整理·中国程序员网站
初识A*算法
写这篇文章的初衷是应一个网友的要求，当然我也发现现在有关人工智能的中文
站点实在太少，我在这里 抛砖引玉，希望大家都来热心的参与。
还是说正题，我先拿A*算法开刀，是因为A*在游戏中有它很典型的用法，是人工
智能在游戏中的代表。
A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，我看还
是先说说何谓启发式算法。
一、何谓启发式搜索算法：
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问
题求解过程表现为从 初始状态到目标状态寻找这个路径的过程。通俗点说，就是
在解一个问题时，找到一条解题的过程可以从 求解的开始到问题的结果（好象并
不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求 解条件的
不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这
个图就是状态空 间。问题的求解实际上就是在这个图中找到一条路径可以从开始
到结果。这个寻找的过程就是状态空间搜 索。
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向
下找，直到找到目标 为止。深度优先是按照一定的顺序前查找完一个分支，再查
找另一个分支，以至找到目标为止。这两种算 法在数据结构书中都有描述，可以
参看这些书得到更详细的解释。
前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态
空间中穷举。这在状 态空间不大的情况下是很合适的算法，可是当状态空间十分
大，且不预测的情况下就不可取了。他的效率 实在太低，甚至不可完成。在这里
就要用到启发式搜索了。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的
位置，再从这个位置 进行搜索直到目标。这样可以省略大量无畏的搜索路径，提
到了效率。在启发式搜索中，对位置的估价是 十分重要的。采用了不同的估价可
以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f(n) = g(n) + h(n)
其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代
价，h(n)是从n到目 标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索
的启发信息，因为g(n)是已知的。如果说详细 点，g(n)代表了搜索的广度的优先
趋势。但是当h(n) >> g(n)时，可以省略g(n),而提高效率。这些就深了， 不懂
也不影响啦！我们继续看看何谓A*算法。
二、初识A*算法：
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。
当然A*也是。这些算法 都使用了启发函数，但在具体的选取最佳搜索节点时的策
略不同。象局部择优搜索法，就是在搜索的过程中 选取“最佳节点”后舍弃其他
的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍 弃
了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶
段的最佳并不一定是全局 的最佳。最好优先就聪明多了，他在搜索时，便没有舍
弃节点（除非该节点是死节点），在每一步的估价中 都把当前的节点和以前的节
点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的
丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算
法。只不过要加上一些约束 条件罢了。由于在一些问题求解时，我们希望能够求
解出状态空间搜索的最短路径，也就是用最快的方法求 解问题，A*就是干这种事
情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可
采 纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数克表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的
最断路经的启发值。由 于这个f'(n)其实是无法预先知道的，所以我们用前面的
估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n) 才可（大多数情况下都
是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别
的重 要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳
的。我们说应用这种估价函数的 最好优先算法就是A*算法。哈！你懂了吗？肯定
没懂！接着看！
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数
，h(n)=0，这种h(n)肯 定小于h'(n)，所以由前述可知广度优先算法是一种可采
纳的。实际也是。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就
是在估计一个节点的值 时的约束条件，如果信息越多或约束条件越多则排除的节
点就越多，估价函数越好或说这个算法越好。这就 是为什么广度优先算法的那么
臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实 时
性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适
当的减小h(n)的信息，即 减小约束条件。但算法的准确性就差了，这里就有一个
平衡的问题。可难了，这就看你的了！
好了我的话也说得差不多了，我想你肯定是一头的雾水了，其实这是写给懂A*算
法的同志看的。哈哈！ 你还是找一本人工智能的书仔细看看吧！我这几百字是不
足以将A*算法讲清楚的。只是起到抛砖引玉的作用 希望大家热情参与吗！
预知A*算法的应用，请看《深入A*算法》。
现在的位置是： 算法结构 | 游戏制作 > 深入A*算法
资料整理·中国程序员网站
深入A*算法----浅析A*算法在搜索最短路径中的应用
一、前言
在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*算法在最短
路径搜索 的例子。值得注意的是这里并不对A*的基本的
概念作介绍，如果你还对A*算法不清楚的话， 请看姊妹篇《初识A*算法》。
这里所举的例子是参考AMIT主页中的一个源程序，你可以在AMIT的站点上下载也
可以在我 的站点上下载。你使用这个源程序时，应该遵
守一定的公约。
二、A*算法的程序编写原理
我在《初识A*算法》中说过，A*算法是最好优先算法的一种。只是有一些约束条
件而已。 我们先来看看最好优先算法是如何编写的吧。
如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点
的估价值）
搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节
点，CLOSED 表中记录已访问过的节点。算法中有一步是
根据估价函数重排OPEN表。这样循环中的每一 步只考虑OPEN表中状态最好的节点
。具体搜索过程如下：
1）初始状态：
OPEN=[A5]；CLOSED=[]；
2）估算A5，取得搜有子节点，并放入OPEN表中；
OPEN=[B4，C4，D6]；CLOSED=[A5]
3）估算B4，取得搜有子节点，并放入OPEN表中；
OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
4）估算C4；取得搜有子节点，并放入OPEN表中；
OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
5）估算H3，取得搜有子节点，并放入OPEN表中；
OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=H3C4，B4，A5]
6）估算O2，取得搜有子节点，并放入OPEN表中；
OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]
7）估算P3，已得到解；
看了具体的过程，再看看伪程序吧。算法的伪程序如下：
Best_First_Search()
{
Open = [起始节点]; Closed = [];
while ( Open表非空 )
{
从Open中取得一个节点X，并从OPEN表中删除。
if (X是目标节点)
{
求得路径PATH；返回路径PATH；
}
for (每一个X的子节点Y)
{
if( Y不在OPEN表和CLOSE表中 )
{
求Y的估价值；并将Y插入OPEN表中；//还没有排序
}
else
if( Y在OPEN表中 )
{
if( Y的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值；
}
else //Y在CLOSE表中
{
if( Y的估价值小于CLOSE表的估价值 )
{
更新CLOSE表中的估价值；
从CLOSE表中移出节点，并放入OPEN表中；
}
}
将X节点插入CLOSE表中；
按照估价值将OPEN表中的节点排序；
}//end for
}//end while
}//end func
啊！伪程序出来了，写一个源程序应该不是问题了，依葫芦画瓢就可以。A*算法
的程序与此 是一样的，只要注意估价函数中的g(n)的h(n)约束条件就可以了。不
清楚的可以看看《初识A*算法》。好了，我们可以进入另一个重要的话题，用A*
算法实现最短路径的搜索。在此之 前你最好认真的理解前面的算法。不清楚可以
找我。我的Email在文章尾。
三、用A*算法实现最短路径的搜索
在游戏设计中，经常要涉及到最短路径的搜索，现在一个比较好的方法就是用A*
算法进行设 计。他的好处我们就不用管了，反正就是好！^_*
注意下面所说的都是以 ClassAstar 这个程序为蓝本，你可以在这里下载这个程
序。这个程 序是一个完整的工程。里面带了一个EXE文件。可以先看看。
先复习一下，A*算法的核心是估价函数f(n)，它包括g(n)和h(n)两部分。g(n) 是
已经走过的 代价，h(n)是n到目标的估计代价。在这个例子中g(n)表示在状态空
间从起始节点到 n节点的 深度，h(n)表示n节点所在地图的位置到目标位置的直
线距离。啊！一个是状态空间，一个是 实际的地图，不要搞错了。再详细点说，
有一个物体A，在地图上的坐标是(xa,ya)，A所要到 达的目标b的坐标是(xb,yb)
。则开始搜索时，设置一个起始节点1，生成八个子节点2 - 9 因 为有八个方向
。如图：
仔细看看节点1、9、17的g(n)和h(n)是怎么计算的。现在应该知道了下面程序中
的f(n)是如何 计算的吧。开始讲解源程序了。其实这个程序是一个很典型的教科
书似的程序，也就是说只要 你看懂了上面的伪程序，这个程序是十分容易理解的
。不过他和上面的伪程序有一些的不同， 我在后面会提出来。
先看搜索主函数：
void AstarPathfinder::FindPath(int sx, int sy, int dx, int dy)
{
NODE *Node, *BestNode;
int TileNumDest;
//得到目标位置，作判断用
TileNumDest = TileNum(sx, sy);
//生成Open和Closed表
OPEN=( NODE* )calloc(1,sizeof( NODE ));
CLOSED=( NODE* )calloc(1,sizeof( NODE ));
//生成起始节点，并放入Open表中
Node=( NODE* )calloc(1,sizeof( NODE ));
Node->g = 0;
//这是计算h值
Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); // should really use
sqrt().
//这是计算f值，即估价值
Node->f = Node->g+Node->h;
Node->NodeNum = TileNum(dx, dy);
Node->x = dx;
Node->y = dy;
OPEN->NextNode=Node; // make Open List point to first node
for (;;)
{ //从Open表中取得一个估价值最好的节点
BestNode=ReturnBestNode();
//如果该节点是目标节点就退出
if (BestNode->NodeNum == TileNumDest) // if we've found the end,
break and finish
break;
//否则生成子节点
GenerateSuccessors(BestNode,sx,sy);
}
PATH = BestNode;
}
再看看生成子节点函数 GenerateSuccessors：
void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int
dy)
{
int x, y;
//哦！依次生成八个方向的子节点，简单！
// Upper-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper
if ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Upper-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Right
if ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower
if ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Lower-Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) )
GenerateSucc(BestNode,x,y,dx,dy);
// Left
if ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) )
GenerateSucc(BestNode,x,y,dx,dy);
}
看看最重要的函数GenerateSucc：
void AstarPathfinder::GenerateSucc(NODE *BestNode,int x, int y, int d
x, int dy)
{
int g, TileNumS, c = 0;
NODE *Old, *Successor;
//计算子节点的 g 值
g = BestNode->g+1; // g(Successor)=g(BestNode)+cost of getting
from BestNode to Successor
TileNumS = TileNum(x,y); // identification purposes
//子节点再Open表中吗？
if ( (Old=CheckOPEN(TileNumS)) != NULL ) // if equal to NULL then
not in OPEN list, else it returns the Node in Old
{
//若在
for( c = 0; c <8; c++) if( BestNode->Child[c] == NULL ) // Add Old t
o the list of BestNode's Children (or Successors).
break;
BestNode->Child[c] = Old;
//比较Open表中的估价值和当前的估价值（只要比较g值就可以了）
if ( g g ) // if our new g value is Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
}
}
else //在Closed表中吗？
if ( (Old=CheckCLOSED(TileNumS)) != NULL ) // if equal to NULL the
n not in OPEN list, else it returns the Node in Old
{
//若在
for( c = 0; c<8; c++) if ( BestNode->Child[c] == NULL ) // Ad
d Old to the list of BestNode's Children (or Successors).
break;
BestNode->Child[c] = Old;
//比较Closed表中的估价值和当前的估价值（只要比较g值就可以了）
if ( g g ) // if our new g value is Parent = BestNode;
Old->g = g;
Old->f = g + Old->h;
//再依次更新Old的所有子节点的估价值
PropagateDown(Old); // Since we changed the g value of Old,
we need
// to propagate this new value downwards, i.e.
// do a Depth-First traversal of the tree!
}
}
else//不在Open表中也不在Close表中
{
//生成新的节点
Successor = ( NODE* )calloc(1,sizeof( NODE ));
Successor->Parent = BestNode;
Successor->g = g;
Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // should do sqrt(),
but since we don't really
Successor->f = g+Successor->h; // care about the distance but ju
st which branch looks
Successor->x = x; // better this should suffice. Any
ayz it's faster.
Successor->y = y;
Successor->NodeNum = TileNumS;
//再插入Open表中，同时排序。
Insert(Successor); // Insert Successor on OPEN list wrt f
for( c =0; c <8; c++) if ( BestNode->Child[c] == NULL ) // Add Old t
o the list of BestNode's Children (or Successors).
break;
BestNode->Child[c] = Successor;
}
}
哈哈！A*算法我懂了！当然，我希望你有这样的感觉！不过我还要再说几句。仔
细看看这个程 序，你会发现，这个程序和我前面说的伪程序有一些不同，在Gen
erateSucc函数中，当子节点 在Closed表中时，没有将子节点从Closed表中删除
并放入Open表中。而是直接的重新的计算该 节点的所有子节点的估价值（用Pro
pagateDown函数）。这样可以快一些！另当子节点在 Open 表和Closed表中时，
重新的计算估价值后，没有重新的对Open表中的节点排序，我有些想不通， 为什
么不排呢？:-(，会不会是一个小小的BUG。你知道告诉我好吗？
好了！主要的内容都讲完了，还是完整仔细的看看源程序吧！希望我所的对你有
一点帮助，一 点点也可以。如果你对文章中的观点有异议或有更好的解释都告诉
我。我的email在文章最后！
最后说声“谢谢！再见！”
--
...我的征途是星辰大海...
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.101.63.121]
|
|