Cocos2d-x 3.3TileMap的A*算法实现详解

总结

在Cocos2d-x 3.3中使用TileMap实现A算法时，由于Cocos里的Vector比C++标准库的vector容纳的类型少很多，因此采用标准库的vector。具体地图为320 680像素，瓦片大小是32 32像素。实现A算法的步骤如下：

1. 添加点击事件，获取终点的瓦片坐标并记录。
2. 设定起始坐标，并将其作为【当前点】。
3. 每次对【当前点】的四周进行探索，将可探索的点放入优先队列openList。
4. 把优先队列中F值最小的点作为新的【当前点】，并将其放入closeList。
5. 持续调用探索方法，直至终点坐标被放入openList。

代码

HelloWorldScene.h

#ifndef __HELLOWORLD_SCENE_H__
#define __HELLOWORLD_SCENE_H__

#include "cocos2d.h"
#include <queue>
#include <vector>

USING_NS_CC;

// 定义【当前点】类，包含权值F和坐标点
class pointValue {
public:
pointValue(Point tem, Point dst, int total) {
tempPoint = tem;
FValue = (abs((int)dst.x - (int)tem.x + (int)dst.y - (int)tem.y) + total);
}

// 当前点坐标和F值
Point tempPoint;
int FValue;
};

// 设置优先队列比较函数，F值最小的【当前点】在优先队列的Top
struct Compare {
bool operator()(pointValue a, pointValue b) {
return a.FValue > b.FValue;
}
};

class HelloWorld : public cocos2d::Layer {
public:
static cocos2d::Scene* createScene();
virtual bool init();
CREATE_FUNC(HelloWorld);
void menuCloseCallback(cocos2d::Ref* pSender);

// 二维数组，防止点重复探索，初始化为0，探索过的设为1
int arr[15][10];

// TileMap的层
TMXLayer *layer;

// 待检测坐标列表，优先队列作为OpenList
std::priority_queue<pointValue, std::vector<pointValue>, Compare> p_quene;

// 关闭列表
std::vector<pointValue> closeList;
std::vector<pointValue>::iterator closeListStart;

// 起点瓦片坐标
Point beginPoint;

// 终点瓦片坐标
Point destination;

// 估算一个从起始点到终点的格子数目，每移动一次，则减30
int total;

// 将最终的路径所有点，存放在closeList中
bool aStart();
};

#endif // __HELLOWORLD_SCENE_H__

HelloWorldScene.cpp

#include "HelloWorldScene.h"
USING_NS_CC;

Scene* HelloWorld::createScene() {
auto scene = Scene::create();
auto layer = HelloWorld::create();
scene->addChild(layer);
return scene;
}

bool HelloWorld::init() {
if (!Layer::init()) {
return false;
}

Size visibleSize = Director::getInstance()->getVisibleSize();
Vec2 origin = Director::getInstance()->getVisibleOrigin();

// 载入TileMap地图
auto map = TMXTiledMap::create("map.tmx");
addChild(map);

// 获取TileMap的层
layer = map->getLayer("layer1");

// 确定起点瓦片坐标和初始化二维数组
beginPoint = Point(0, 0);
arr[0][0] = 1;

// 点击事件监听，记录终点瓦片坐标
auto listener = EventListenerTouchOneByOne::create();
listener->onTouchBegan = [this](Touch *t, Event *e) {
// 设置终点瓦片坐标
int dx = (int)(t->getLocation().x) / 32;
int dy = 14 - (int)(t->getLocation().y) / 32;
this->destination = Point(dx, dy);
CCLOG("%d,%d", dx, dy);

// 自己设置起点到终点的最短格子数估值，即G值
total = 1000;

// 寻找最短路径，坐标存放在closeList里面
aStart();
return true;
};
Director::getInstance()->getEventDispatcher()->addEventListenerWithSceneGraphPriority(listener, this);
return true;
}

