A寻路算法模拟实现C++可运行

1、/写一个自己实现的A*搜索算法/#includestdafx.h#include#include#include#include#includeusingnamespacestd;constintnMapWidth=8;constintnMapHeight=8;structNodeintnEnable;intnNodeMark;intnValue;intx;inty;Node():nEnable(0),nNodeMark(0),nValue(0),x(0),y(0);std:mapm_OpenList;std:map:iteratoritrO=m_OpenList.find(pNode-nNo

2、deMark);if(itrO!=m_OpenList.end()std:map:iteratoritrO=m_OpenList.find(pNode-nNodeMark);if(itrO!=m_OpenList.end()std:mapm_CloseList;std:vectorm_KeyList;Nodem_MapNodenMapWidthnMapHeight;/计算openlist中靠前节点周围的节点voidComputerRound(intcurx,intcury);/将一个新的节点加入到OPenList中voidAddNodeToOpenList(Node*pNode,intnNum

3、);/打印地图voidPrint(NodepNodenMapHeight);voidPrint(NodepNodenMapHeight)for(intn=0;nnMapWidth;+n)for(intm=0;mnMapHeight;+m)if(m=0)coutendl;if(n=0)coutpNodenm.nEnable/*(pNodenm.nNodeMark)*/elsecoutpNodenm.nEnable/*(pNodenm.nNodeMark)*/nEnable)return;if(m_OpenList.empty()m_OpenListpNode-nNodeMark=nNum;m_K

4、eyList.push_back(pNode-nNodeMark);elsestd:map:iteratoritrQ=m_CloseList.find(pNode-nNodeMark);if(itrQ!=m_CloseList.end()std:map:iteratoritrO=m_OpenList.find(pNode-nNodeMark);if(itrO!=m_OpenList.end()std:map:iteratoritrO=m_OpenList.find(pNode-nNodeMark);if(itrO!=m_OpenList.end()if(nNumnNodeMark=nNum;m

5、_KeyList.push_back(pNode-nNodeMark);elseif(*itr).secondnNum)m_OpenListpNode-nNodeMark=nNum;/将openlist中的一个靠前的节点展开到CloseList中voidAddNodeToCloseList(Node*pNode,intnNum)if(!pNode)return;if(m_CloseList.empty()m_CloseListpNode-nNodeMark=nNum;ComputerRound(pNode-x,pNode-y);elsestd:map:iteratoritrB=m_CloseL

6、ist.find(pNode-nNodeMark);if(itrB=m_CloseList.end()if(*itrO).secondnNum)return;std:map:iteratoritr;while(!m_KeyList.empty()elsestd:vector:iteratoritrK=std:find(m_KeyList.begin(),m_KeyList.end(),(*itrO).first);if(itrK!=m_KeyList.end()m_KeyList.erase(itrK);m_OpenList.erase(itrO);elsem_CloseListpNode-n

7、NodeMark+=nNum;ComputerRound(pNode-x,pNode-y);elseif(nNumnNodeMark)m_CloseListpNode-nNodeMark=nNum;/探索是否该节点可行voidTryNode(intnx,intny,intcurx,intcury)if(nx0|ny=nMapWidth|ny=nMapWidth)return;if(m_MapNodenxny.nEnable=0)return;intnNum=abs(nx-curx)+abs(ny-cury);std:map:iteratoritr=m_CloseList.find(m_MapN

8、odecurxcury.nNodeMark);if(itr!=m_CloseList.end()nNum+=(*itr).second;AddNodeToOpenList(&(m_MapNodenxny),nNum);#defineDesX3#defineDesY4voidComputerRound(intcurx,intcury)/对每一个当前节点执行以下操作std:map:iteratoritr;while(!m_KeyList.empty()TryNode(curx,cury+1,curx,cury);TryNode(curx+1,cury,curx,cury);TryNode(curx

9、+1,cury+1,curx,cury);TryNode(curx-1,cury,curx,cury);TryNode(curx-1,cury-1,curx,cury);TryNode(curx-1,cury+1,curx,cury);TryNode(curx,cury-1,curx,cury);TryNode(curx+1,cury-1,curx,cury);voidmain()intnMark=0;for(intn=0;nnMapWidth;+n)for(intm=0;mnMapHeight;+m)if(n!=2|m=3|m=1)m_MapNodenm.nEnable=1;if(n=4&(

10、m!=6)m_MapNodenm.nEnable=0;m_MapNodenm.nNodeMark=+nMark;m_MapNodenm.x=n;m_MapNodenm.y=m;Print(m_MapNode);AddNodeToCloseList(&(m_MapNode11),0);itr=m_OpenList.find(*(m_KeyList.begin();intnV=(*itr).first;intnNum=(*itr).second;std:vector:iteratoritrK=std:find(m_KeyList.begin(),m_KeyList.end(),(*itr).first);if(itrK!=m_KeyList.end()m_KeyList.erase(itrK);itr=m_OpenList.erase(itr);AddNodeToCloseList(&(m_MapNode(nV-1)/nMapWidth(nV-1)%nMapWidth),nNum);coutendl;coutendl;std:map:iteratoritrC;for(intn=0;nnMapWidth;+n)for(intm=0