#ifndef __HELLOWORLD_SCENE_H__
#define __HELLOWORLD_SCENE_H__

#include "cocos2d.h"
#include "vector"
using namespace std;
USING_NS_CC;
#define MAP_WIDTH 200//要比tmx中的map大
#define MAP_HEIGHT 200
class PathSprite 
{
public:
 PathSprite(CCSprite* sprite)
 {
 m_parent = NULL;
 m_child = NULL;
 m_costToSource = 0;
 m_FValue = 0;
 m_sprite = sprite;
 };
public:
 CCSprite* m_sprite;//包含的瓦片精靈
 PathSprite* m_parent;//父節(jié)點(diǎn)
 PathSprite* m_child;//子節(jié)點(diǎn)
 float m_costToSource;//到起始點(diǎn)的距離
 int m_x;//地圖坐標(biāo)
 int m_y;
 float m_FValue;
};
class PathSearchInfo//尋路類(主要負(fù)責(zé)尋路的參數(shù)和邏輯)
{
public:
 
 static int m_startX;//開始點(diǎn)
 static int m_startY;
 
 static int m_endX;//結(jié)束點(diǎn)
 static int m_endY;
 
 static CCSize m_mapSize;//地圖大小
 static CCSize m_tileSize;//地圖的塊大小
 static vector m_openList;//開放列表(里面存放相鄰節(jié)點(diǎn))
 static PathSprite* m_inspectArray[MAP_WIDTH][MAP_HEIGHT];//全部需要檢測的點(diǎn)
 static vector m_pathList;//路徑列表
 static vector m_haveInspectList;//檢測過的列表

 static float calculateTwoObjDistance(PathSprite* obj1, PathSprite* obj2)//計(jì)算兩個(gè)物體間的距離
 {
 // 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)//把相鄰的節(jié)點(diǎn)放入開放節(jié)點(diǎn)中
 {
 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);//獲得累計(jì)的路程
 G = adjacent->m_costToSource;
 
 //三種算法, 感覺H2不錯(cuò)
 H1 = _x + _y;
 H2 = hypot(_x, _y);
 H3 = max(_x, _y);
 
#if 1 //A*算法 = Dijkstra算法 + 最佳優(yōu)先搜索
 F = G + H2;
#endif
#if 0//Dijkstra算法
 F = G;
#endif
#if 0//最佳優(yōu)先搜索
 F = H2;
#endif
 adjacent->m_FValue = F;
 
 adjacent->m_parent = node;//設(shè)置父節(jié)點(diǎn)
 adjacent->m_sprite->setColor(ccORANGE);//搜尋過的節(jié)點(diǎn)設(shè)為橘色(測試用)
 m_haveInspectList.push_back(adjacent);
 node->m_child = adjacent;//設(shè)置子節(jié)點(diǎn)

 PathSearchInfo::m_inspectArray[adjacent->m_x][adjacent->m_y] = NULL;//把檢測過的點(diǎn)從檢測列表中刪除
 PathSearchInfo::m_openList.push_back(adjacent);//加入開放列表
 }
 }
 static PathSprite* getMinPathFormOpenList()//從開放節(jié)點(diǎn)中獲取F值最小值的點(diǎn)
 {
 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 < _sp->m_FValue)
 {
 _sp = *iter;
 }
 }
 return _sp;
 }
 else
 {
 return NULL;
 }
 
 }
 static PathSprite* getObjFromInspectArray(int x, int y)//根據(jù)橫縱坐標(biāo)從檢測數(shù)組中獲取點(diǎn)
 {
 if (x >=0 && y >=0 && x < m_mapSize.width && y < m_mapSize.height) {
 return m_inspectArray[x][y];
 }
 return NULL;
 }
 static bool removeObjFromOpenList( PathSprite* sprite)//從開放列表中移除對象
 {
 if (!sprite) {
 return false;
 }
 for (vector::iterator iter = m_openList.begin(); iter != m_openList.end(); iter++)
 {
 if (*iter == sprite)
 {
 m_openList.erase(iter);
 return true;
 }
 }
 return false;
 
 } 
};
class HelloWorld : public cocos2d::CCLayer
{
public:
 // Here's a difference. Method 'init' in cocos2d-x returns bool, instead of returning 'id' in cocos2d-iphone
 virtual bool init(); 

