a-star-算法剖析

深入A*算法-浅析A*算法在搜索最短路径中的应用Sunway目录1A*算法的程序编写原理2用A*算法实现最短路径的搜索在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*算法在最短路径搜索的例子。值得注意的是这里并不对A*的基本的概念作介绍，如果你还对A*算法不清楚的话，请看姊妹篇《初识A*算法》。这里所举的例子是参考AMIT主页中的一个源程序，你可以在AMIT的站点上下载也可以在我的站点上下载。你使用这个源程序时，应该遵守一定的公约。1、A*算法的程序编写原理我在《初识A*算法》中说过，A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）。如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）图1状态空间图搜索过程中设置两个表：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表中;//还没有排序}elseif(Y在OPEN表中){if(Y的估价值小于OPEN表的估价值)更新OPEN表中的估价值;}else//Y在CLOSE表中{if(Y的估价值小于CLOSE表的估价值){更新CLOSE表中的估价值;从CLOSE表中移出节点,并放入OPEN表中;}}将X节点插入CLOSE表中;按照估价值将OPEN表中的节点排序;}//endfor}//endwhile}//endfunc啊！伪程序出来了，写一个源程序应该不是问题了，依葫芦画瓢就可以。A*算法的程序与此是一样的，只要注意估价函数中的g(n)的h(n)约束条件就可以了。不清楚的可以看看《初识A*算法》。好了，我们可以进入另一个重要的话题，用A*算法实现最短路径的搜索。在此之前你最好认真的理解前面的算法。不清楚可以找我。2、用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因为有八个方向。如图：图2节点图先看搜索主函数：voidAstarPathfinder::FindPath(intsx,intsy,intdx,intdy){NODE*Node,*BestNode;intTileNumDest;//得到目标位置，作判断用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);//shouldreallyusesqrt().//这是计算f值，即估价值Node-f=Node-g+Node-h;Node-NodeNum=TileNum(dx,dy);Node-x=dx;Node-y=dy;OPEN-NextNode=Node;//makeOpenListpointtofirstnodefor(;;){//从Open表中取得一个估价值最好的节点BestNode=ReturnBestNode();//如果该节点是目标节点就退出if(BestNode-NodeNum==TileNumDest)//ifwe'vefoundtheend,breakandfinishbreak;//否则生成子节点GenerateSuccessors(BestNode,sx,sy);}PATH=BestNode;}再看看生成子节点函数GenerateSuccessors：voidAstarPathfinder::GenerateSuccessors(NODE*BestNode,intdx,intdy){intx,y;//依次生成八个方向的子节点，简单！//Upper-Leftif(FreeTile(x=BestNode-x-TILESIZE,y=BestNode-y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Upperif(FreeTile(x=BestNode-x,y=BestNode-y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Upper-Rightif(FreeTile(x=BestNode-x+TILESIZE,y=BestNode-y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Rightif(FreeTile(x=BestNode-x+TILESIZE,y=BestNode-y))GenerateSucc(BestNode,x,y,dx,dy);//Lower-Rightif(FreeTile(x=BestNode-x+TILESIZE,y=BestNode-y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Lowerif(FreeTile(x=BestNode-x,y=BestNode-y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Lower-Leftif(FreeTile(x=BestNode-x-TILESIZE,y=BestNode-y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Leftif(FreeTile(x=BestNode-x-TILESIZE,y=BestNode-y))GenerateSucc(BestNode,x,y,dx,dy);}看看最重要的函数GenerateSucc：voidAstarPathfinder::GenerateSucc(NODE*BestNode,intx,inty,intdx,intdy){intg,TileNumS,c=0;NODE*Old,*Successor;//计算子节点的g值g=BestNode-g+1;//g(Successor)=g(BestNode)+costofgettingfromBestNodetoSuccessorTileNumS=TileNum(x,y);//identificationpurposes//子节点再Open表中吗？if((Old=CheckOPEN(TileNumS))!=NULL)//ifequaltoNULLthennotinOPENlist,//elseitreturnstheNodeinOld{//若在for(c=0;c8;c++)if(BestNode-Child[c]==NULL)//AddOldtothelistofBestNode'sChildren//(orSuccessors).break;BestNode-Child[c]=Old;//比较Open表中的估价值和当前的估价值（只要比较g值就可以了）if(gg)//ifournewgvalueisParent=BestNode;Old-g=g;Old-f=g+Old-h;}}else//在Closed表中吗？if((Old=CheckCLOSED(TileNumS))!=NULL)//ifequaltoNULLthennotinOPENlist//elseitreturnstheNodeinOld{//若在for(c=0;c8;c++)if(BestNode-Child[c]==NULL)//AddOldtothelistofBestNode's//Children(orSuccessors).break;BestNode-Child[c]=Old;//比较Closed表中的估价值和当前的估价值（只要比较g值就可以了）if(gg)//ifournewgvalueisParent=BestNode;Old-g=g;Old-f=g+Old-h;//再依次更新Old的所有子节点的估价值PropagateDown(Old);//SincewechangedthegvalueofOld,weneed//topropagatethisnewvaluedownwards,i.e.//doaDepth-Firsttraversalofthetree!}}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);//shoulddosqrt(),butsincewedon'treallySuccessor-f=g+Successor-h;//careaboutthedistancebutjustwhichbranchlooksSuccessor-x=x;//betterthisshouldsuffice.Anyayzit'sfaster.Successor-y=y;Successor-NodeNum=TileNumS;//再插入Open表中，同时排序。Insert(Successor);//InsertSuccessoronOPENlistwrtffor(c=0;c8;c++)if(BestNode-Child[c]==NULL)//AddOldtothelistofBestNode