cocos2dx A*算法

首页 > 代码库 > cocos2dx A*算法

**cocos2dx A*算法**

2024-07-28 02:25:19 236人阅读

头文件和源文件复制到项目中就能用了! have fun

使用cocos2dx 3.2 原理都一样

淡蓝色的点是地图

深蓝色的点是障碍物

绿色的点是路径

暗绿色的点是搜寻过的点

红色的点是按路径行走的点

dijkstra算法会发现路径最短,但寻找过的路径比较多(计算速度慢)

最佳优先搜索算法会发现寻找过的路径少了(计算速度提高了),但走了许多弯路

A星算法结合了上面2种算法即寻找到了最短路径, 搜寻过的路径也比较少

[cpp] view plaincopy

#ifndef __HELLOWORLD_SCENE_H__
#define __HELLOWORLD_SCENE_H__
#include "cocos2d.h"
#include "vector"
using namespace std;
USING_NS_CC;
class PathSprite : public cocos2d::Sprite//继承Sprite类, 因为要在里面加些其他变量
{
PathSprite():Sprite()
{
m_parent = NULL;
m_child = NULL;
m_costToSource = 0;
m_FValue = 0;
};
public:
static PathSprite* create(const char* ch)
{
PathSprite *pRet = new PathSprite();
if (pRet )
{
pRet->initWithFile(ch);
pRet->autorelease();
return pRet;
}
else
{
delete pRet;
pRet = NULL;
return NULL;
}
}
PathSprite* m_parent;//父节点
PathSprite* m_child;//子节点
float m_costToSource;//到起始点的距离
int m_x;//地图坐标
int m_y;
float m_FValue;
};
class PathSearchInfo//寻路类(主要负责寻路的参数和逻辑)
{
public:
static int m_startX;//开始点
static int m_startY;
static int m_endX;//结束点
static int m_endY;
static vector<PathSprite*> m_openList;//开放列表(里面存放相邻节点)
static vector<PathSprite*> m_inspectList;//检测列表(里面存放除了障碍物的节点)
static vector<PathSprite*> m_pathList;//路径列表
static void barrierTest( vector<PathSprite*> &pathList,int x, int y)//模拟障碍物
{
PathSprite* _z = getObjByPointOfMapCoord(pathList, x, y);
if (_z)
{
_z->setColor(ccColor3B::MAGENTA);
removeObjFromList(pathList, _z);
}
}
static float calculateTwoObjDistance(PathSprite* obj1, PathSprite* obj2)//计算两个物体间的距离
{
// float _offsetX = obj1->m_x - obj2->m_x;
// float _offsetY = obj1->m_y - obj2->m_y;
// return sqrt( _offsetX * _offsetX + _offsetY * _offsetY);
float _x = abs(obj2->m_x - obj1->m_x);
float _y = abs(obj2->m_y - obj1->m_y);
return _x + _y;
}
static void inspectTheAdjacentNodes(PathSprite* node, PathSprite* adjacent, PathSprite* endNode)//把相邻的节点放入开放节点中
{
if (adjacent)
{
float _x = abs(endNode->m_x - adjacent->m_x);
float _y = abs(endNode->m_y - adjacent->m_y);
float F , G, H1, H2, H3;
adjacent->m_costToSource = node->m_costToSource + calculateTwoObjDistance(node, adjacent);//获得累计的路程
G = adjacent->m_costToSource;
//三种算法, 感觉H2不错
H1 = _x + _y;
H2 = hypot(_x, _y);
H3 = max(_x, _y);
#if 1 //A*算法 = Dijkstra算法 + 最佳优先搜索
F = G + H2;
#endif
#if 0//Dijkstra算法
F = G;
#endif
#if 0//最佳优先搜索
F = H2;
#endif
adjacent->m_FValue = F;
adjacent->m_parent = node;//设置父节点
adjacent->setColor(Color3B::ORANGE);//搜寻过的节点设为橘色
node->m_child = adjacent;//设置子节点
PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList, adjacent);//把检测过的点从检测列表中删除
PathSearchInfo::m_openList.push_back(adjacent);//加入开放列表
}
}
static PathSprite* getMinPathFormOpenList()//从开放节点中获取路径最小值
{
if (m_openList.size()>0) {
PathSprite* _sp =* m_openList.begin();
for (vector<PathSprite*>::iterator iter = m_openList.begin(); iter != m_openList.end(); iter++)
{
if ((*iter)->m_FValue < _sp->m_FValue)
{
_sp = *iter;
}
}
return _sp;
}
else
{
return NULL;
}
}
static PathSprite* getObjByPointOfMapCoord( vector<PathSprite*> &spriteVector, int x, int y)//根据点获取对象
{
for (int i = 0; i < spriteVector.size(); i++)
{
if (spriteVector[i]->m_x == x && spriteVector[i]->m_y == y)
{
return spriteVector[i];
}
}
return NULL;
}
static bool removeObjFromList(vector<PathSprite*> &spriteVector, PathSprite* sprite)//从容器中移除对象
{
for (vector<PathSprite*>::iterator iter = spriteVector.begin(); iter != spriteVector.end(); iter++)
{
if (*iter == sprite)
{
spriteVector.erase(iter);
return true;
}
}
return false;
}
};
class HelloWorld : public cocos2d::Layer
{
public:
// there‘s no ‘id‘ in cpp, so we recommend returning the class instance pointer
static cocos2d::Scene* createScene();
// Here‘s a difference. Method ‘init‘ in cocos2d-x returns bool, instead of returning ‘id‘ in cocos2d-iphone
virtual bool init();
// a selector callback
void menuCloseCallback(cocos2d::Ref* pSender);
// implement the "static create()" method manually
CREATE_FUNC(HelloWorld);
bool onTouchBegan(Touch* touch, Event* event);
void onTouchMoved(Touch* touch, Event* event);
void onTouchEnded(Touch* touch, Event* event);
void calculatePath();//计算路径
void drawPath();//绘制路径
vector<PathSprite*> m_mapList;//地图
void clearPath();//清理路径
PathSprite* m_player;//人物用于演示行走
int m_playerMoveStep;//人物当前的行程
void playerMove();//人物走动
};
#endif // __HELLOWORLD_SCENE_H__