 // there's no 'id' in cpp, so we recommend returning the class instance pointer
 static cocos2d::CCScene* scene();
 
 // a selector callback
 void menuCloseCallback(CCObject* pSender);
 
 // implement the "static node()" method manually
 CREATE_FUNC(HelloWorld);
 void onEnter();
 virtual bool ccTouchBegan(CCTouch* touch, CCEvent* event);
 virtual void ccTouchMoved(CCTouch* touch, CCEvent* event);
 virtual void ccTouchEnded(CCTouch* touch, CCEvent* event);
 
 void calculatePath();//計(jì)算路徑
 
 void drawPath();//繪制路徑(測試用)
 
 void clearPath();//清理路徑

 void playerMove();//人物走動(dòng)

 void update(float dt);//跟新大地圖(行走時(shí), 人不動(dòng), 地圖跟著人動(dòng));
 
public:
 CCPoint m_orignPoint;//人物的起始點(diǎn)
 
 PathSprite* m_player;//人物點(diǎn)
 
 int m_playerMoveStep;//人物當(dāng)前的行程的索引
 
};

#endif // __HELLOWORLD_SCENE_H__

#include "HelloWorldScene.h"

USING_NS_CC;
vector PathSearchInfo::m_openList;

PathSprite* PathSearchInfo::m_inspectArray[MAP_WIDTH][MAP_HEIGHT] = {NULL};

vector PathSearchInfo::m_pathList;

vector PathSearchInfo::m_haveInspectList;

CCSize PathSearchInfo::m_mapSize;

CCSize PathSearchInfo::m_tileSize;

int PathSearchInfo::m_startX;

int PathSearchInfo::m_startY;

int PathSearchInfo::m_endX;

int PathSearchInfo::m_endY;

