A*（A-Star)算法是一种静态路网中求解最短路最有效的方法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。
A-star算法的原理
节点(Node)：每个格子都可以称为节点。
代价(Cost)：描述角色移动到某个节点时所走的距离（或难易程度）。
对于“曼哈顿算法”，，笔直的走，然后转个弯，再笔直的继续。
“几何算法”的最好解释就是“勾股定理”，算出起点与终点之间的直线距离，然后乘上代价因子。
“对角算法”综合了以上二种算法，先按对角线走，一直走到与终点水平或垂直平行后，再笔直的走。
若以当前单元格为起点（称为父单元格，它的周围有八个方向），下一步走哪呢？
这时就得给下一步的单元格（称为子单元格）进行“估价”。
“估价”可用估价函数来实现。
入门级的估价函数是这样的：
终点到目前点的估计代价＝终点至当前点的直线距离
于是下一步的代价可以这样算
代价＝起点到当前点的实际步数（通过一个变量累加可以直接得到）+终点到目前点的估计代价
然后把估价后的单元格放入“待考察表”
从待考察表中取代价最小的单元格作为起点，对它周围8个方向的单元格进行估价，然后把它放入“已考察表”。
若对一个单元格估价时，发现它已经在“待考察表”中则比较该单元格原先的估价和当前的估价，保留小的估价，并更新其父单元格属性。
不断重复以上过程，直到在“待考察表”中取出的单元格是终点单元格为止，若“待考察表为空”则表示找不到路径。
到达终点单元格后，通过其“父单元格”属性，一直找到起点，便构成一条路径。
两个例子：
Enterthemap'sfilename:b.txtRows=7Cols=13...................x.........xxxx............x.........xxxx............x...................Setthestartpoint(x,y):53Settheendpoint(x,y):123Steps:12,311,210,19,08,07,06,05,04,03,12,23,34,35,3Rows=7Cols=13....******......*..x...*....*xxxx....*....***x.....*...xxxx............x...................===========================Enterthemap'sfilename:a.txtRows=7Cols=7........xxx......x.x....x.x......x......x......x.Setthestartpoint(x,y):00Settheendpoint(x,y):66Steps:6,66,56,46,36,25,14,03,02,01,00,0Rows=7Cols=7*****...xxx.*....x.x*...x.x*.....x*.....x*.....x*
C++代码
以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值+列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h值”表示。
2.1countH（state&st）;
countH函数功能是计算st状态的h值。
计算过程中将会用到rightPos数组，数组里记录的是目标状态下，0~9每个将牌在九宫格里的位置（位置=行下标*3+列下标）。
2.2f（state*p）;
f()=h()+level
2.3look_up_dup(vector
在open表或close表中，是否存在指定状态p，当找到与p完全相等的节点时，退出函数。
2.4search(state&start)；
在open表不为空时，按f值由小到大对open表中元素进行排序。
调用findZero()函数找到0值元素的位置。空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。确定某方向可走后，空格移动一步，生成状态p’。
此时，检查open表中是否已有p’，若有，更新p’数据；检查close表中是否已有p’，若有，将p’从close表中删除，添加到open表中。重复的执行这个过程，直到某状态的h值为零。
2.5dump_solution(state*q)；
在终端输出解路径。
//A*算法八数码问题
#include"stdafx.h"
#include
#include
#include
#include
usingnamespacestd;
constintGRID=3;//Grid表示表格的行数(列数)，这是3*3的九宫格
intrightPos[9]={4,0,1,2,5,8,7,6,3};//目标状态时，若p[i][j]=OMG,那么3*i+j=rightPos[OMG]
structstate{
intpanel[GRID][GRID];intlevel;//记录深度inth;
state*parent;
state(intlevel):level(level){}
booloperator==(state&q){
//判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回false
for(inti=0;i if(panel[i][j]!=q.panel[i][j])returnfalse;}} returntrue;} state&operator=(state&p){//以状态p为当前状态赋值，对应位置元素相同 for(inti=0;i return*this;}}; voiddump_panel(state*p){//将八数码按3*3矩阵形式输出for(inti=0;i cout< intcountH(state&st){//给定状态st，计算它的h值。 inth=0; for(inti=0;i h+=abs(rightPos[st.panel[i][j]]/GRID-i)+ abs(rightPos[st.panel[i][j]]%GRID-j); //h=各个将牌与其目标位置的距离之和.距离定义为：行下标之差的绝对值+列下标之差的绝对值。}} returnh;} intfindZero(state&st){//找到零值元素，返回其在表中的位置 for(inti=0;i intf(state*p){//计算并返回f()值，即h值+levelreturncountH(*p)+p->level;} boolcompare_state(state*p,state*q){//比较两个状态的f值returnf(p)>f(q);} vector vector returnit_r;} state*search(state&start){//A*算法进行搜索 intlevel=0; open_table.push_back(&start);intcount=0; while(!open_table.empty()){ sort(open_table.begin(),open_table.end(),compare_state);//对open表中的元素进行排序 state*p=open_table.back();open_table.pop_back(); if(countH(*p)==0) returnp;//所有将牌到达目标位置，搜索过程结束level=p->level+1; intzeroPos=findZero(*p); intx=zeroPos/3;//空格的行下标inty=zeroPos%3;//空格的列下标 for(inti=0;i<4;i++){//上下左右四个方向intx_offset=0,y_offset=0;switch(i){ case0:x_offset=0,y_offset=1;break;//右case1:x_offset=0,y_offset=-1;break;//左case2:x_offset=1,y_offset=0;break;//上case3:x_offset=-1,y_offset=0;break;//下}; if(x+x_offset<0||x+x_offset>=GRID||y+y_offset<0||y+y_offset>=GRID){continue; //若移动一步后，将超出上/下/左/右边界，则这个方向不可走，尝试下一个方向 } state*q=newstate(level);//这个方向可走，扩展下一个节点 q->parent=p;*q=*p; q->panel[x][y]=q->panel[x+x_offset][y+y_offset];q->panel[x+x_offset][y+y_offset]=0;//空格沿这个方向移一步 boolskip=false; vector if(dup!=open_table.end()){if(f(q) (*dup)->level=q->level;(*dup)->parent=q->parent;} skip=true;} dup=look_up_dup(close_table,q); if(dup!=close_table.end()){//若q已在close表中，且f值比原值小， if(f(q) delete*dup; close_table.erase(dup);open_table.push_back(q);skip=true;}} if(!skip){ open_table.push_back(q);}} close_table.push_back(p);}} voiddump_solution(state*q)//输出解路径{ vector trace.push_back(q);q=q->parent;} intcount=0; while(!trace.empty()){ cout<<"Step"< dump_panel(trace.back()); cout<<"h:"< < intmain(){ statep(0);state*q; p.panel[0][0]=2;//设置初始状态p.panel[0][1]=1;p.panel[0][2]=6;p.panel[1][0]=4;p.panel[1][1]=0;p.panel[1][2]=8;p.panel[2][0]=7;p.panel[2][1]=5;p.panel[2][2]=3;