搜索
/*========================================================================精简的A*算法作者：添翼虎网址：@163.net本程序参考了风云的最短路径代码(~cloudwu)，并加以改进和优化：1、把原来用于存放已处理节点的堆栈改为(store_queue)队列，这样在从sort_queue队列出列时可直接放入store_queue中。2、解除了地图大小的限制(如果有64K内存限制时，地图大小只能是180x180)3、删除了原程序中的一些冗余，见程序中的注释。4、程序继续使用dis_map数组保存各点历史历史最佳距离，也包含了某点是否已经经过的信息，虽然这样做可能会比使用链表多用一些内存，但是在搜索时可以节省不时间。5、程序更具有实用性，可直接或修改后运用于你的程序中，但请你使用该代码后应该返回一些信息给我，如算法的改进或使用于什么程序等。本程序可以用BorlandC++或DJGPP编译，并附带有一个数据文件map.dat,保存有地图的数据，（注：该地图文件格式与风云的原代码的地图格式不一样）-------------------------------------------------------------------------*///#defineNDEBUG#includestdio.h#includeconio.h#includeassert.h#includestdlib.h#definetile_num(x,y)((y)*map_w+(x))//将x,y坐标转换为地图上块的编号#definetile_x(n)((n)%map_w)//由块编号得出x,y坐标#definetile_y(n)((n)/map_w)#defineMAPMAXSIZE180//地图面积最大为180x180，如果没有64K内存限制可以更大#defineMAXINT32767//树结构,比较特殊,是从叶节点向根节点反向链接，方便从叶节点找到根节点typedefstructtree_node*TREE;structtree_node{inth;//节点所在的高度，表示从起始点到该节点所有的步数inttile;//该节点的位置TREEfather;//该节点的上一步};//链接结构，用于保存处理过的和没有处理过的结点typedefstructlink_node*LINK;structlink_node{TREEnode;intf;LINKnext;};LINKsort_queue;//保存没有处理的行走方法的节点LINKstore_queue;//保存已经处理过的节点(搜索完后释放)unsignedchar*map;//地图数据unsignedint*dis_map;//保存搜索路径时,中间目标地最优解intmap_w,map_h;//地图宽和高intstart_x,start_y,end_x,end_y;//地点,终点坐标//初始化队列voidinit_queue(){sort_queue=(LINK)malloc(sizeof(*sort_queue));sort_queue-node=NULL;sort_queue-f=-1;sort_queue-next=(LINK)malloc(sizeof(*sort_queue));sort_queue-next-node=NULL;sort_queue-next-f=MAXINT;sort_queue-next-next=NULL;store_queue=(LINK)malloc(sizeof(*store_queue));store_queue-node=NULL;store_queue-f=-1;store_queue-next=NULL;}//待处理节点入队列,依靠对目的地估价距离插入排序voidenter_queue(TREEnode,intf){LINKp=sort_queue,father,q;while(fp-f){father=p;p=p-next;assert(p);}q=(LINK)malloc(sizeof(*q));assert(sort_queue);q-f=f,q-node=node,q-next=p;father-next=q;}//将离目的地估计最近的方案出队列TREEget_from_queue(){LINKbestchoice=sort_queue-next;LINKnext=sort_queue-next-next;sort_queue-next=next;bestchoice-next=store_queue-next;store_queue-next=bestchoice;returnbestchoice-node;}//释放栈顶节点voidpop_stack(){LINKs=store_queue-next;assert(s);store_queue-next=store_queue-next-next;free(s-node);free(s);}//释放申请过的所有节点voidfreetree(){inti;LINKp;while(store_queue){p=store_queue;free(p-node);store_queue=store_queue-next;free(p);}while(sort_queue){p=sort_queue;free(p-node);sort_queue=sort_queue-next;free(p);}}//估价函数,估价x,y到目的地的距离,估计值必须保证比实际值小intjudge(intx,inty){intdistance;distance=abs(end_x-x)+abs(end_y-y);returndistance;}//尝试下一步移动到x,y可行否inttrytile(intx,inty,TREEfather){TREEp=father;inth;if(map[tile_num(x,y)]!='')return1;//如果(x,y)处是障碍,失败//这一步用来判断(x,y)点是否已经加入队列，多余可以删除，因为dis_map已经//保存该点是否已经保存//while(p){//if(x==tile_x(p-tile)&&y==tile_y(p-tile))return1;//如果(x,y)曾经经过,失败//p=p-father;//}h=father-h+1;if(h=dis_map[tile_num(x,y)])return1;//如果曾经有更好的方案移动到(x,y)失败dis_map[tile_num(x,y)]=h;//记录这次到(x,y)的距离为历史最佳距离//将这步方案记入待处理队列p=(TREE)malloc(sizeof(*p));p-father=father;p-h=father-h+1;p-tile=tile_num(x,y);enter_queue(p,p-h+judge(x,y));return0;}//路径寻找主函数int*findpath(void){TREEroot;inti,j;int*path;memset(dis_map,0xff,map_h*map_w*sizeof(*dis_map));//填充dis_map为0XFF，表示各点未曾经过init_queue();root=(TREE)malloc(sizeof(*root));root-tile=tile_num(start_x,start_y);root-h=0;root-father=NULL;enter_queue(root,judge(start_x,start_y));for(;;){intx,y,child;TREEp;root=get_from_queue();if(root==NULL){returnNULL;}x=tile_x(root-tile);y=tile_y(root-tile);if(x==end_x&&y==end_y)break;//达到目的地成功返回child=trytile(x,y-1,root);//尝试向上移动child&=trytile(x,y+1,root);//尝试向下移动child&=trytile(x-1,y,root);//尝试向左移动child&=trytile(x+1,y,root);//尝试向右移动//child&=trytile(x+1,y-1,root);//尝试向右上移动//child&=trytile(x+1,y+1,root);//尝试向右下移动//child&=trytile(x-1,y+1,root);//尝试向左下移动//child&=trytile(x-1,y-1,root);//尝试向左上移动if(child!=0)pop_stack();//如果四个方向均不能移动,释放这个死节点}//回溯树，将求出的最佳路径保存在path[]中path=(int*)malloc((root-h+2)*sizeof(int));assert(path);for(i=0;root;i++){path[i]=root-tile;root=root-father;}path[i]=-1;freetree();returnpath;}voidprintpath(int*path){inti;if(path==NULL)return;for(i=0;path[i]=0;i++){gotoxy(tile_x(path[i])+1,tile_y(path[i])+1);cprintf(.);}}intreadmap(){FILE*f;inti,j;f=fopen(map.dat,r);assert(f);fscanf(f,%d,%d\n,&map_w,&map_h);map=malloc(map_w*map_h+1);assert(map);for(i=0;imap_h;i++)fgets(map+tile_num(0,i),map_w+2,f);fclose(f);start_x=-1,end_x=-1;for(i=0;imap_h;i++)for(j=0;jmap_w;j++){if(map[tile_num(j,i)]=='s')map[tile_num(j,i)]='',start_x=j,start_y=i;if(map[tile_num(j,i)]=='e')map[tile_num(j,i)]='',end_x=j,end_y=i;}assert(start_x=0&&end_x=0);dis_map=malloc(map_w*map_h*sizeof(*dis_map));assert(dis_map);return0;}voidshowmap(){inti,j;clrscr();for(i=0;imap_h;i++){gotoxy(1,i+1);for(j=0;jmap_w;j++)if(map[tile_num(j,i)]!='')cprintf(O);elsecprintf();}gotoxy(start_x+1,start_y+1);cprintf(s);gotoxy(end_x+1,end_y+1);cprintf(e);}intmain(){int*path;readmap();showmap();getch();path=findpath();printpath(path);if(dis_map)free(dis_map);if(path)free(path);if(map)free(map)