cocos2d-x的A*寻路

时间:2023-03-08 16:55:45
cocos2d-x的A*寻路

如果你还不熟悉A*寻路,请先看下这篇文章http://blog.csdn.net/dssdss123/article/details/11494065

一、先介绍几个函数和结构:

1、virtual void draw()

这个函数跟与MFC上单文档里的OnDraw函数很像,这里只是少了dc,这个函数会一直被调用,无需刷新,也就是说,你无需像在MFC上一样调用Invalidate或者InvalidateRect

2、virtual void ccTouchBegan(CCTouch* pTouch, CCEvent* pEvent)

这个函数是下响应触摸的,当你点击屏幕时,就会进到这个函数。要使这个函数有效,你需要在init中调用
setTouchEnabled(true);    // 允许该层响应触摸
CCDirector::sharedDirector()->getTouchDispatcher()->addTargetedDelegate(this, 0, false);    // 注册单点触摸

在这个例子中,我们不需要多点触摸

3、ccColor4F结构

这个结构在ccDrawSolidRect函数中将会使用到,ccDrawSolidRect是画某种颜色的矩形,对应在MFC中,我们使用的是FillSolidRect。ccColor4F是RGBA的结构,RGB是三颜色,红绿蓝,最后一个alpha值,他表示这个颜色的透明度。为1是完全不透明,0时则完全透明。

二、实现

1、去掉coco自带的乱七八糟的显示

1)去掉帧频显示

在函数bool AppDelegate::applicationDidFinishLaunching()中

// turn on display FPS
//pDirector->setDisplayStats(true);

将pDirector->setDisplayStats(true),注释掉

2)去掉menu,Hello World文字标签

在函数void HelloWorld::init()中

// Add the menu to HelloWorld layer as a child layer.
//this->addChild(pMenu, 1);

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

将menu和label注释掉

3)替换背景图,并置于最底层

// 3. Add add a splash screen, show the cocos2d splash image.
CCSprite* pSprite = CCSprite::create("map.jpg");    // 将原先的HelloWorld.png,替换为自己的图片,这里我换成map.jpg
CC_BREAK_IF(! pSprite);

2、初始化地图

声明结构表示格子掩码等一些信息,我们的例子中,只需掩码,所以结构如下:

    struct ST_GRID
{
ST_GRID() { gf = GRID_FLAG_DEFAULT; }
GRID_FLAG gf;
};
typedef vector<ST_GRID*> VEC_GRID;
VEC_GRID m_vecGrid; // 保存地图产生的所有格子

初始化地图的格子掩码,如下:

void HelloWorld::InitMap()
{
// 初始化格子掩码
 srand((unsigned int)time(NULL));
for (int i = 0; i < GetRow() * GetCol(); i++)
{
int nRandFlag = ((int)(CCRANDOM_0_1() * 10)) % 4 == 0 ? GRID_FLAG_OBSTACLE : GRID_FLAG_DEFAULT; // 十分之四的概率产生障碍
ST_GRID* pGrid = new ST_GRID;
if (!pGrid)
{
return ;
}
pGrid->gf = (GRID_FLAG)nRandFlag;
m_vecGrid.push_back(pGrid);
}
}

3、寻路

定义一个结构,用于寻路过程中,记录每个格子的信息

    struct NODE
{
NODE() {nIndex = 0; nG = 0; pParent = NULL;}
int nIndex;
int nG;
NODE* pParent;
};
vector<NODE*> m_vecPath; // 寻路的路径

下面开始寻路

