cocos2dx下的A星算法

这是我依据这篇博文http://hi.baidu.com/wsapyoemdfacmqr/item/bdfb5c0a74c904d01ef0466d。来在cocos2dx上编写。这是终于的效果图：

红色的地方是执行轨迹，黑色是禁止区域，接下来是代码，请结合那篇博文观看：

首先创建地板类，必需要有x和y，还有依据那篇博文的h和g。这是h文件里的代码：

#include "cocos2d.h"

typedef enum _FloorState
{
    FloorGround,
    FloorRiver
} FloorState;

class Floor : public cocos2d::LayerColor
{
public:
    Floor();
    ~Floor(){}

    static int at(int x, int y);
    static Floor * create(const cocos2d::Color4B& color);
    bool initWithColor(const cocos2d::Color4B& color);

    int getF();

private:
    CC_SYNTHESIZE(int, _x, X);
    CC_SYNTHESIZE(int, _y, Y);

    CC_SYNTHESIZE(int, _h, H);
    CC_SYNTHESIZE(int, _g, G);

    CC_SYNTHESIZE(FloorState, _landForm, LandForm);

    CC_SYNTHESIZE(Floor *, _lastFloor, LastFloor);
};

基本上没有什么难度，另外，那个静态方法at使用了从数组中高速获取地板。

然后是cpp文件：

#include "Floor.h"

USING_NS_CC;

Floor::Floor()
{
    _x = 0;
    _y = 0;

    _h = -1;
    _g = -1;

    _lastFloor = NULL;
}

int Floor::at(int x, int y)
{
    return x + 28 * y;
}

Floor *Floor::create(const cocos2d::Color4B &color)
{
    Floor *_floor = new Floor();
    if ( _floor && _floor -> initWithColor( color ) )
    {
        _floor -> autorelease();
        return _floor;
    }

    delete _floor;
    _floor = NULL;
    return NULL;
}

bool Floor::initWithColor(const cocos2d::Color4B &color)
{
    if ( LayerColor::initWithColor(color, 39, 39) )
    {
        return true;
    }

    return false;
}

int Floor::getF()
{
    return _h + _g;
}

然后在执行的Layer中：

void MainScene::createGround()
{
    for (int y = 0; y < 18; y++)
    {
        for (int x = 0; x < 28; x++)
        {
            auto _floor = Floor::create( Color4B(255, 255, 255, 255) );
            _floor -> setPosition(x * (_floor -> getContentSize().width + 1), y * (_floor -> getContentSize().height + 1));
            _floor -> setX(x);
            _floor -> setY(y);
            _floor -> setLandForm( FloorGround );
            this -> addChild( _floor );

            if ( (x == 15 && y < 7) || (x == 3 && y < 10) || (y == 12 && x < 20) || (x == 5 && y > 8) || (x == 13 && y > 1) )
            {
                _floor -> setColor( Color3B(0, 0, 0) );
                _floor -> setLandForm( FloorRiver );
            }
            ground.pushBack( _floor );
        }
    }
}

当中，这种方法：_floor -> setLandForm( FloorRiver )使用来制造禁止区域

然后加入起点和终点：

    end = Floor::create( Color4B(0, 255, 255, 10) );
    end -> setPosition( (ground.at( Floor::at(24, 14) )) -> getPosition() );
    end -> setX(24);
    end -> setY(14);
    this -> addChild( end );

    origin = Floor::create( Color4B(255, 255, 0, 255) );
    origin -> setPosition( (ground.at( Floor::at(0, 0) )) -> getPosition() );
    origin -> setX(0);
    origin -> setY(0);
    origin -> setH( fabs((end -> getX() - origin -> getX())) + fabs( end -> getY() - origin -> getY() ) );
    origin -> setG(0);
    this -> addChild( origin );
    open.pushBack( origin );

在这些完毕后，就是须要使用A*算法来计算出路径了

首先从open数组中寻找F最小的地板；之后。将上下左右的地板做个推断，是否增加数组中。这部分放在一个死循环中，当增加的地板正是终点时，能够结束：

while (1)
    {
        Vector< Floor * >::iterator index = open.begin();
        Vector< Floor * >::iterator minF = index;
        for (; index != open.end(); index++)
        {
            if ( (*index) -> getF() < (*minF) -> getF() )
            {
                minF = index;
            }
        }

        Floor *_origin = (*minF);

        handleFloor(_origin, _origin -> getX(), _origin -> getY() - 1);
        handleFloor(_origin, _origin -> getX(), _origin -> getY() + 1);
        handleFloor(_origin, _origin -> getX() - 1, _origin -> getY());
        handleFloor(_origin, _origin -> getX() + 1, _origin -> getY());

        open.eraseObject( _origin );
        close.pushBack( _origin );
        _origin -> setColor( Color3B(0, 255, 0) );

        Floor *getEnd = open.at( open.size() - 1 );
        if ( getEnd -> getX() == end -> getX() && getEnd -> getY() == end -> getY() )
        {
            CCLOG("ENDG");
            return;
        }
    }

handleFloor函数是用来推断该地板是否可以增加数组中

void MainScene::handleFloor(Floor *_floor, int x, int y)
{
    if ( x < 0 || y < 0 )
    {
        return;
    }
    Floor *handle = ground.at( Floor::at(x, y) );
    handle -> setX(x);
    handle -> setY(y);
    handle -> setH( fabs((end -> getX() - handle -> getX())) + fabs( end -> getY() - handle -> getY() ) );
    handle -> setG( fabs((origin -> getX() - handle -> getX())) + fabs( origin -> getY() - handle -> getY() ) );
    JUDGE( handle, _floor );
}

#define JUDGE(__FLOOR__, __LAST__)
if ( !open.contains(__FLOOR__) && !close.contains(__FLOOR__) && __FLOOR__ -> getLandForm() != FloorRiver )
{
open.pushBack( __FLOOR__ );
__FLOOR__ -> setColor( Color3B(100, 100, 100) );
__FLOOR__ -> setLastFloor( __LAST__ );
}

之后，就是取出open数组终的最后一块地板，并能够获取这块地板的上一块地板。并将其颜色改变

    Floor *index = open.at( open.size() - 1 );

    while ( index -> getLastFloor() != NULL )
    {
        index -> setColor( Color3B(255, 0, 0) );
        index = index -> getLastFloor();
    }

在这里下载