CCScene* HelloWorld::scene()
{
 // 'scene' is an autorelease object
 CCScene *scene = CCScene::create();
 
 // 'layer' is an autorelease object
 HelloWorld *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
void HelloWorld::onEnter()
{
 CCDirector* pDirector = CCDirector::sharedDirector();
 pDirector->getTouchDispatcher()->addTargetedDelegate(this, 0, true);
 CCLayer::onEnter();

}

bool HelloWorld::init()
{
 //////////////////////////////
 // 1. super init first
 if ( !CCLayer::init() )
 {
 return false;
 }
 
 CCSize visibleSize = CCDirector::sharedDirector()->getVisibleSize();
 CCPoint origin = CCDirector::sharedDirector()->getVisibleOrigin();

 /////////////////////////////
 // 2. add a menu item with "X" image, which is clicked to quit the program
 // you may modify it.


 
 CCLabelTTF* pLabel = CCLabelTTF::create("A* + tiledMap", "Arial", 24);
 
 // position the label on the center of the screen
 pLabel->setPosition(ccp(origin.x + visibleSize.width/2,
 origin.y + visibleSize.height - pLabel->getContentSize().height));

 // add the label as a child to this layer
 this->addChild(pLabel, 1);

 this->scheduleUpdate();

 CCTMXTiledMap* map = CCTMXTiledMap::create("gameMap.tmx");
 this->addChild(map);
 map->setPosition(CCPoint());
 CCTMXLayer* _road = map->layerNamed("road");//行走路徑的地圖
 CCSize _mapSize = map->getMapSize();
 for (int j = 0; j < _mapSize.height; j++) {
 for (int i = 0; i < _mapSize.width; i++) {
 CCSprite* _sp = _road->tileAt(CCPoint(i, j));
 if (_sp) {
 PathSprite* _pathSprite = new PathSprite(_sp);
 _pathSprite->m_x = i;
 _pathSprite->m_y = j;
 PathSearchInfo::m_inspectArray[i][j] = _pathSprite;//把地圖中所有的點(diǎn)一一對應(yīng)放入檢測列表中
 }
 }
 }
 PathSearchInfo::m_mapSize = _mapSize;//獲取地圖的尺寸
 PathSearchInfo::m_tileSize = map->getTileSize();//獲取瓦片的尺寸
 
 //設(shè)置起始和終點(diǎn)
 PathSearchInfo::m_startX =30;
 PathSearchInfo::m_startY = 75;

 //創(chuàng)建一個(gè)人物
 m_player = new PathSprite(CCSprite::create("10001.png"));
 m_player->m_sprite->setAnchorPoint(CCPoint(0.5,0));
 this->addChild(m_player->m_sprite);
 
 m_player->m_x = PathSearchInfo::m_startX;//設(shè)置人物的起始的地圖坐標(biāo)
 m_player->m_y = PathSearchInfo::m_startY;
 
 m_orignPoint = PathSearchInfo::m_inspectArray[PathSearchInfo::m_startX][PathSearchInfo::m_startY]->m_sprite->getPosition();
 m_player->m_sprite->setPosition(m_orignPoint);//設(shè)置人物的起始的世界坐標(biāo)

 
 
 return true;
}
void HelloWorld::calculatePath()
{
 
 //得到開始點(diǎn)的節(jié)點(diǎn)
 PathSprite* _startNode = PathSearchInfo::m_inspectArray[PathSearchInfo::m_startX][PathSearchInfo::m_startY];
 //得到結(jié)束點(diǎn)的節(jié)點(diǎn)
 PathSprite* _endNode = PathSearchInfo::m_inspectArray[PathSearchInfo::m_endX][PathSearchInfo::m_endY];
 
 //因?yàn)槭情_始點(diǎn) 把到起始點(diǎn)的距離設(shè)為0, F值也為0
 _startNode->m_costToSource = 0;
 _startNode->m_FValue = 0;
 
 //把已經(jīng)檢測過的點(diǎn)從檢測列表中刪除
 PathSearchInfo::m_inspectArray[PathSearchInfo::m_startX][PathSearchInfo::m_startY] = NULL;
 //把該點(diǎn)放入已經(jīng)檢測過點(diǎn)的列表中
 PathSearchInfo::m_haveInspectList.push_back(_startNode);
 //然后加入開放列表
 PathSearchInfo::m_openList.push_back(_startNode);
 
 PathSprite* _node = NULL;
 while (true)
 {
 //得到離起始點(diǎn)最近的點(diǎn)(如果是第一次執(zhí)行, 得到的是起點(diǎn))
 _node = PathSearchInfo::getMinPathFormOpenList();
 if (!_node)
 {
 //找不到路徑
 break;
 }
 //把計(jì)算過的點(diǎn)從開放列表中刪除
 PathSearchInfo::removeObjFromOpenList( _node);
 int _x = _node->m_x;
 int _y = _node->m_y;
 
 //
 if (_x ==PathSearchInfo::m_endX && _y == PathSearchInfo::m_endY)
 {
 break;
 }
 
 //檢測8個(gè)方向的相鄰節(jié)點(diǎn)是否可以放入開放列表中
 CCLog("%d, %d",_x, _y);
 PathSprite* _adjacent = PathSearchInfo::getObjFromInspectArray( _x + 1, _y + 1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x +1, _y);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x +1, _y-1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x , _y -1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x -1, _y - 1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x -1, _y);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x -1, _y+1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 _adjacent = PathSearchInfo::getObjFromInspectArray( _x , _y+1);
 PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent, _endNode);
 
 }
 
 while (_node)
 {
 //把路徑點(diǎn)加入到路徑列表中
 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)->m_sprite->setColor(ccGREEN);
 }
 
}
CCRect getBoundingBox(float x, float y, float width, float height)
{
 return CCRect(x - width/2, y - height/2, width, height);
}
bool HelloWorld::ccTouchBegan(CCTouch* touch, CCEvent* event)
{

 //清除之前的路徑
 clearPath();
 
 auto nodePosition = convertToNodeSpace( touch->getLocation() );
 CCLog("%f, %f", nodePosition.x, nodePosition.y);
// for (int i = 0; i < PathSearchInfo::m_inspectList.size(); i++)
// {
// PathSprite* _sp = PathSearchInfo::m_inspectList[i];
// 
// CCRect _rect = getBoundingBox( _sp->m_sprite->getPositionX(), _sp->m_sprite->getPositionY(), _sp->m_sprite->getContentSize().width, _sp->m_sprite->getContentSize().height);
// 
// if (_rect.containsPoint(nodePosition))
// {
 PathSprite* _sp = PathSearchInfo::m_inspectArray[(int)(nodePosition.x/PathSearchInfo::m_tileSize.width)][(int)(PathSearchInfo::m_mapSize.height - nodePosition.y/PathSearchInfo::m_tileSize.height)];
 if (_sp) {
 CCLog("%f, %f", _sp->m_sprite->getPositionX(), _sp->m_sprite->getPositionY());
 //獲取觸摸點(diǎn), 設(shè)置為終點(diǎn)
 PathSearchInfo::m_endX = _sp->m_x;
 PathSearchInfo::m_endY = _sp->m_y;
 //計(jì)算路徑
 calculatePath();
 //繪制路徑
 drawPath( );
 //移動(dòng)物體
 playerMove();
 }
 
 
// }
// 
// }

 return true;
}