void HelloWorld::FindPath()
{
vector<NODE*> vecClose; // close表
vector<NODE*> vecOpen; // open表
if (m_nStartIndex == -1 || m_nEndIndex == -1)
{
return ;
}
m_vecPath.clear(); // 这里,我们并没有delete,但却不会内存泄漏,因为cocos2d-x使用了跟java一样的技术 -- 内存回收机制,自动处理垃圾 // 先添加开始点
NODE* pNode = new NODE;
pNode->nIndex = m_nStartIndex;
vecClose.push_back(pNode); int nStep = 0;
while(true)
{
if (nStep++ >= 200) // 最多寻200格
{
break;
}
NODE* pNextNode = vecClose[vecClose.size() - 1]; // 取下一个路径
if (!pNextNode)
{
break;
}
if (pNextNode->nIndex == m_nEndIndex) // 找到终点,就不再找了
{
break;
} for (int i = 0; i < 8; i++)
{
int nIndex = GetIndexByDir(pNextNode->nIndex, i); // 根据方向取索引
if (-1 == nIndex)
{
continue;
}
if (m_vecGrid[nIndex]->gf == GRID_FLAG_OBSTACLE) // 障碍
{
continue;
}
if (InTable(nIndex, vecClose) != NULL) // 在close表里
{
continue;
} NODE* pNode = InTable(nIndex, vecOpen); // 在open表里,比较G值,取G值更小的为新路径
if (pNode)
{
int nNewG = pNextNode->nG + GetGByIndex(pNextNode->nIndex, pNode->nIndex);
if (pNode->nG > nNewG)
{
pNode->nG = nNewG;
pNode->pParent = pNextNode; // 改变节点的父节点
}
continue;
} // 新搜索到的格子,添加到开放列表
pNode = new NODE;
pNode->nIndex = nIndex;
pNode->nG = pNextNode->nG + GetGByIndex(pNextNode->nIndex, pNode->nIndex);
pNode->pParent = pNextNode;
vecOpen.push_back(pNode);
} // 找下一个路径,open表里F值最小的就是了
int nMinF = 0xFFFFFF;
pNextNode = NULL;
int nNextNodeIndex = 0;
for (int i = 0; i < (int)vecOpen.size(); i++)
{
NODE* pNode = vecOpen[i];
if (!pNode)
{
continue;
}
int nH = GetHByIndex(pNode->nIndex); // 计算该点与终点的H值,即路径长度
int nF = nH + pNode->nG; // F = H + G
if (nF < nMinF)
{
nMinF = nF;
pNextNode = pNode;
nNextNodeIndex = i;
}
}
// 找到F值最小的,放入close表,并从open表里删除
 if (nNextNodeIndex >= 0 && nNextNodeIndex < (int)vecOpen.size())
{
vecClose.push_back(pNextNode);
vecOpen.erase(vecOpen.begin() + nNextNodeIndex);
}
} // 寻路结束,找最优路径
pNode = vecClose[vecClose.size() - 1];
while (pNode)
{
m_vecPath.push_back(pNode);
pNode = pNode->pParent;
}
}

4、展示到界面上

void HelloWorld::draw()
{
// 画背景表格
CCSize size = CCDirector::sharedDirector()->getWinSize();
for (int i = 0; i < GetRow(); i++)
{
ccDrawLine(ccp(0, i * GRID_SIDELEN), ccp(size.width, i * GRID_SIDELEN));
}
for (int i = 0; i < GetCol(); i++)
{
ccDrawLine(ccp(i * GRID_SIDELEN, 0), ccp(i * GRID_SIDELEN, size.height));
} // 画特殊格子颜色
// 寻路得到的路径
for (int i = 0; i < (int)m_vecPath.size(); i++)
{
CCPoint ptObstacleLT;
CCPoint ptObstacleRD;
GetRectPointByIndex(m_vecPath[i]->nIndex, ptObstacleLT, ptObstacleRD);
ccColor4F clrObstacle = {0, 1, 1, 0};
ccDrawSolidRect(ptObstacleLT, ptObstacleRD, clrObstacle);
} // 开始点
CCPoint ptStartLT;
CCPoint ptStartRD;
GetRectPointByIndex(m_nStartIndex, ptStartLT, ptStartRD);
ccColor4F clrStart = {1, 0, 0, 1};
ccDrawSolidRect(ptStartLT, ptStartRD, clrStart); // 结束点
CCPoint ptEndLT;
CCPoint ptEndRD;
GetRectPointByIndex(m_nEndIndex, ptEndLT, ptEndRD);
ccColor4F clrEnd = {0, 1, 0, 1};
ccDrawSolidRect(ptEndLT, ptEndRD, clrEnd); // 障碍
for (int i = 0; i < (int)m_vecGrid.size(); i++)
{
if (m_vecGrid[i]->gf == GRID_FLAG_OBSTACLE)
{
CCPoint ptObstacleLT;
CCPoint ptObstacleRD;
GetRectPointByIndex(i, ptObstacleLT, ptObstacleRD);
ccColor4F clrObstacle = {0, 0, 1, 1};
ccDrawSolidRect(ptObstacleLT, ptObstacleRD, clrObstacle);
}
}
}

