a算法:深入A*算法

、前言 　　在这里我将对A*算法实际应用进行定探讨并且举个有关A*算法在最短路径搜索例子值得注意是这里并不对A*基本概念作介绍如果你还对A*算法不清楚话请看姊妹篇初识A*算法

　　这里所举例子是参考AMIT主页中个源使用这个源时应该遵守定公约

2、A*算法编写原理

　　我在初识A*算法中说过A*算法是最好优先算法种只是有些约束条件而已我们先来看看最好优先算法是如何编写吧

　　如图有如下状态空间:(起始位置是A目标位置是P字母后数字表示节点估价值)

\" width=288 border=0>



　　搜索过程中设置两个表:OPEN和CLOSEDOPEN表保存了所有已生成而未考察节点CLOSED表中记录已访问过节点算法中有步是根据估价重排OPEN表这样循环中每步只考虑OPEN表中状态最好节点具体搜索过程如下:

1)状态:　　　　　　　　　　　　　　　　
　 OPEN=[A5]；CLOSED=；
2)估算A5取得搜有子节点并放入OPEN表中；
　 OPEN=[B4C4D6]；CLOSED=[A5]
3)估算B4取得搜有子节点并放入OPEN表中；
　 OPEN=[C4E5F5D6]；CLOSED=[B4A5]
4)估算C4；取得搜有子节点并放入OPEN表中；
　 OPEN=[H3G4E5F5D6]；CLOSED=[C4B4A5]
5)估算H3取得搜有子节点并放入OPEN表中；
　 OPEN=[O2P3G4E5F5D6]；CLOSED=[H3C4B4A5]
6)估算O2取得搜有子节点并放入OPEN表中；
　 OPEN=[P3G4E5F5D6]；CLOSED=[O2H3C4B4A5]
7)估算P3已得到解；

　　看了具体过程再看看伪吧算法伪如下:

Best_First_Search
{
　 Open = [起始节点];
　 Closed = ;
　 while (Open表非空)
　 {
　　 从Open中取得个节点X并从OPEN表中删除
　　 (X是目标节点)
　　 {
　　　 求得路径PATH；
　　　 返回路径PATH；
　　 }
　　 for (每个X子节点Y)
　　 {
　　　 (Y不在OPEN表和CLOSE表中)
　　　 {
　　　　 求Y估价值；
　　　　 并将Y插入OPEN表中；
　　　 }
　　　 //还没有排序
　　　 (Y在OPEN表中)
　　　 {
　　　　 (Y估价值小于OPEN表估价值)
　　　　　 更新OPEN表中估价值；
　　　 }
　　　 //Y在CLOSE表中
　　　 {
　　　　 (Y估价值小于CLOSE表估价值)
　　　　 {
　　　　　 更新CLOSE表中估价值；
　　　　　 从CLOSE表中移出节点并放入OPEN表中；
　　　　 }
　　　 }
　　　 将X节点插入CLOSE表中；
　　　 按照估价值将OPEN表中节点排序；
　　 }//end for
　 }//end while
}//end func

　　啊！伪出来了写个源应该不是问题了依葫芦画瓢就可以A*算法和此是样只要注意估价中g(n)h(n)约束条件就可以了不清楚可以看看初识A*算法好了我们可以进入另个重要话题用A*算法实现最短路径搜索在此的前你最好认真理解前面算法不清楚可以找我我Email在文章尾

3、用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生成 8个子节点2- 9 有 8个方向如图:

\" width=453 border=0>



　　仔细看看节点1、9、17g(n)和h(n)是如何计算现在应该知道了下面中f(n)是如何计算吧开始讲解源了其实这个是个很典型教科书似也就是说只要你看懂了上面伪这个是十分容易理解不过他和上面伪有些区别我在后面会提出来

　　先看搜索主:

