《A 寻路算法模拟实现 C++ 可运行》由会员分享,可在线阅读,更多相关《A 寻路算法模拟实现 C++ 可运行(6页珍藏版)》请在金锄头文库上搜索。
1、/写一个自己实现的A*搜寻算法/ #include “stdafx.h“#include #include #include #include #include using namespace std;const int nMapWidth = 8; const int nMapHeight = 8;struct Nodeint nEnable; int nNodeMark; int nValue; int x;int y; Node():nEnable(0),nNodeMark(0),nValue(0),x(0),y(0);std:map m_OpenList;std:map m_Close
2、List; std:vectorm_KeyList;Node m_MapNodenMapWidthnMapHeight;/计算openlist中靠前节点四周的节点 void ComputerRound(int curx,int cury);/将一个新的节点参加到OPenList中void AddNodeToOpenList(Node* pNode,int nNum);/打印地图void Print(Node pNodenMapHeight);void Print(Node pNodenMapHeight)for (int n = 0; n nMapWidth; +n)for(int m = 0
3、; m nMapHeight; +m)if (m = 0)coutendl; if (n = 0)coutpNodenm.nEnable/*“(“ “pNodenm.nNodeMark“)“*/“;elsecoutpNodenm.nEnable/*“(“pNodenm.nNodeMark“)“*/nEnable) return;if (m_OpenList.empty()elsem_OpenListpNode-nNodeMark = nNum; m_KeyList.push_back(pNode-nNodeMark);std:map:iterator itr = m_OpenList.find
4、(pNode-nNodeMark); if (itr = m_OpenList.end()std:map:iterator itrQ = m_CloseList.find(pNode-nNodeMark); if (itrQ != m_CloseList.end()if (nNum nNodeMark =nNum; m_KeyList.push_back(pNode-nNodeMark);if (*itr).second nNum)m_OpenListpNode-nNodeMark =nNum;/将openlist中的一个靠前的节点开放到CloseList中void AddNodeToClos
5、eList(Node* pNode,int nNum)if(!pNode)return;if (m_CloseList.empty()elsem_CloseListpNode-nNodeMark = nNum; ComputerRound(pNode-x,pNode-y);std:map:iterator itrB = m_CloseList.find(pNode-nNodeMark); if(itrB = m_CloseList.end()std:map:iterator itrO = m_OpenList.find(pNode-nNodeMark); if (itrO != m_OpenL
6、ist.end()if (*itrO).second nNum)return;elsestd:vector:iterator itrK =std:find(m_KeyList.begin(),m_KeyList.end(),(*itrO).first);if (itrK != m_KeyList.end() m_KeyList.erase(itrK);m_OpenList.erase(itrO);elseelsem_CloseListpNode-nNodeMark += nNum; ComputerRound(pNode-x,pNode-y);if (nNum nNodeMark) m_Clo
7、seListpNode-nNodeMark = nNum;/探究是否该节点可行void TryNode(int nx,int ny,int curx, int cury)if (nx 0 | ny = nMapWidth | ny = nMapWidth) return;if (m_MapNodenxny.nEnable = 0) return;int nNum = abs(nx - curx) + abs(ny - cury);std:map:iterator itr = m_CloseList.find(m_MapNodecurxcury.nNodeMark); if(itr != m_C
8、loseList.end()nNum += (*itr).second; AddNodeToOpenList(&(m_MapNodenxny),nNum);#define DesX3#define DesY 4voidComputerRound(intcurx,intcury)/对每一个当前节点执行以下操作TryNode(curx,cury+1,curx,cury); TryNode(curx+1,cury,curx,cury); TryNode(curx+1,cury+1,curx,cury); TryNode(curx-1,cury,curx,cury); TryNode(curx-1,c
9、ury-1,curx,cury); TryNode(curx-1,cury+1,curx,cury); TryNode(curx,cury-1,curx,cury);TryNode(curx+1,cury-1,curx,cury);void main()int nMark = 0;for (int n = 0; n nMapWidth; +n)for(int m = 0; m nMapHeight; +m)if (n != 2 | m = 3 | m = 1) m_MapNodenm.nEnable = 1;if (n = 4 & (m != 6) m_MapNodenm.nEnable =
10、0;m_MapNodenm.nNodeMark = +nMark; m_MapNodenm.x = n; m_MapNodenm.y = m;Print(m_MapNode);AddNodeToCloseList(&(m_MapNode11),0);std:map:iterator itr; while(!m_KeyList.empty()itr = m_OpenList.find(*(m_KeyList.begin(); int nV = (*itr).first;int nNum =(*itr).second; std:vector:iterator itrK =std:find(m_Ke
11、yList.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:iterator itrC; for (int n = 0; n nMapWidth; +n)for(int m = 0; m nMapHeight; +m)if (m = 0)coutendl;if (m = 1 & n = 1)cout“ST“ “;continue;itrC = m_CloseList.find(m_MapNodenm.nNodeMark); if (itrC != m_CloseList.end()elsecout(*itrC).second“;cout“0“;getchar();