void HelloWorld::ccTouchMoved(CCTouch* touch, CCEvent* event)
{

}



void HelloWorld::ccTouchEnded(CCTouch* touch, CCEvent* event)
{

}

void HelloWorld::menuCloseCallback(CCObject* pSender)
{
#if (CC_TARGET_PLATFORM == CC_PLATFORM_WINRT) || (CC_TARGET_PLATFORM == CC_PLATFORM_WP8)
	CCMessageBox("You pressed the close button. Windows Store Apps do not implement a close button.","Alert");
#else
 CCDirector::sharedDirector()->end();
#if (CC_TARGET_PLATFORM == CC_PLATFORM_IOS)
 exit(0);
#endif
#endif
}

void HelloWorld::clearPath()
{
 for (vector::iterator iter = PathSearchInfo::m_haveInspectList.begin(); iter != PathSearchInfo::m_haveInspectList.end(); iter++)
 {
 (*iter)->m_sprite->setColor(ccWHITE);
 (*iter)->m_costToSource = 0;
 (*iter)->m_FValue = 0;
 (*iter)->m_parent = NULL;
 (*iter)->m_child = NULL;
 
 PathSearchInfo::m_inspectArray[(*iter)->m_x][(*iter)->m_y] = (*iter);
 }
 
 //把移除了障礙物的地圖放入檢測列表中
 //PathSearchInfo::m_inspectList = PathSearchInfo::m_mapList;
 PathSearchInfo::m_openList.clear();
 PathSearchInfo::m_pathList.clear();
 PathSearchInfo::m_haveInspectList.clear();
 PathSearchInfo::m_startX = m_player->m_x;
 PathSearchInfo::m_startY = m_player->m_y;
 m_player->m_sprite->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;
 
 //根據(jù)路徑列表移動(dòng)人物
 m_player->m_sprite->runAction(CCSequence::create(CCMoveTo::create(1/24.0, PathSearchInfo::m_pathList[m_playerMoveStep]->m_sprite->getPosition()), CCCallFunc::create(this, SEL_CallFunc(&HelloWorld::playerMove)) , NULL));
 
}
void HelloWorld::update(float dt)
{
 this->setPosition(m_orignPoint - m_player->m_sprite->getPosition());
}