bool HelloWorld::aStart() {
// 每调用一次aStart相当于移动一步，每移动一步total减30，作为G值
total = total - 30;

if ((int)beginPoint.x == (int)destination.x && (int)beginPoint.y == (int)destination.y) {
return true;
}

// 探索这个点的4周(上，右，下，左)，若存在，则放进优先队列openList中
// 判断上方
if ((int)beginPoint.x >= 0 && ((int)beginPoint.y - 1) >= 0 && (int)beginPoint.x <= 9 && ((int)beginPoint.y - 1) <= 14) {
Sprite *testUp = layer->getTileAt(Vec2((int)beginPoint.x, (int)beginPoint.y - 1));
if (testUp != NULL && (arr[(int)beginPoint.x][(int)beginPoint.y - 1] != 1)) {
CCLOG("up");
// 初始化探索的点，将它放进优先队列openList中，并设置二维数组中的值为1，防止重复探索
auto temp = new pointValue(Point(beginPoint.x, beginPoint.y - 1), destination, total);
p_quene.push(*temp);
arr[(int)beginPoint.x][(int)beginPoint.y - 1] = 1;
}
}

// 判断左方
if (((int)beginPoint.x - 1) >= 0 && (int)beginPoint.y >= 0 && ((int)beginPoint.x - 1) <= 9 && (int)beginPoint.y <= 14) {
Sprite *testLeft = layer->getTileAt(Vec2((int)beginPoint.x - 1, (int)beginPoint.y));
if (testLeft != NULL && (arr[(int)beginPoint.x - 1][(int)beginPoint.y] != 1)) {
CCLOG("left");
// 初始化探索的点，将它放进优先队列openList中，并设置二维数组中的值为1，防止重复探索
auto temp2 = new pointValue(Point(beginPoint.x - 1, beginPoint.y), destination, total);
p_quene.push(*temp2);
arr[(int)beginPoint.x - 1][(int)beginPoint.y] = 1;
}
}

// 判断下方
if ((int)beginPoint.x >= 0 && ((int)beginPoint.y + 1) >= 0 && (int)beginPoint.x <= 9 && ((int)beginPoint.y + 1) <= 14) {
Sprite *testDown = layer->getTileAt(Vec2((int)beginPoint.x, (int)beginPoint.y + 1));
if (testDown != NULL && (arr[(int)beginPoint.x][(int)beginPoint.y + 1] != 1)) {
CCLOG("down");
// 初始化探索的点，将它放进优先队列openList中，并设置二维数组中的值为1，防止重复探索
auto temp3 = new pointValue(Point(beginPoint.x, beginPoint.y + 1), destination, total);
p_quene.push(*temp3);
arr[(int)beginPoint.x][(int)beginPoint.y + 1] = 1;
}
}

// 判断右方
if (((int)beginPoint.x + 1) >= 0 && (int)beginPoint.y >= 0 && ((int)beginPoint.x + 1) <= 9 && (int)beginPoint.y <= 14) {
Sprite *testRight = layer->getTileAt(Vec2((int)beginPoint.x + 1, (int)beginPoint.y));
if (testRight != NULL && (arr[(int)beginPoint.x + 1][(int)beginPoint.y] != 1)) {
CCLOG("right");
// 初始化探索的点，将它放进优先队列openList中，并设置二维数组中的值为1，防止重复探索
auto temp4 = new pointValue(Point(beginPoint.x + 1, beginPoint.y), destination, total);
p_quene.push(*temp4);
arr[(int)beginPoint.x + 1][(int)beginPoint.y] = 1;
}
}

// 重置当前位置
beginPoint.x = p_quene.top().tempPoint.x;
beginPoint.y = p_quene.top().tempPoint.y;
CCLOG("%d,%d", (int)beginPoint.x, (int)beginPoint.y);

// 把F值最小的点，放进closeList中，并从优先队列中pop掉
closeList.push_back(p_quene.top());
p_quene.pop();

// 在路径中添加精灵
auto star = Sprite::create("star.png");
star->setPosition(Point(beginPoint.x * 32 + 10, 480 - beginPoint.y * 32 - 10));
addChild(star);

// 继续递归
return aStart();
}

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
}

效果

原文档未提供具体效果描述，可根据代码运行后查看添加的精灵是否按照A*算法计算的路径进行移动。