Cocos2d-x 寻路算法之三 A Star

Cocos2d-x 寻路算法之三 A Star

1.A Star 寻路算法介绍：

看过之前的两篇文章：​​《Cocos2d-x 寻路算法之二 离目的地的距离优先》​​​，​​《Cocos2d-x 寻路算法之一 距离优先》​​的读者知道，这两种寻路算法都有问题，前一个搜索太广了，资源浪费；后一个还不够聪明，有时候会找不到最佳路线。为什么要先介绍这两种不佳的算法呢？因为A Star 寻路算法就是前面两者的结合。同时考虑离起点的距离和离终点的距离。

Figure 1

究竟是C1还是C2这个格子是最佳路线点呢？因为我们这次离起点的距离和离终点的距离都考虑了，所以C1的价值是1.0 + 1.41 + 4.12 总共 6.53的长度。而C2的价值是 2.0 + 6.32 总共 8.32的长度。显然C1更佳。如果按照我们第一个寻路算法，只考虑离起点距离的话，C2还短些呢！但C2离终点远啊。

2.代码实现

float distanceBetweenTwoCells(float c1X,float c1Y, float c2X, float c2Y){ return sqrt(pow(c2X - c1X,2) + pow(c2Y - c1Y,2));}bool comparebyDistanceBetweenStartAndGoal(Cell *c1, Cell *c2){ float distanceOfC1AndGoal = c1->getDistance() + distanceBetweenTwoCells((float)c1->getX(),(float)c1->getY(),(float)g_goalX,(float) g_goalY); float distanceOfC2AndGoal = c2->getDistance() + distanceBetweenTwoCells((float)c2->getX(),(float)c2->getY(),(float)g_goalX,(float) g_goalY); if(distanceOfC1AndGoal <= distanceOfC2AndGoal){ return false; }else{ return true; }}

只要加上这个方法就行了，把这个方法作为heap的比较条件。整个startPathFinding都不需要改，这里再次给出startPathFinding代码：

typedef bool (*compareTwoCells)(Cell *c1, Cell *c2); void HelloWorld::startPathFinding(compareTwoCells compareMethod, int startX,int startY,int goalX,int goalY){ Cell *startCell = _m_Map.Get(startX, startY); vector vecCells; vecCells.push_back(startCell); make_heap(vecCells.begin(),vecCells.end(),compareMethod); startCell->setMarked(true); Cell *nowProcessCell; while(vecCells.size() != 0){ pop_heap(vecCells.begin(),vecCells.end(),compareMethod); nowProcessCell = vecCells.back(); vecCells.pop_back(); if(nowProcessCell->getX() == _goalX && nowProcessCell->getY() == _goalY){//the goal is reach return; } for(int i = 0; i < 8; ++i){ //check eight direction int indexX = nowProcessCell->getX() + DIRECTION[i][0]; int indexY = nowProcessCell->getY() + DIRECTION[i][1]; if(indexX >= 0 && indexX < xLineCount && indexY >= 0 && indexY < yLineCount && _m_Map.Get(indexX,indexY)->getPassable() == true){//check is a OK cell or not Cell *cell = _m_Map.Get(indexX,indexY); float beforeDistance = DISTANCE[i] * cell->getWeight() + _m_Map.Get(nowProcessCell->getX(), nowProcessCell->getY())->getDistance();//calculate the distance if(cell->getMarked() == false){ cell->setMarked(true); cell->setLastX(nowProcessCell->getX()); cell->setLastY(nowProcessCell->getY()); cell->setDistance(beforeDistance); vecCells.push_back(cell);//only push the unmarked cell into the vector push_heap(vecCells.begin(),vecCells.end(),compareMethod); }else{// if find a lower distance, update it if(beforeDistance < cell->getDistance()){ cell->setDistance(beforeDistance); cell->setLastX(nowProcessCell->getX()); cell->setLastY(nowProcessCell->getY()); make_heap(vecCells.begin(),vecCells.end(),compareMethod);//distance change,so make heap again } } } } } } startPathFinding(comparebyDistanceBetweenStartAndGoal,_playerX,_playerY,_goalX,_goalY);//A star path finding demo

函数指针太酷了！

3.三种寻路算法的图片比较

3.1只考虑距离起点的距离，采用Breadth-First

特点：可以找到目标，但搜索Cell太多。

3.2 只考虑离目标距离

特点：搜索Cell大多情况会相对少些，但不一定能找到最短路线。

3.3 A Star ，同时考虑到起点和终点的距离

特点：能找到最短路线，搜索的Cell比第一种要少，看最后的搜索方式，也有第二种搜索的智慧。

4.A Star动态gif演示图

不知道为什么我对GIF这么热衷。

5. Cocos2d-x A Star 源码下载：

(请用7z解压，开发工具vs2010)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。