cocos2dx A*算法

头文件和源文件复制到项目中就能用了! have fun 使用cocos2dx 3.2 原理都一样 淡蓝色的点是地图 深蓝色的点是障碍物 绿色的点是路径 暗绿色的点是搜寻过的点 红色的点是按路径行走的点 dijkstra算法 会发现路径最短,但寻找过的路径比较多(计算速度慢) 最佳优

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

使用cocos2dx 3.2 原理都一样

淡蓝色的点是地图

深蓝色的点是障碍物

绿色的点是路径

暗绿色的点是搜寻过的点

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

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

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

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

#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 m_openList;//开放列表(里面存放相邻节点)
    static vector m_inspectList;//检测列表(里面存放除了障碍物的节点)
    static vector m_pathList;//路径列表
    static void  barrierTest( vector &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::iterator iter = m_openList.begin(); iter !=  m_openList.end(); iter++)
            {
                if ((*iter)->m_FValue m_FValue)
                {
                    _sp = *iter;
                }
            }
            return _sp;
        }
        else
        {
            return NULL;
        }
        
    }
    static PathSprite* getObjByPointOfMapCoord( vector &spriteVector,  int x, int y)//根据点获取对象
    {
        for (int i = 0; i m_x == x && spriteVector[i]->m_y == y)
            {
                return spriteVector[i];
            }
        }
        return NULL;
    }
    static bool removeObjFromList(vector &spriteVector, PathSprite* sprite)//从容器中移除对象
    {
        for (vector::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 m_mapList;//地图
    
    void clearPath();//清理路径
    
    PathSprite* m_player;//人物 用于演示行走
    int m_playerMoveStep;//人物当前的行程
    void playerMove();//人物走动
};

#endif // __HELLOWORLD_SCENE_H__

#include "HelloWorldScene.h"

vector PathSearchInfo::m_openList;

vector PathSearchInfo::m_inspectList;

vector 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 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 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::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 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::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));
    
}