void AstarPathfinder::FindPath( sx, sy, dx, dy){ NODE *Node, *BestNode; TileNumDest; //得到目标位置作判断用 TileNumDest = TileNum(sx, sy); //生成Open和Closed表 OPEN = ( NODE* )calloc(1,( NODE )); CLOSED=( NODE* )calloc(1,( NODE )); //生成起始节点并放入Open表中 Node=( NODE* )calloc(1,( NODE )); Node->g = 0; //这是计算h值 // should really use sqrt. Node->h = (dx-sx)*(dx-sx) + (dy-sy)*(dy-sy); //这是计算f值即估价值 Node->f = Node->g+Node->h; Node->NodeNum = TileNum(dx, dy); Node->x = dx; Node->y = dy; // make Open List po to first node OPEN->NextNode=Node; for (;;) { //从Open表中取得个估价值最好节点 BestNode=ReturnBestNode; //如果该节点是目标节点就退出 // we\'ve found the end, and finish ; (BestNode->NodeNum TileNumDest) //否则生成子节点 GenerateSuccessors(BestNode,sx,sy); } PATH = BestNode;}



　　再看看生成子节点:

void AstarPathfinder::GenerateSuccessors(NODE *BestNode, dx, 　dy){ x, y; //哦！依次生成 8个方向子节点简单！ // Upper-Left ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Upper ( FreeTile(x=BestNode->x, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Upper-Right ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y-TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Right ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y) ) GenerateSucc(BestNode,x,y,dx,dy); // Lower-Right ( FreeTile(x=BestNode->x+TILESIZE, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Lower ( FreeTile(x=BestNode->x, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Lower-Left ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y+TILESIZE) ) GenerateSucc(BestNode,x,y,dx,dy); // Left ( FreeTile(x=BestNode->x-TILESIZE, y=BestNode->y) ) GenerateSucc(BestNode,x,y,dx,dy);}

　　看看最重要:

void AstarPathfinder::GenerateSucc(NODE *BestNode, x, y, dx, dy){ g, TileNumS, c = 0; NODE *Old, *Successor; //计算子节点 g 值 // g(Successor)=g(BestNode)+cost of getting from BestNode to Successor g = BestNode->g+1; // identication purposes TileNumS = TileNum(x,y); //子节点再Open表中吗？ // equal to NULL then not in OPEN list, it s the Node in Old ( (Old=CheckOPEN(TileNumS)) != NULL ) { //若在 for( c = 0; c < 8; c) // Add Old to the list of BestNode\'s Children (or Successors). ( BestNode->Child[c] NULL ) ; BestNode->Child[c] = Old; //比较Open表中估价值和当前估价值(只要比较g值就可以了) // our g value is < Old\'s then re Old\'s parent to po to BestNode ( g < Old->g ) { //当前估价值小就更新Open表中估价值 Old->Parent = BestNode; Old->g = g; Old->f = g + Old->h; } } //在Closed表中吗？ // equal to NULL then not in OPEN list, it s the Node in Old ( (Old=CheckCLOSED(TileNumS)) != NULL ) { //若在 for( c = 0; c< 8; c) // Add Old to the list of BestNode\'s Children (or Successors). ( BestNode->Child[c] NULL ) ; BestNode->Child[c] = Old; //比较Closed表中估价值和当前估价值(只要比较g值就可以了) // our g value is < Old\'s then re Old\'s parent to po to BestNode ( g < Old->g ) { //当前估价值小就更新Closed表中估价值 Old->Parent = BestNode; Old->g = g; Old->f = g + Old->h; //再依次更新Old所有子节点估价值 // Since we changed the g value of Old, we need // to propagate this value downwards, i.e. // do a Depth-First traversal of the tree! PropagateDown(Old); } } //不在Open表中也不在Close表中 { //生成新节点 Successor = ( NODE* )calloc(1,( NODE )); Successor->Parent = BestNode; Successor->g = g; // should do sqrt, but since we don\'t really Successor->h = (x-dx)*(x-dx) + (y-dy)*(y-dy); // care about the distance but just which branch looks Successor->f = g+Successor->h; // better this should suffice. Anyayz it\'s faster. Successor->x = x; Successor->y = y; Successor->NodeNum = TileNumS; //再插入Open表中同时排序 // Insert Successor _disibledevent=>

　　哈哈！A*算法我懂了！当然我希望你有这样感觉！不过我还要再说几句仔细看看这个你会发现这个和我前面说伪有些区别在GenerateSucc中当子节点在Closed表中时没有将子节点从Closed表中删除并放入Open表中而是直接重新计算该节点所有子节点估价值(用PropagateDown)这样可以快些！另当子节点在Open表和Closed表中时重新计算估价值后没有重新对Open表中节点排序我有些想不通为什么不排呢？:-(会不会是个小小BUG你知道告诉我好吗？

　　好了！主要内容都讲完了还是完整仔细看看源吧！希望我所对你有点帮助点点也可以如果你对文章中观点有异议或有更好解释都告诉我我email在文章最后！
　

延伸阅读

• 2010-11-24-- 加密算法,谈谈数据加密的处理--提供各种算法处理
• 2010-12-2-- 负面的惩罚,Google 修改算法以惩罚那些拥有更多负面评论的商户排名
• 2009-9-12-- dllloadex汉化版:Dll  Show  4.7  汉化版注册算法
• 2011-8-1-- paxos,Paxos算法
• 2009-9-12-- dllloadex汉化版:Dll  Show  4.7  汉化版注册算法
• 2008-12-14-- 点灯游戏:点灯游戏算法实现代码
• 2009-9-12-- 加密算法:破解微软脚本加密算法
• 2008-12-14-- a算法:初识A*算法
• 2009-9-12-- 算法导论:和同学破解了一个邹老大的短信分拆算法！！！！！！！！！！
• 2009-2-12-- 加密算法:算法回顾之插入排序