[cpp] view plaincopy

#include "HelloWorldScene.h"
vector<PathSprite*> PathSearchInfo::m_openList;
vector<PathSprite*> PathSearchInfo::m_inspectList;
vector<PathSprite*> PathSearchInfo::m_pathList;
int PathSearchInfo::m_startX;
int PathSearchInfo::m_startY;
int PathSearchInfo::m_endX;
int PathSearchInfo::m_endY;
Scene* HelloWorld::createScene()
{
// ‘scene‘ is an autorelease object
auto scene = Scene::create();
// ‘layer‘ is an autorelease object
auto layer = HelloWorld::create();
// add layer as a child to scene
scene->addChild(layer);
// return the scene
return scene;
}
// on "init" you need to initialize your instance
bool HelloWorld::init()
{
//////////////////////////////
// 1. super init first
if ( !Layer::init() )
{
return false;
}
Size visibleSize = Director::getInstance()->getVisibleSize();
Vec2 origin = Director::getInstance()->getVisibleOrigin();
Size winSize = Director::getInstance()->getWinSize();
/////////////////////////////
// 2. add a menu item with "X" image, which is clicked to quit the program
// you may modify it.
// add a "close" icon to exit the progress. it‘s an autorelease object
auto listener = EventListenerTouchOneByOne::create();
listener->setSwallowTouches(true);
listener->onTouchBegan = CC_CALLBACK_2(HelloWorld::onTouchBegan, this);
listener->onTouchMoved = CC_CALLBACK_2(HelloWorld::onTouchMoved, this);
listener->onTouchEnded = CC_CALLBACK_2(HelloWorld::onTouchEnded, this);
_eventDispatcher->addEventListenerWithSceneGraphPriority(listener, this);
//模拟一张地图左上角为(0,0) 主要是模拟tiledmap 每块的宽度为1
int _width = 25;
int _heigth = 15;
for (int i = 0; i < _heigth; i++)
{
for (int j = 0; j < _width; j++)
{
PathSprite* _sp = PathSprite::create("CloseNormal.png");
_sp->m_x = j;
_sp->m_y = i;
Size _size = _sp->getContentSize();
_sp->setPosition(CCPoint(j * _size.width + 100, - i * _size.height + 600));
m_mapList.push_back(_sp);
this->addChild(_sp);
}
}
//设置障碍物
// for (int i = 0; i < _heigth*_width/2; i++)
// {
//
// int _x = CCRANDOM_0_1()*_width;
// int _y = CCRANDOM_0_1()*_heigth;
// if (_x ==0 && _y == 0) {
// continue;
// }
// PathSearchInfo::barrierTest(m_mapList,_x,_y);
// }
for (int i = 0; i < 10; i++) {
PathSearchInfo::barrierTest(m_mapList,5+i,10);
PathSearchInfo::barrierTest(m_mapList,15,i+1);
}
//PathSprite::getObjByPointOfMapCoord(m_inspectList, 2, 5)->removeFromParent();
//设置起始和终点
PathSearchInfo::m_startX =0;
PathSearchInfo::m_startY = 0;
PathSearchInfo::m_endX = 4;
PathSearchInfo::m_endY = 9;
m_player = PathSprite::create("CloseSelected1.png");
m_player->setColor(Color3B::RED);
this->addChild(m_player);
m_player->m_x = PathSearchInfo::m_startX;
m_player->m_y = PathSearchInfo::m_startY;
m_player->setPosition(PathSearchInfo::getObjByPointOfMapCoord(m_mapList, PathSearchInfo::m_startX, PathSearchInfo::m_startY)->getPosition());
return true;
}
void HelloWorld::calculatePath()
{
//得到开始点的节点
PathSprite* _sp = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, PathSearchInfo::m_startX, PathSearchInfo::m_startY);
//得到开始点的节点
PathSprite* _endNode = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, PathSearchInfo::m_endX, PathSearchInfo::m_endY);
//因为是开始点把到起始点的距离设为0
_sp->m_costToSource = 0;
_sp->m_FValue = 0;
//把已经检测过的点从检测列表中删除
PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList, _sp);
//然后加入开放列表
PathSearchInfo::m_openList.push_back(_sp);
PathSprite* _node = NULL;
while (true)
{
//得到离起始点最近的点
_node = PathSearchInfo::getMinPathFormOpenList();
if (!_node)
{
//找不到路径
break;
}
//把计算过的点从开放列表中删除
PathSearchInfo::removeObjFromList(PathSearchInfo::m_openList, _node);
int _x = _node->m_x;
int _y = _node->m_y;
//
if (_x ==PathSearchInfo::m_endX && _y == PathSearchInfo::m_endY)
{
break;
}
//检测8个方向的相邻节点是否可以放入开放列表中
PathSprite* _adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x + 1, _y + 1);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x +1, _y);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x +1, _y-1);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x , _y -1);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y - 1);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y+1);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x , _y+1);
PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
}
while (_node)
{
//PathSprite* _sp = node;
PathSearchInfo::m_pathList.insert(PathSearchInfo::m_pathList.begin(), _node);
_node = _node->m_parent;
}
}
void HelloWorld::drawPath( )
{
for (vector<PathSprite*>::iterator iter = PathSearchInfo::m_pathList.begin(); iter != PathSearchInfo::m_pathList.end(); iter++)
{
(*iter)->setColor(ccColor3B::GREEN);
}
}
bool HelloWorld::onTouchBegan(Touch* touch, Event* event)
{
//清除之前的路径
clearPath();
auto nodePosition = convertToNodeSpace( touch->getLocation() );
log("%f, %f", nodePosition.x, nodePosition.y);
for (int i = 0; i < PathSearchInfo::m_inspectList.size(); i++)
{
PathSprite* _sp = PathSearchInfo::m_inspectList[i];
if (_sp->getBoundingBox().containsPoint(nodePosition))
{
//获取触摸点, 设置为终点
PathSearchInfo::m_endX = _sp->m_x;
PathSearchInfo::m_endY = _sp->m_y;
//计算路径
calculatePath();
//绘制路径
drawPath( );
playerMove();
}
}
return true;
}
void HelloWorld::onTouchMoved(Touch* touch, Event* event)
{
// If it weren‘t for the TouchDispatcher, you would need to keep a reference
// to the touch from touchBegan and check that the current touch is the same
// as that one.
// Actually, it would be even more complicated since in the Cocos dispatcher
// you get Sets instead of 1 UITouch, so you‘d need to loop through the set
// in each touchXXX method.
}
void HelloWorld::onTouchEnded(Touch* touch, Event* event)
{
}
void HelloWorld::menuCloseCallback(Ref* pSender)
{
#if (CC_TARGET_PLATFORM == CC_PLATFORM_WP8) || (CC_TARGET_PLATFORM == CC_PLATFORM_WINRT)
MessageBox("You pressed the close button. Windows Store Apps do not implement a close button.","Alert");
return;
#endif
Director::getInstance()->end();
#if (CC_TARGET_PLATFORM == CC_PLATFORM_IOS)
exit(0);
#endif
}
void HelloWorld::clearPath()
{
for (vector<PathSprite*>::iterator iter = m_mapList.begin(); iter != m_mapList.end(); iter++)
{
(*iter)->setColor(ccColor3B::WHITE);
(*iter)->m_costToSource = 0;
(*iter)->m_FValue = 0;
(*iter)->m_parent = NULL;
(*iter)->m_child = NULL;
}
//把移除了障碍物的地图放入检测列表中
PathSearchInfo::m_inspectList = m_mapList;
PathSearchInfo::m_openList.clear();
PathSearchInfo::m_pathList.clear();
PathSearchInfo::m_startX = m_player->m_x;
PathSearchInfo::m_startY = m_player->m_y;
m_player->stopAllActions();
m_playerMoveStep = 0;
}
void HelloWorld::playerMove()
{
m_playerMoveStep++;
if (m_playerMoveStep >= PathSearchInfo::m_pathList.size()) {
return;
}
m_player->m_x = PathSearchInfo::m_pathList[m_playerMoveStep]->m_x;
m_player->m_y = PathSearchInfo::m_pathList[m_playerMoveStep]->m_y;
m_player->runAction(Sequence::create(MoveTo::create(0.2, PathSearchInfo::m_pathList[m_playerMoveStep]->getPosition()), CallFunc::create(this, SEL_CallFunc(&HelloWorld::playerMove)) , NULL));
}

cocos2dx A*算法

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > cocos2dx A*算法

看完仍有疑问？有类似问题直接问程序猿

**cocos2dx A*算法**