下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 #ifndef _ASTAR_H_

#ifndef _ASTAR_H_.doc

#ifndef _ASTAR_H_

15岁懵懂花季
2017-09-27 0人阅读 举报 0 0 暂无简介

简介:本文档为《#ifndef _ASTAR_H_doc》,可适用于经济金融领域

#ifndefASTARH#defineASTARH从上面#ifndef开始到#endif结束是头文件内容typedefunsignedlongADWORDclassAstarPathFind{protected:structTAstarNode{ADWORDPos该点的坐标(,)的模式保存(y,x)shortActualCost保存从起点到该节点的实际开销shortEstimateCost保存此点的估价开销shortSumCost上面两者之和TAstarNode*Father此点的父节点TAstarNode*Prev在Open或者Next中的上一个节点TAstarNode*Next在Open或者Next链表中的下一个节点charModified该节点是否被修改过记录而备清除空,Open,CloseshortDirWalked有字节点的方向(未用)shortDirFrom从哪个方向来的(未用)}TAstarNode**Node对应地图中每个节点TAstarNode*Open保存没有处理的按估计值排序的节点TAstarNode*Close保存处理过的节点TAstarNode**Modify保存修改过的节点intheight地图的高度intwidth地图的宽度ADWORDMaxSize最大面积即height*widthADWORDModifyPointModify数组的指针ADWORDOpenCountOpen队列中的节点数目ADWORDCloseCountClose队列里面的节点数目ADWORDOpenLimitedOpen队列最多节点数目ADWORDCloseLimitedClose队列最多节点数目shortDirMask要搜索方向的标志位为从上开始顺时针七个方向ADWORDMinPos终点或最接近终点的节点shortTargetX终点坐标shortTargetYchar(*MoveAble)(shortx,shorty)检查地图是否可以移动函数指针short(*JudgeCost)(short,short,short,short)取得估计值的函数指针charAddToOpenQueue(TAstarNode*node)将节点排序加入Open队列charGetFromOpenQueue()从Open队列取出最小的并放入Close队列charPopCloseStack()取出Close队列中的节点voidClearModified()清除所有搜索记录charTryTile(shortx,shorty,TAstarNode*Father,charFromDir)public:intCreate(intmapw,intmaph,char(*MoveCheck)(shortx,shorty),short(*JudgeFun)(shortx,shorty,shortdx,shortdy))intRelease()virtualintFindPath(shortstartx,shortstarty,shortendx,shortendy)intGetPosPath(short*PosXY,intmaxpos)intGetDirPath(char*Dirs,intmaxpos)voidSetJudgeFun(short(*JudgeFun)(short,short,short,short))voidSetMapCheck(char(*MapCheck)(short,short))voidSetOpenLimited(longOpenLimited)voidSetCloseLimited(longCloseLimited)voidSetDirMask(longDirMask)}#endif#include<stdioh>#defineCOSTMAX#definetilepos(x,y)(((ADWORD)y<<)|x)#definetilex(pos)(posxffff)#definetiley(pos)(pos>>)待处理节点入队列,依靠对目的地估价距离插入排序charAstarPathFind::AddToOpenQueue(TAstarNode*node){ADWORDishortf=node>SumCostregisterTAstarNode*p,*bnode>Modified|=记录Open标志for(b=,p=Open,i=pi<=OpenCountb=p,p=p>Next,i)if(f<=p>SumCost)breakif(i>OpenCount)returnnode>Next=pnode>Prev=bif(b)b>Next=nodeelseOpen=nodeif(p)p>Prev=nodeOpenCountreturn}将离目的地估计最近的方案出队列charAstarPathFind::GetFromOpenQueue(){TAstarNode*BestChoice=Openif(!Open)returnOpen=Open>Nextif(Open)Open>Prev=if(BestChoice>Modified)return已经在Close中了BestChoice>Next=CloseBestChoice>Prev=BestChoice>Modified=清除Open标志BestChoice>Modified|=设置Close标志if(Close)Close>Prev=BestChoiceClose=BestChoiceOpenCountCloseCountreturn}释放栈顶节点charAstarPathFind::PopCloseStack(){if(Close){Close>Modified=清除Close标志Close=Close>Nextif(Close)Close>Prev=CloseCountreturn}return}还原修改过的所有节点voidAstarPathFind::ClearModified(){ADWORDifor(i=i<ModifyPointi){Modifyi>Modified=Modifyi>ActualCost=COSTMAX}ModifyPoint=OpenCount=CloseCount=Open=Close=}尝试下一步移动到x,y可行否charAstarPathFind::TryTile(shortx,shorty,TAstarNode*Father,charFromDir){registerTAstarNode*nodeshortActualCostif(!MoveAble(x,y))return如果地图无法通过则退出node=NodeyxActualCost=Father>ActualCost实际值计算if(ActualCost>=node>ActualCost)returnif(node>Modified)在Open表中就清除{if(node>Next)node>Next>Prev=node>Previf(node>Prev)node>Prev>Next=node>NextelseOpen=node>NextOpenCountnode>Modified=node>Father=Fathernode>ActualCost=ActualCostnode>SumCost=ActualCostnode>EstimateCostAddToOpenQueue(node)}elseif(node>Modified){在Close表中就清除if(node>Next)node>Next>Prev=node>Previf(node>Prev)node>Prev>Next=node>NextelseClose=node>NextCloseCountnode>Modified=node>Father=Fathernode>ActualCost=ActualCostnode>SumCost=ActualCostnode>EstimateCostAddToOpenQueue(node)}else{if(!(node>Modified))ModifyModifyPoint=node记录这个修改过的点以还原node>Modified=node>Father=Fathernode>DirFrom=FromDirnode>ActualCost=ActualCostnode>EstimateCost=JudgeCost(x,y,TargetX,TargetY)node>SumCost=ActualCostnode>EstimateCostAddToOpenQueue(node)将节点加入Open队列}return}路径寻找主函数intAstarPathFind::FindPath(shortstartx,shortstarty,shortendx,shortendy){TAstarNode*rootintj,okshortx,yADWORDmax=shortMinJudgeif(!Node||!Modify)returnClearModified()root=Nodestartystartxroot>ActualCost=root>EstimateCost=JudgeCost(startx,starty,endx,endy)root>SumCost=root>EstimateCostroot>Father=root>Modified=ModifyModifyPoint=rootAddToOpenQueue(root)MinPos=tilepos(startx,starty)MinJudge=root>EstimateCostTargetX=endxTargetY=endyfor(ok=ok==){ok=GetFromOpenQueue()取出Open队列估价值最小的节点放入Close中root=Close得到刚才取出的节点if(ok||root==){ok=break}x=(short)tilex(root>Pos)y=(short)tiley(root>Pos)if(root>EstimateCost<MinJudge)找到一个估计离终点最近的点MinJudge=root>EstimateCost,MinPos=root>Posif(CloseCount>max)max=CloseCountif(x==endxy==endy)MinPos=root>Pos,ok=如果走到终点了else{j=if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(DirMask)j=TryTile(x,y,root,)if(j)if(PopCloseStack()){ok=break}如果不是通路则从Close中取出}if(OpenCount>=OpenLimited||CloseCount>=CloseLimited)ok=}if(ok<)returnreturn}intAstarPathFind::GetPosPath(short*PosXY,intmaxpos){shortx,yADWORDjTAstarNode*p,*sintiif(maxpos>)maxposfor(p=Nodetiley(MinPos)tilex(MinPos),s=p,j=pj<MaxSizep=p>Father,j){x=(short)tilex(p>Pos)y=(short)tiley(p>Pos)i=(p>ActualCost<maxpos)p>ActualCost:maxposPosXYi<<=xPosXY(i<<)=y}i=(s>ActualCost<maxpos)(s>ActualCost):maxposPosXYi*=PosXYi*=return}intAstarPathFind::GetDirPath(char*PosDir,intmaxpos){staticcharincr={,,,,,,,,,}shorti,x,y,nx,nyADWORDjTAstarNode*p,*sx=(short)tilex(MinPos)y=(short)tiley(MinPos)if(maxpos>)maxposfor(p=Nodeyx,s=p,j=pj<MaxSizep=p>Father,j){nx=(short)tilex(p>Pos)ny=(short)tiley(p>Pos)i=(p>ActualCost<maxpos)(p>ActualCost):maxposPosDiri=incr(yny)*xnxx=nxy=ny}i=(s>ActualCost<maxpos)(s>ActualCost):maxposPosDiri=return}intAstarPathFind::Create(intmapw,intmaph,char(*MoveCheck)(short,short),short(*JudgeFun)(shortx,shorty,short,short)){inti,jheight=maphwidth=mapwMaxSize=maphMaxSize*=mapwModify=newTAstarNode*MaxSize*if(!Modify)returnNode=newTAstarNode*maphif(!Node){deleteModifyModify=return}for(i=i<maphi)Nodei=newTAstarNodemapwfor(i=,j=i<maphi)if(!Nodei)j=if(!j){for(i=i<maphi)if(Nodei)deleteNodeideleteNodedeleteModifyNode=Modify=return}for(j=j<maphj)for(i=i<mapwi){NodejiPos=tilepos(i,j)NodejiModified=NodejiActualCost=COSTMAX}ModifyPoint=SetMapCheck(MoveCheck)SetJudgeFun(JudgeCost=JudgeFun)SetDirMask(x)SetOpenLimited()SetCloseLimited(MaxSize)return}intAstarPathFind::Release(){intjif(Node)for(j=j<heightj)if(Nodej)deleteNodejif(Node)deleteNodeif(Modify)deleteModifyNode=Modify=return}voidAstarPathFind::SetJudgeFun(short(*JudgeFun)(short,short,short,short)){JudgeCost=JudgeFun}voidAstarPathFind::SetMapCheck(char(*MapCheck)(short,short)){MoveAble=MapCheck}voidAstarPathFind::SetOpenLimited(longOL){OpenLimited=OL}voidAstarPathFind::SetCloseLimited(longCL){CloseLimited=CL}voidAstarPathFind::SetDirMask(longDM){DirMask=(short)DM}#include<conioh>#include<stdlibh>#include<ctypeh>charmapintmaph,mapwstaticshortincx={,,,,,,,}staticshortincy={,,,,,,,}AstarPathFindPathFindintstartx,starty,endx,endyshortJudge(shortx,shorty,shortendx,shortendy){shortdx=abs(xendx)shortdy=abs(yendy)return(dxdy)<<}charPossible(shortx,shorty){if(x<||y<||x>=mapw||y>=maph)returnreturn(mapyx==''):}intreadmap(){inti,jFILE*fif((f=fopen("mapdat","r"))==)returnfscanf(f,"d,dn",mapw,maph)for(j=j<maphj)fgets(mapj,mapw,f)fclose(f)for(j=j<maphj)for(i=i<mapwi){if(mapji=='s'||mapji=='S')startx=i,starty=j,mapji=''if(mapji=='e'||mapji=='E')endx=i,endy=j,mapji=''}return}#include<timeh>#defineTIMESintmain(void){inti,jintx,ylongtdoublefif(readmap()){printf("nomapfilen")return}shortPosXYcharPosRfor(j=j<maphj){for(i=i<mapwi)putchar(mapji)putchar('n')}i=PathFindCreate(mapw,maph,Possible,Judge)if(i){printf("创建失败n")return}PathFindSetCloseLimited(*L)PathFindSetDirMask(xff)PathFindFindPath(startx,starty,endx,endy)PathFindGetPosPath(PosXY,)PathFindGetDirPath(PosR,)getch()for(i=PosXYi*>=i){x=PosXYi*y=PosXYi*mapyx=''}for(j=j<maphj){for(i=i<mapwi){putchar(mapji)if(mapji=='')mapji=''}putchar('n')}printf("AnykeytoTestingspeed,findingpathsn")getch()for(t=clock()t==clock())for(i=,t=clock()i<TIMESi){PathFindFindPath(startx,starty,endx,endy)PathFindGetPosPath(PosXY,)}t=clock()tf=TIMES*CLKTCKf=tPathFindRelease()printf("TimetofinddpathsisldTCKuse!freq=fn",TIMES,t,f)getch()return}

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/18

#ifndef _ASTAR_H_

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利