研究了几个小时，看了网上的一些资料，感觉都写得不好，可能是我太笨了，我现在来讲解一下在cocos2dx如何利用A*算法自动寻找目标。我是根据上下左右来进行搜索的，通过不停地去比
研究了几个小时，看了网上的一些资料，感觉都写得不好，可能是我太笨了，我现在来讲解一下在cocos2dx如何利用A*算法自动寻找目标。
我是根据上下左右来进行搜索的，通过不停地去比较F值来取得取得最小代价得到路径：
首先：在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;
}
代码还需要优化，不美观，我只是大概的写了个例子。