cocos2dx 搜寻路径 之 dijkstra

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

使用cocos2dx 3.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_distance = 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_distance;//到起始点的距离
	int m_x;//地图坐标
	int m_y;
};

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 void  barrierTest(int x, int y)//模拟障碍物
	{
		PathSprite* _z = getObjByPointOfMapCoord(m_inspectList, x, y);
		if (_z)
		{
			_z->setColor(ccColor3B::YELLOW);
			removeObjFromList(PathSearchInfo::m_inspectList, _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);
	}
	static void inspectTheAdjacentNodes(PathSprite* node, PathSprite* adjacent)//把相邻的节点放入开放节点中
	{
		if (adjacent)
		{
			adjacent->m_distance = node->m_distance + PathSearchInfo::calculateTwoObjDistance(node, adjacent);//获得累计的路程
			adjacent->m_parent = node;//设置父节点
			node->m_child = adjacent;//设置子节点
			PathSearchInfo::removeObjFromList(PathSearchInfo::m_inspectList, adjacent);//把检测过的点从检测列表中删除
			PathSearchInfo::m_openList.push_back(adjacent);//加入开放列表
		}
	}
	static PathSprite* getMinPathFormOpenList()//从开放节点中获取路径最小值
	{
		PathSprite* _sp =* m_openList.begin();
		for (vector<PathSprite*>::iterator iter = m_openList.begin(); iter !=  m_openList.end(); iter++)
		{
			if ((*iter)->m_distance < _sp->m_distance)
			{
				_sp = *iter;
			}
		}
		return _sp;
	}
	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);
};

#endif // __HELLOWORLD_SCENE_H__

#include "HelloWorldScene.h"

vector<PathSprite*> PathSearchInfo::m_openList;

vector<PathSprite*> PathSearchInfo::m_inspectList;

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


    
	//模拟一张地图 左上角 为(0,0) 主要是模拟tiledmap  每块的宽度为1  
	int length = 10;
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length; 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));
			PathSearchInfo::m_inspectList.push_back(_sp);
			this->addChild(_sp);
		}
	}
	
	//设置障碍物
	PathSearchInfo::barrierTest(0,3);
	PathSearchInfo::barrierTest(1,3);
	PathSearchInfo::barrierTest(2,3);
	PathSearchInfo::barrierTest(3,3);

	PathSearchInfo::barrierTest(3,5);
	PathSearchInfo::barrierTest(4,5);
	PathSearchInfo::barrierTest(5,5);
	PathSearchInfo::barrierTest(6,5);

	PathSearchInfo::barrierTest(0,7);
	PathSearchInfo::barrierTest(1,7);
	PathSearchInfo::barrierTest(2,7);
	PathSearchInfo::barrierTest(3,7);
	//PathSprite::getObjByPointOfMapCoord(m_inspectList, 2, 5)->removeFromParent();

	//设置起始和终点
	PathSearchInfo::m_startX = 0;
	PathSearchInfo::m_startY = 1;

	PathSearchInfo::m_endX = 4;
	PathSearchInfo::m_endY = 9;

	//得到开始点的节点
	PathSprite* _sp = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, PathSearchInfo::m_startX, PathSearchInfo::m_startY);
	//因为是开始点 把到起始点的距离设为0
	_sp->m_distance = 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);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x +1, _y);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x +1, _y-1);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x , _y -1);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y - 1);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x -1, _y+1);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);

		_adjacent = PathSearchInfo::getObjByPointOfMapCoord(PathSearchInfo::m_inspectList, _x , _y+1);
		PathSearchInfo::inspectTheAdjacentNodes(_node, _adjacent);
		
	}


	int i = 0;
	while (_node)
	{
		PathSprite* _sp = _node;
		_node = _node->m_parent;
		_sp->setColor(ccColor3B::MAGENTA);
	}
    return true;
}


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
}

cocos2dx 搜寻路径 之 dijkstra

原文：http://blog.csdn.net/w18767104183/article/details/39650409