在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*算法在最短路径搜索的例子。值得注意的是这里并不对A*的基本的概念作介绍，如果你还对A*算法不清楚的话，请看姊妹篇《初识A*算法》。
这里所举的例子是参考AMIT主页中的一个源程序，你可以在AMIT的站点上下载也可以在我的站点上下载。你使用这个源程序时，应该遵守一定的公约。

1、A*算法的程序编写原理
我在《初识A*算法》中说过，A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。如图有如下的状态空间（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）：

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 dx, 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 to 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 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 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 just which branch
looks Successor->x = x; // better this should suffice. Anyayz 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 to the list of BestNode’s
Children (or Successors).
break;
BestNode->Child[c] = Successor;
}
}

哈哈。A*算法我懂了。当然，我希望你有这样的感觉。不过我还要再说几句。仔细看看这个程序，你会发现，这个程序和我前面说的伪程序有一些不同，在GenerateSucc函数中，当子节点在Closed表中时，没有将子节点从Closed表中删除并放入Open表中。而是直接的重新的计算该节点的所有子节点的估价值（用PropagateDown函数）。这样可以快一些。另当子节点在Open表和Closed表中时，重新的计算估价值后，没有重新的对Open表中的节点排序，我有些想不通，为什么不排呢？会不会是一个小小的BUG。你知道告诉我好吗？
好了。主要的内容都讲完了，还是完整仔细的看看源程序吧。希望我所的对你有一点帮助，一点点也可以。如果你对文章中的观点有异议或有更好的解释都告诉我。