这里,我只介绍几个比较重要的函数,其他的就不赘述了,资源已上传到CSDN,但还没显示出来,等显示出来了,再把链接发到此处,有疑问的童鞋留言哈

。。。。。。。。

啊,我还是直接上源码吧

#ifndef __HELLOWORLD_SCENE_H__
#define __HELLOWORLD_SCENE_H__ #include "cocos2d.h"
#include "Box2D/Box2D.h"
#include "SimpleAudioEngine.h"
USING_NS_CC; enum STEP
{
STEP_DEFAULT = 0,
STEP_STARTPOINT = 1,
STEP_ENDPOINT = 2,
}; enum GRID_FLAG
{
GRID_FLAG_DEFAULT = 0, // 默认可通过
GRID_FLAG_OBSTACLE = 1, // 障碍
};
const int GRID_SIDELEN = 20; // 不能为0
//////////////////////////////////////////////////////////////////////////
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 recommand to return the exactly class pointer
static cocos2d::CCScene* scene(); // a selector callback
void menuCloseCallback(CCObject* pSender); // implement the "static node()" method manually
CREATE_FUNC(HelloWorld); public:
virtual void draw();
virtual bool ccTouchBegan(CCTouch* pTouch, CCEvent* pEvent); private:
void InitMap(); private:
int GetRow();
int GetCol();
int GetIndexByPoint(CCPoint pt);
void GetRectPointByIndex(int nIndex, CCPoint &ptLT, CCPoint &ptRD); private:
int m_nStartIndex;
int m_nEndIndex; struct ST_GRID
{
ST_GRID() { gf = GRID_FLAG_DEFAULT; }
GRID_FLAG gf;
};
typedef vector<ST_GRID*> VEC_GRID;
VEC_GRID m_vecGrid; struct NODE
{
NODE() {nIndex = 0; nG = 0; pParent = NULL;}
int nIndex;
int nG;
NODE* pParent;
};
vector<NODE*> m_vecPath; // 寻路的路径 public:
void FindPath(); private:
int GetIndexByDir(int nIndex, int nDir);
int GetGByIndex(int nStartIndex, int nEndIndex);
int GetHByIndex(int nIndex);
NODE *InTable(int nIndex, vector<NODE*> &vecTbl); private:
int m_nStep;
}; #endif // __HELLOWORLD_SCENE_H__
#include "HelloWorldScene.h"

using namespace cocos2d;

