网站界面设计案例教程,wordpress 分类目录函数,做seo网站优化价格,商城网站建设那家好一、前言 在这里我将对A*算法的实际应用进行一定的探讨#xff0c;并且举一个有关A*算法在最短路径搜索的例子。 二、A*算法的程序编写原理 A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。 如图有如下的状态空间#xff1a;…一、前言 在这里我将对A*算法的实际应用进行一定的探讨并且举一个有关A*算法在最短路径搜索的例子。 二、A*算法的程序编写原理 A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。 如图有如下的状态空间起始位置是A目标位置是P字母后的数字表示节点的估价值 搜索过程中设置两个表OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点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表中删除。 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*算法进行设计。他的好处我们就不用管了反正就是好^_* 先复习一下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值// should really use sqrt().Node-h (dx-sx)*(dx-sx) (dy-sy)*(dy-sy);//这是计算f值即估价值Node-f Node-gNode-h;Node-NodeNum TileNum(dx, dy);Node-x dx; Node-y dy;// make Open List point to first nodeOPEN-NextNodeNode;for (;;){//从Open表中取得一个估价值最好的节点BestNodeReturnBestNode();//如果该节点是目标节点就退出// if weve found the end, break and finish break;if (BestNode-NodeNum TileNumDest)//否则生成子节点GenerateSuccessors(BestNode,sx,sy);}PATH BestNode;
} 再看看生成子节点函数 void AstarPathfinder::GenerateSuccessors(NODE *BestNode, int dx, int dy)
{int x, y;//哦依次生成八个方向的子节点简单// Upper-Leftif ( FreeTile(xBestNode-x-TILESIZE, yBestNode-y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Upperif ( FreeTile(xBestNode-x, yBestNode-y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Upper-Rightif ( FreeTile(xBestNode-xTILESIZE, yBestNode-y-TILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Rightif ( FreeTile(xBestNode-xTILESIZE, yBestNode-y) )GenerateSucc(BestNode,x,y,dx,dy);// Lower-Rightif ( FreeTile(xBestNode-xTILESIZE, yBestNode-yTILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Lowerif ( FreeTile(xBestNode-x, yBestNode-yTILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Lower-Leftif ( FreeTile(xBestNode-x-TILESIZE, yBestNode-yTILESIZE) )GenerateSucc(BestNode,x,y,dx,dy);// Leftif ( FreeTile(xBestNode-x-TILESIZE, yBestNode-y) )GenerateSucc(BestNode,x,y,dx,dy);
} 看看最重要的函数 void AstarPathfinder::GenerateSucc(NODE *BestNode,int x, int y, int dx, int dy)
{int g, TileNumS, c 0;NODE *Old, *Successor;//计算子节点的 g 值// g(Successor)g(BestNode)cost of getting from BestNode to Successorg BestNode-g1;// identification purposesTileNumS TileNum(x,y);//子节点再Open表中吗// if equal to NULL then not in OPEN list, else it returns the Node in Oldif ( (OldCheckOPEN(TileNumS)) ! NULL ){//若在for( c 0; c 8; c)// Add Old to the list of BestNodes Children (or Successors).if( BestNode-Child[c] NULL )break;BestNode-Child[c] Old;//比较Open表中的估价值和当前的估价值只要比较g值就可以了// if our new g value is Olds then reset Olds parent to point to BestNodeif ( g Old-g ){//当前的估价值小就更新Open表中的估价值Old-Parent BestNode;Old-g g;Old-f g Old-h;}}else//在Closed表中吗// if equal to NULL then not in OPEN list, else it returns the Node in Oldif ( (OldCheckCLOSED(TileNumS)) ! NULL ){//若在for( c 0; c 8; c)// Add Old to the list of BestNodes Children (or Successors).if ( BestNode-Child[c] NULL )break;BestNode-Child[c] Old;//比较Closed表中的估价值和当前的估价值只要比较g值就可以了// if our new g value is Olds then reset Olds parent to point to BestNodeif ( 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 new value downwards, i.e.// do a Depth-First traversal of the tree!PropagateDown(Old);}}//不在Open表中也不在Close表中else{//生成新的节点Successor ( NODE* )calloc(1,sizeof( NODE ));Successor-Parent BestNode;Successor-g g;// should do sqrt(), but since we dont reallySuccessor-h (x-dx)*(x-dx) (y-dy)*(y-dy);// care about the distance but just which branch looksSuccessor-f gSuccessor-h;// better this should suffice. Anyayz its faster.Successor-x x;Successor-y y;Successor-NodeNum TileNumS;//再插入Open表中同时排序。// Insert Successor on OPEN list wrt fInsert(Successor);for( c 0; c 8; c)// Add Old to the list of BestNodes Children (or Successors).if ( BestNode-Child[c] NULL )break;BestNode-Child[c] Successor;}
} 哈哈A*算法我懂了当然我希望你有这样的感觉不过我还要再说几句。仔细看看这个程序你会发现这个程序和我前面说的伪程序有一些不同在GenerateSucc函数中当子节点在Closed表中时没有将子节点从Closed表中删除并放入Open表中。而是直接的重新的计算该节点的所有子节点的估价值用PropagateDown函数。这样可以快一些另当子节点在Open表和Closed表中时重新的计算估价值后没有重新的对Open表中的节点排序我有些想不通为什么不排呢:-(会不会是一个小小的BUG。你知道告诉我好吗 好了主要的内容都讲完了还是完整仔细的看看源程序吧希望我所的对你有一点帮助一点点也可以。如果你对文章中的观点有异议或有更好的解释都告诉我。我的email在文章最后 转载于:https://www.cnblogs.com/Mr_SuperBaby/archive/2012/04/23/2467221.html
