首页 > 代码库 > Cocos2d-x 3.1.1 学习日志16--A星算法(A*搜寻算法)的学习
Cocos2d-x 3.1.1 学习日志16--A星算法(A*搜寻算法)的学习
A *搜寻算法俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。
首先:1、在Map地图中任取2个点,开始点和结束点
2、首先判断该点是不是不可以穿越的点,或者是已经再close中了
3、如果2步骤为真,什么都不做,如果为假,那么我们就进行添加了
4、如果在添加的时候,发现该点在open中不存在,那么我们直接添加,而且视之为当前节点,如果该点 存在open中,那么我们比较G值,如果发现当前节点到该节点的G小于原来的G,那么再重新设置G,F值, 然后设置这个节点为当前节点。
5、再添判断玩之后,再添加它的4个邻接点,循环1-4的步骤。直至找到,或者说是open中为null了的时 候,就结束查询了。
代码如下:
#include <iostream> #include <string> #include "AStartMap.h" using namespace std; int main() { AstartMap *gameMap = new AstartMap; gameMap->initMap(); if(gameMap != 0) { delete gameMap; gameMap = 0; } return 0; } #ifndef ASTARTNODE_H_ #define ASTARTNODE_H_ class AStartNode { public: AStartNode(); ~AStartNode(); public: void setPos(int icol, int irow); void setG(int iG); int getG(); void setH(int iH); int getH(); void setF(int iF); void setFID(int iFID); int getFID(); int getF(); int getCol(); int getRow(); private: int m_Col; int m_Row; int m_G; int m_H; int m_F; int m_FID; };// end of AStartNode #endif // end of ASTARTNODE_H_ #include "AStartNode.h" AStartNode::AStartNode() : m_Col(0), // m_Row(0), m_G(0), m_H(0), m_F(0), m_FID(0) { } AStartNode::~AStartNode() { } void AStartNode::setPos(int icol, int irow) { m_Col = icol; m_Row = irow; } void AStartNode::setG(int iG) { m_G = iG; } int AStartNode::getG() { return m_G; } void AStartNode::setH(int iH) { m_H = iH; } int AStartNode::getH() { return m_H; } void AStartNode::setF(int iF) { m_F = iF; } int AStartNode::getF() { return m_F; } int AStartNode::getCol() { return m_Col; } int AStartNode::getRow() { return m_Row; } void AStartNode::setFID(int iFID) { m_FID = iFID; } int AStartNode::getFID() { return m_FID; } #ifndef ASTARTMAP_H_ #define ASTARTMAP_H_ #include <vector> class AStartNode; class AstartMap { public: typedef enum { STARTMAP_COL = 10, STARTMAP_ROW = 10, } StartMap; typedef enum { MAPPATH_BEGINPOINT = -2, MAPPATH_WALL = -1, MAPPATH_ROAD = 0, MAPPATH_ENDPOINT = 2, } MapPath; typedef enum { STARTNODE_G = 10, STARTNODE_H = 10, }StartNodeInfo; public: AstartMap(); ~AstartMap(); public: void initMap(); private: void _initMapBoard(); void _initSelectBeginPoint(); void _addIntoCloseNode(AStartNode *newCloseNode); void _addIntoOpenNode(AStartNode *newOpenNode); void _deleteBeginNodefromOpenNode(AStartNode *newOpenNode); void _add_adjacentnodeToOpenNode(AStartNode *newOpenNode); void _beginToMove(); void _setStartNode_G_H_Value(AStartNode *newOpenNode, AStartNode *parentNode); bool _isWater(AStartNode *pStartNode); bool _isInClose(AStartNode *pStartNode); bool _isInOpen(AStartNode *pStartNode); private: AStartNode *_getMinFstartNode(); AStartNode *_getAStartNodeAt(int iCol, int iRow); void _heapRebuild(std::vector<AStartNode *> &rStartNodeArray,int root,int size); void _heapSort(std::vector<AStartNode *> &rStartNodeArray ,int size); private: std::vector<AStartNode *> m_AstartNode; std::vector<AStartNode *> m_openNode; std::vector<AStartNode *> m_closeNode; AStartNode *m_pEndNode; int GameMap[STARTMAP_COL][STARTMAP_ROW]; // map };// end of AstartMap bool isNum(int inum); #endif // end of ASTARTMAP_H_ #include "AStartNode.h" #include <iostream> #include <ctype.h> #include <assert.h> #include <cmath> #include "AStartMap.h" extern bool isNum(int inum); AstartMap::AstartMap() : m_pEndNode(0) { } AstartMap::~AstartMap() { } void AstartMap::initMap() { /* *@init the game map */ _initMapBoard(); } void AstartMap::_initMapBoard() { //memset(GameMap, MAPPATH_ROAD, STARTMAP_COL * STARTMAP_ROW * sizeof(int)); for(int i = 0; i < STARTMAP_COL; ++i) { for(int j = 0; j < STARTMAP_ROW; ++j) { GameMap[i][j] = MAPPATH_ROAD; AStartNode *aStartNode = new AStartNode; aStartNode->setPos(i, j); m_AstartNode.push_back(aStartNode); } } for(int i = 0; i < 7; ++i) { // set the game wall GameMap[i + 2][4] = MAPPATH_WALL; } _initSelectBeginPoint(); } void AstartMap::_initSelectBeginPoint() { int ibegin_xpos = 0; int ibegin_ypos = 0; std::cout<<"Select the Begin Point(X in(0-9), y in (0- 9): \n"; std::cin>>ibegin_xpos; std::cin>>ibegin_ypos; if(!isNum(ibegin_xpos) || !isNum(ibegin_ypos)) return; std::cout<<"Select the End Point(X in(0-9), y in (0- 9): \n"; int iend_xpos = 0; int iend_ypos = 0; std::cin>>iend_xpos; std::cin>>iend_ypos; if(!isNum(iend_xpos) || !isNum(iend_ypos)) return; GameMap[iend_xpos][iend_ypos] = MAPPATH_ENDPOINT; // set end point AStartNode *pBeginNode = _getAStartNodeAt(ibegin_xpos, ibegin_ypos); m_pEndNode = _getAStartNodeAt(iend_xpos, iend_ypos); if(pBeginNode == 0) return; pBeginNode->setG(0); pBeginNode->setF(0); pBeginNode->setH(0); m_openNode.push_back(pBeginNode); /* *@Game Begin *the player begins to move */ _beginToMove(); } void AstartMap::_beginToMove() { while(true) { AStartNode *pBeginNode = _getMinFstartNode(); std::cout<<"select point: "<<pBeginNode->getCol()<<", "<<pBeginNode->getRow()<<std::endl; _add_adjacentnodeToOpenNode(pBeginNode); _addIntoCloseNode(pBeginNode); _deleteBeginNodefromOpenNode(pBeginNode); if(pBeginNode == m_pEndNode) { // find the end position std::cout<<"fine the end position"<<std::endl<<std::endl; break; } } } AStartNode *AstartMap::_getAStartNodeAt(int iCol, int iRow) { int iNode_Count = m_AstartNode.size(); for(int i = 0; i < iNode_Count; ++i) { if(m_AstartNode[i]->getCol() == iCol && m_AstartNode[i]->getRow() == iRow) return m_AstartNode[i]; } return 0; } void AstartMap::_addIntoCloseNode(AStartNode *newCloseNode) { if(newCloseNode == 0) return; m_closeNode.push_back(newCloseNode); } void AstartMap::_addIntoOpenNode(AStartNode *newOpenNode) { if(newOpenNode == 0) return; m_openNode.push_back(newOpenNode); // then other 4 node } void AstartMap::_add_adjacentnodeToOpenNode(AStartNode *newOpenNode) { int ileftNodeRow = newOpenNode->getRow() - 1; if(ileftNodeRow >= 0) { AStartNode *leftNode = _getAStartNodeAt(newOpenNode->getCol(), ileftNodeRow); if(!_isWater(leftNode) && !_isInClose(leftNode) ) { if(! _isInOpen(leftNode) ) { // in open leftNode->setFID(newOpenNode->getFID()); _addIntoOpenNode(leftNode); _setStartNode_G_H_Value(leftNode, newOpenNode); } else { // not in open // _setStartNode_G_H_Value(leftNode, newOpenNode); } } } int irightNodeRow = newOpenNode->getRow() + 1; if(irightNodeRow < STARTMAP_ROW) { AStartNode *rightNode = _getAStartNodeAt(newOpenNode->getCol(), irightNodeRow); if(!_isWater(rightNode) && !_isInClose(rightNode)) { if(! _isInOpen(rightNode) ) { // in open rightNode->setFID(newOpenNode->getFID()); _addIntoOpenNode(rightNode); _setStartNode_G_H_Value(rightNode, newOpenNode); } else { // not in open //_setStartNode_G_H_Value(rightNode, newOpenNode); } } } int iupNodeCol = newOpenNode->getCol() - 1; if(iupNodeCol >= 0) { AStartNode *upNode = _getAStartNodeAt(iupNodeCol, newOpenNode->getRow()); if(!_isWater(upNode) && !_isInClose(upNode)) { if( ! _isInOpen(upNode)) { //in open upNode->setFID(newOpenNode->getFID()); _addIntoOpenNode(upNode); _setStartNode_G_H_Value(upNode, newOpenNode); } else { //_setStartNode_G_H_Value(upNode, newOpenNode); } } } int idownNodeCol = newOpenNode->getCol() + 1; if(idownNodeCol < STARTMAP_COL) { AStartNode *downNode = _getAStartNodeAt(idownNodeCol, newOpenNode->getRow()); if(!_isWater(downNode) && !_isInClose(downNode)) { if( ! _isInOpen(downNode)) { //in open downNode->setFID(newOpenNode->getFID()); _addIntoOpenNode(downNode); _setStartNode_G_H_Value(downNode, newOpenNode); } else { //_setStartNode_G_H_Value(downNode, newOpenNode); } } } } bool AstartMap::_isWater(AStartNode *pStartNode) { int icol = pStartNode->getCol(); int irow = pStartNode->getRow(); if(GameMap[icol][irow] == MAPPATH_WALL) return true; return false; } bool AstartMap::_isInClose(AStartNode *pStartNode) { assert(pStartNode); std::vector<AStartNode *>::iterator it = m_closeNode.begin(); for( ; it != m_closeNode.end(); ++it) { if(*it == pStartNode) { return true; } } return false; } bool AstartMap::_isInOpen(AStartNode *pStartNode) { assert(pStartNode); std::vector<AStartNode *>::iterator it = m_openNode.begin(); for(; it != m_openNode.end(); ++it) { if(*it == pStartNode) { return true; } } return false; } void AstartMap::_deleteBeginNodefromOpenNode(AStartNode *newOpenNode) { if(newOpenNode == 0) return; std::vector<AStartNode *>::iterator it = m_openNode.begin(); for( ; it != m_openNode.end(); ++it) { if(*it == newOpenNode) { m_openNode.erase(it); break; } } } void AstartMap::_setStartNode_G_H_Value(AStartNode *newOpenNode, AStartNode *parentNode) { if(newOpenNode == 0 || parentNode == 0) return ; if(newOpenNode->getCol() == 6 && newOpenNode->getRow() == 3) { int i = 0; } newOpenNode->setG( parentNode->getG() + 10); newOpenNode->setH( ( abs((m_pEndNode->getRow() - newOpenNode->getRow())) + abs((m_pEndNode->getCol() - newOpenNode->getCol())) - 1) * 10); newOpenNode->setF(newOpenNode->getG() + newOpenNode->getH()); } AStartNode *AstartMap::_getMinFstartNode() { _heapSort(m_openNode, m_openNode.size()); int icount = m_openNode.size(); AStartNode *minNode = m_openNode[0]; return minNode; } void AstartMap::_heapRebuild(std::vector<AStartNode *> &rStartNodeArray, int root, int size) { int child = 2 * root + 1; if(child <= size - 1) { int rightChild = child + 1; if(rightChild <= size - 1) if(rStartNodeArray[child]->getF() < rStartNodeArray[rightChild]->getF()) child = rightChild; if(rStartNodeArray[root]->getF() < rStartNodeArray[child]->getF()) { AStartNode *temp = rStartNodeArray[child]; rStartNodeArray[child] = rStartNodeArray[root]; rStartNodeArray[root] = temp; _heapRebuild(rStartNodeArray, child, size); } } } void AstartMap::_heapSort(std::vector<AStartNode *> &rStartNodeArray, int size) { for(int i = size-1; i >= 0; i--){ _heapRebuild(rStartNodeArray,i,size); } int last=size-1; for(int i = 1;i <= size; i++, last--) { AStartNode *temp=rStartNodeArray[0]; rStartNodeArray[0]=rStartNodeArray[last]; rStartNodeArray[last]=temp; _heapRebuild(rStartNodeArray,0,last); } } // bool isNum(int inum) { // if the num in(0-9) return true, or return false if(inum >= 0 && inum <= 9) return true; return false; }
速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体(units)的数量、物体的重要性、组(group)的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是,建立一个启发式函数用于假定通过一个网格空间的最小代价是1,然后建立一个代价函数(cost function)用于测量(scales):
g’(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0,则改进后的代价函数的值总是1。这种情况下,地形代价被完全忽略,A*工作变成简单地判断一个网格可否通过。如果alpha是1,则最初的代价函数将起作用,然后你得到了A*的所有优点。你可以设置alpha的值为0到1的任意值。
你也可以考虑对启发式函数的返回值做选择:绝对最小代价或者期望最小代价。例如,如果你的地图大部分地形是代价为2的草地,其它一些地方是代价为1的道路,那么你可以考虑让启发式函数不考虑道路,而只返回2*距离。
速度和精确度之间的选择并不是全局的。在地图上的某些区域,精确度是重要的,你可以基于此进行动态选择。例如,假设我们可能在某点停止重新计算路径或者改变方向,则在接近当前位置的地方,选择一条好的路径则是更重要的,因此为何要对后续路径的精确度感到厌烦?或者,对于在地图上的一个安全区域,最短路径也许并不十分重要,但是当从一个敌人的村庄逃跑时,安全和速度是最重要的。
在游戏中,路径潜在地花费了许多存储空间,特别是当路径很长并且有很多物体需要寻路时。路径压缩,导航点和beacons通过把多个步骤保存为一个较小数据从而减少了空间需求。Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map.如果路径仍然用了许多存储空间,可以限制路径长度,这就回到了经典的时间-空间折衷法:为了节省空间,信息可以被丢弃,稍后才重新计算它。
Cocos2d-x 3.1.1 学习日志16--A星算法(A*搜寻算法)的学习
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。