CCScene* HelloWorld::scene()
{
CCScene * scene = NULL;
do
{
// 'scene' is an autorelease object
scene = CCScene::create();
CC_BREAK_IF(! scene); // 'layer' is an autorelease object
HelloWorld *layer = HelloWorld::create();
CC_BREAK_IF(! layer); // add layer as a child to scene
scene->addChild(layer);
} while (0); // return the scene
return scene;
} // on "init" you need to initialize your instance
bool HelloWorld::init()
{
bool bRet = false;
do
{
//////////////////////////////////////////////////////////////////////////
// super init first
////////////////////////////////////////////////////////////////////////// CC_BREAK_IF(! CCLayer::init()); //////////////////////////////////////////////////////////////////////////
// add your codes below...
////////////////////////////////////////////////////////////////////////// // 1. Add a menu item with "X" image, which is clicked to quit the program. // Create a "close" menu item with close icon, it's an auto release object.
CCMenuItemImage *pCloseItem = CCMenuItemImage::create(
"CloseNormal.png",
"CloseSelected.png",
this,
menu_selector(HelloWorld::menuCloseCallback));
CC_BREAK_IF(! pCloseItem); // Place the menu item bottom-right conner.
pCloseItem->setPosition(ccp(CCDirector::sharedDirector()->getWinSize().width - 20, 20)); // Create a menu with the "close" menu item, it's an auto release object.
CCMenu* pMenu = CCMenu::create(pCloseItem, NULL);
pMenu->setPosition(CCPointZero);
CC_BREAK_IF(! pMenu); // Add the menu to HelloWorld layer as a child layer.
//this->addChild(pMenu, 1); // 2. Add a label shows "Hello World". // Create a label and initialize with string "Hello World".
CCLabelTTF* pLabel = CCLabelTTF::create("Hello World", "Arial", 24);
CC_BREAK_IF(! pLabel); // Get window size and place the label upper.
CCSize size = CCDirector::sharedDirector()->getWinSize();
pLabel->setPosition(ccp(size.width / 2, size.height - 50)); // Add the label to HelloWorld layer as a child layer.
//this->addChild(pLabel, 1); // 3. Add add a splash screen, show the cocos2d splash image.
CCSprite* pSprite = CCSprite::create("map.jpg");
CC_BREAK_IF(! pSprite); // Place the sprite on the center of the screen
pSprite->setPosition(ccp(size.width/2, size.height/2)); // Add the sprite to HelloWorld layer as a child layer.
this->addChild(pSprite, -1); setTouchEnabled(true);
CCDirector::sharedDirector()->getTouchDispatcher()->addTargetedDelegate(this,0,false); m_nStep = STEP_STARTPOINT;
m_nStartIndex = -1;
m_nEndIndex = -1;
InitMap(); bRet = true;
} while (0); return bRet;
} void HelloWorld::menuCloseCallback(CCObject* pSender)
{
// "close" menu item clicked
CCDirector::sharedDirector()->end();
} //////////////////////////////////////////////////////////////////////////
void HelloWorld::InitMap()
{
srand((unsigned int)time(NULL));
for (int i = 0; i < GetRow() * GetCol(); i++)
{
int nRandFlag = ((int)(CCRANDOM_0_1() * 10)) % 4 == 0 ? GRID_FLAG_OBSTACLE : GRID_FLAG_DEFAULT;
ST_GRID* pGrid = new ST_GRID;
if (!pGrid)
{
return ;
}
pGrid->gf = (GRID_FLAG)nRandFlag;
m_vecGrid.push_back(pGrid);
}
} //////////////////////////////////////////////////////////////////////////
void HelloWorld::FindPath()
{
vector<NODE*> vecClose;
vector<NODE*> vecOpen;
if (m_nStartIndex == -1 || m_nEndIndex == -1)
{
return ;
}
m_vecPath.clear(); // 先添加开始点
NODE* pNode = new NODE;
pNode->nIndex = m_nStartIndex;
vecClose.push_back(pNode); int nStep = 0;
while(true)
{
if (nStep++ >= 200)
{
break;
}
NODE* pNextNode = vecClose[vecClose.size() - 1];
if (!pNextNode)
{
break;
}
if (pNextNode->nIndex == m_nEndIndex)
{
break;
} for (int i = 0; i < 8; i++)
{
int nIndex = GetIndexByDir(pNextNode->nIndex, i);
if (-1 == nIndex)
{
continue;
}
if (m_vecGrid[nIndex]->gf == GRID_FLAG_OBSTACLE) // 障碍
{
continue;
}
if (InTable(nIndex, vecClose) != NULL) // 在close表里
{
continue;
} NODE* pNode = InTable(nIndex, vecOpen); // 在open表里
if (pNode)
{
int nNewG = pNextNode->nG + GetGByIndex(pNextNode->nIndex, pNode->nIndex);
if (pNode->nG > nNewG)
{
pNode->nG = nNewG;
pNode->pParent = pNextNode;
}
continue;
} // 新搜索到的格子
pNode = new NODE;
pNode->nIndex = nIndex;
pNode->nG = pNextNode->nG + GetGByIndex(pNextNode->nIndex, pNode->nIndex);
pNode->pParent = pNextNode;
vecOpen.push_back(pNode);
} int nMinF = 0xFFFFFF;
pNextNode = NULL;
int nNextNodeIndex = 0;
for (int i = 0; i < (int)vecOpen.size(); i++)
{
NODE* pNode = vecOpen[i];
if (!pNode)
{
continue;
}
int nH = GetHByIndex(pNode->nIndex);
int nF = nH + pNode->nG;
if (nF < nMinF)
{
nMinF = nF;
pNextNode = pNode;
nNextNodeIndex = i;
}
}
if (nNextNodeIndex >= 0 && nNextNodeIndex < (int)vecOpen.size())
{
vecClose.push_back(pNextNode);
vecOpen.erase(vecOpen.begin() + nNextNodeIndex);
}
} // 寻路结束,找最优路径
pNode = vecClose[vecClose.size() - 1];
while (pNode)
{
m_vecPath.push_back(pNode);
pNode = pNode->pParent;
}
} //////////////////////////////////////////////////////////////////////////
int HelloWorld::GetIndexByDir(int nIndex, int nDir)
{
if (nIndex < 0 || nIndex >= (int)m_vecGrid.size())
{
return -1;
} int nRow = nIndex / GetCol();
int nCol = nIndex % GetCol(); switch(nDir)
{
case 0: // 上
nRow += 1;
break;
case 1: // 右上
nRow += 1;
nCol +=1;
break;
case 2: // 右
nCol += 1;
break;
case 3: // 右下
nRow -= 1;
nCol += 1;
break;
case 4: // 下
nRow -= 1;
break;
case 5: // 左下
nRow -= 1;
nCol -= 1;
break;
case 6: // 左
nCol -= 1;
break;
case 7: // 左上
nRow += 1;
nCol -= 1;
break;
default:
break;
}
if (nRow < 0 || nRow >= GetRow()
|| nCol < 0 || nCol >= GetCol())
{
return -1;
}
return nRow * GetCol() + nCol;
} //////////////////////////////////////////////////////////////////////////
int HelloWorld::GetGByIndex(int nStartIndex, int nEndIndex)
{
int nStartRow = nStartIndex / GetCol();
int nStartCol = nStartIndex % GetCol(); int nEndRow = nEndIndex / GetCol();
int nEndCol = nEndIndex % GetCol(); if (nStartRow == nEndRow || nStartCol == nEndCol)
{
return 10;
}
return 14;
} //////////////////////////////////////////////////////////////////////////
int HelloWorld::GetHByIndex(int nIndex)
{
int nRow = nIndex / GetCol();
int nCol = nIndex % GetCol(); int nEndRow = m_nEndIndex / GetCol();
int nEndCol = m_nEndIndex % GetCol(); return (abs(nEndRow - nRow) + abs(nEndCol - nCol))*10;
} //////////////////////////////////////////////////////////////////////////
HelloWorld::NODE *HelloWorld::InTable(int nIndex, vector<NODE*> &vecTbl)
{
for (int i = 0; i < (int)vecTbl.size(); i++)
{
if (nIndex == vecTbl[i]->nIndex)
{
return vecTbl[i];
}
}
return NULL;
} //////////////////////////////////////////////////////////////////////////
int HelloWorld::GetRow()
{
CCSize size = CCDirector::sharedDirector()->getWinSize();
return size.height / GRID_SIDELEN;
} //////////////////////////////////////////////////////////////////////////
int HelloWorld::GetCol()
{
CCSize size = CCDirector::sharedDirector()->getWinSize();
return size.width / GRID_SIDELEN;
} //////////////////////////////////////////////////////////////////////////
int HelloWorld::GetIndexByPoint(CCPoint pt)
{
pt.x = pt.x > (int)pt.x ? pt.x + 1 : pt.x;
pt.y = pt.y > (int)pt.y ? pt.y + 1 : pt.y;
return (int)pt.y / GRID_SIDELEN * GetCol() + (int)pt.x / GRID_SIDELEN;
} //////////////////////////////////////////////////////////////////////////
void HelloWorld::draw()
{
// 画背景表格
CCSize size = CCDirector::sharedDirector()->getWinSize();
for (int i = 0; i < GetRow(); i++)
{
ccDrawLine(ccp(0, i * GRID_SIDELEN), ccp(size.width, i * GRID_SIDELEN));
}
for (int i = 0; i < GetCol(); i++)
{
ccDrawLine(ccp(i * GRID_SIDELEN, 0), ccp(i * GRID_SIDELEN, size.height));
} // 画特殊格子颜色
// 寻路得到的路径
for (int i = 0; i < (int)m_vecPath.size(); i++)
{
CCPoint ptObstacleLT;
CCPoint ptObstacleRD;
GetRectPointByIndex(m_vecPath[i]->nIndex, ptObstacleLT, ptObstacleRD);
ccColor4F clrObstacle = {0, 1, 1, 1};
ccDrawSolidRect(ptObstacleLT, ptObstacleRD, clrObstacle);
} // 开始点
CCPoint ptStartLT;
CCPoint ptStartRD;
GetRectPointByIndex(m_nStartIndex, ptStartLT, ptStartRD);
ccColor4F clrStart = {1, 0, 0, 1};
ccDrawSolidRect(ptStartLT, ptStartRD, clrStart); // 结束点
CCPoint ptEndLT;
CCPoint ptEndRD;
GetRectPointByIndex(m_nEndIndex, ptEndLT, ptEndRD);
ccColor4F clrEnd = {0, 1, 0, 1};
ccDrawSolidRect(ptEndLT, ptEndRD, clrEnd); // 障碍
for (int i = 0; i < (int)m_vecGrid.size(); i++)
{
if (m_vecGrid[i]->gf == GRID_FLAG_OBSTACLE)
{
CCPoint ptObstacleLT;
CCPoint ptObstacleRD;
GetRectPointByIndex(i, ptObstacleLT, ptObstacleRD);
ccColor4F clrObstacle = {0, 0, 1, 1};
ccDrawSolidRect(ptObstacleLT, ptObstacleRD, clrObstacle);
}
}
} //////////////////////////////////////////////////////////////////////////
void HelloWorld::GetRectPointByIndex(int nIndex, CCPoint &ptLT, CCPoint &ptRD)
{
ptLT.x = nIndex % GetCol() * GRID_SIDELEN;
ptLT.y = nIndex / GetCol() * GRID_SIDELEN;
ptRD.x = ptLT.x + GRID_SIDELEN;
ptRD.y = ptLT.y + GRID_SIDELEN;
} //////////////////////////////////////////////////////////////////////////
bool HelloWorld::ccTouchBegan(CCTouch *pTouch, CCEvent *pEvent)
{
if (!pTouch)
{
return false;
} int nIndex = GetIndexByPoint(pTouch->getLocation());
if (m_vecGrid[nIndex]->gf == GRID_FLAG_OBSTACLE)
{
return false;
} if (STEP_STARTPOINT == m_nStep)
{
m_nStartIndex = nIndex;
m_nStep = STEP_ENDPOINT;
}
else if (STEP_ENDPOINT == m_nStep)
{
m_nEndIndex = nIndex;
m_nStep = STEP_STARTPOINT;
FindPath();
}
return true;
}

哎,想来想去,还是直接上源码比较直截了当。。。。。寻路效果如下,红色是起点,绿色是终点,蓝色是障碍物,浅蓝色是最终寻路路径:

cocos2d-x的A*寻路

cocos2d-x的A*寻路

cocos2d-x的A*寻路

cocos2d-x的A*寻路