Cocos2d-x 寻路算法解析(一): 距离优先

发表于2015-12-15
评论4 688浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594
寻路这块在游戏中一直很重要,花了点时间研究了下这个问题,主要参考的是《Data Structures For Game Programmers》,其他的算法用普通Console演示就行了,寻路算法还是用一个界面比较好,最近在学Cocos2d-x,就用它了。 

  1.效果图

  用到Cocos2d-x中的基本画线段,画矩形就行了,还有简单的sprite拖动。这demo建了一个线条类,继承CCNode,重写draw方法就行了。在draw方法中简单地调用ccDrawColor4F函数来设置颜色,ccDrawLine来画线条,非常容易,cocos2d-x这些函数封装了opengles中的原始函数,使用非常简单。sprite拖动可以参考这篇文章《cocos2d-x Touch 事件应用的一个例子 》


  1.小人和红色X都可以用鼠标移动,移到上面的地图上,表示寻路起点和终点。

  2.Distance, Simple Heuristic, Complex Heuristic, A Star分别是4种寻路算法,点击程序就会开始演示寻路过程。

  3.地图的格子点击会加深颜色,总共4个等级,白,灰,深灰,黑,表示该格子的通过难度,白色是1,灰是2,深灰是3,黑色是不可通过区域。

  4.”+++”表示加快演示速度,”—”表示降低演示速度。

  2. Breadth – First Search算法

  顾名思义,有点像呼吸,一层层地扩展开来,这个时候队列(Queue),stl中的deque就派上用场了。deque不懂可以参考这篇文章《C++ Queue Example Rearranging RailRoad Cars》


  起点在中心,会先访问它的第一个外圈,再是第二个。现在我觉得它更像一颗石头扔在水面上的效果。

  下面是伪代码:

  1. BreadthFirst( Node )
  2. Queue.Enqueue( Node )Mark( Node )
  3. While( Queue.IsNotEmpty )
  4. Process( Queue.Front )
  5. For Each Child of Queue.Front
  6. if NotMarked( Child )
  7. Queue.Enqueue( Child )
  8. Mark( Child )
  9. end if
  10. end For
  11. Queue.Dequeue()
  12. End While
  13. End Function

  遍历一个树或者图都可以用这个方法。在我们这里遇到了点麻烦,因为我们都知道斜角的距离是根号2的倍数,要比上下左右方向远,因为寻路,很重要的因素的距离的长短。我们需要考虑距离这个因素了。

  3.Distance – First Search


  起点还在中心,这张图显示了每一格到中心的估算距离。如果依靠距离优先的算法,下图是寻路次序:


  所以我们定义了一个方向数组:

  1. const int DIRECTION[8][2]={
  2. {0,1},  //north
  3. {1,0},  //east
  4. {0,-1},  //south
  5. {-1,0},  //west
  6. {1,1},  //northeast
  7. {1,-1},  //southeast
  8. {-1,-1},  //southwest
  9. {-1,1}  //northwest
  10. };

  这样通过一个for循环,就可以访问它周围一圈的格子了,而且是按照距离优先了,上下左右优先,斜角次些。

  因为是地图,我们这里简单定义了一个2维数组,非常简单用一个vector就可以模拟了,假定读者熟悉stl中的vector和C++中的template,不熟悉可以参考这篇文章《STL Vector》和《C++ 基础之 “模版函数”,”类模版”》

  1. #ifndef ARRAY2D_H
  2. #define ARRAY2D_H

  3. #include <vector>

  4. using namespace std;

  5. template <class Datatype>
  6. class Array2D{
  7. public:
  8.     Array2D(int p_width, int p_height):m_array(p_width * p_height),
  9.         m_width(p_width),m_height(p_height){
  10.     }
  11.     Datatype* Get(int p_x, int p_y)const{
  12.         return m_array[p_y * m_width + p_x];
  13.     }
  14.     void Set(int p_x, int p_y, Datatype* data){
  15.         m_array[p_y * m_width + p_x] = data;
  16.     }
  17.     int Size() const{
  18.         return m_width * m_height;
  19.     }
  20.     int Width() const{
  21.         return m_width;
  22.     }
  23.     int Height()const{
  24.         return m_height;
  25.     }
  26. private:
  27.     vector<Datatype*> m_array;
  28.     int m_width;
  29.     int m_height;

  30. };

  31. #endif

  我们还定义了一个Cell类表示每一个格子:它有很多属性,像位置,最短距离到这个Cell的Cell的位置,是否已经处理过,到起点的距离,是否可以通过,还有就是这个Cell的权重,表示经过难度。我们这里使用了一个从cocos2d-x中拷来的宏,这样get和set方法就不用手写了。

  1. #ifndef _CELL_H
  2. #define _CELL_H

  3. #define SYNTHESIZE(varType, varName, funName)
  4. protected: varType varName;
  5. public: virtual varType get##funName(void) const { return varName; }
  6. public: virtual void set##funName(varType var){ varName = var; }

  7. class Cell{
  8. public:
  9.     Cell():_marked(false),_distance(0),_lastX(-1),_lastY(-1),
  10.         _x(-1),_y(-1),_passable(true),_weight(1),_drawProgress(false){
  11.     }

  12.     SYNTHESIZE(int, _x, X);                       //start at left bottom
  13.     SYNTHESIZE(int, _y, Y);                       //start at left bottom
  14.     SYNTHESIZE(int, _lastX, LastX);               //store the nearest cell's location related this cell
  15.     SYNTHESIZE(int, _lastY, LastY);               //store the nearest cell's location related this cell
  16.     SYNTHESIZE(bool, _marked, Marked);            //whether this cell process or not
  17.     SYNTHESIZE(float, _distance, Distance);       //distance between this cell and start
  18.     SYNTHESIZE(bool, _passable, Passable);        //whether this call can pass
  19.     SYNTHESIZE(int, _drawProgress, DrawProgress); //just for draw the path finding progress
  20.     inline void setWeight(int weight){
  21.         if(weight > 4){
  22.             _weight = 1;
  23.         }else{
  24.             _weight = weight;
  25.             setPassable(weight == 4 ? false : true);
  26.         }

  27.     }
  28.     inline int getWeight()const{ return _weight;}
  29. private:
  30.     int _weight;              //default is 1, 4 means this cell is impassable.
  31.                                //distance have relationship with weight
  32. };

  33. #endif

  核心算法如下:事先需要了解的知识:因为我们需要按照最短距离优先寻路,所以一个优先队列就需要了,这里简单地使用了heap,对heap不了解的可以看下这篇文章《HeapSort(堆排序 C++) 》,下面还用上了C++中的函数指针,可以参考这篇文章《C++ 函数指针 函数名作为参数 》,为什么要用函数指针呢?看完整个寻路算法系列你就知道了。

  语言解释:

  先把起点Cell加入到heap中,对这个Cell的周围8个Cell进行处理,主要是更新他们到起点的距离和记录最短距离到这个Cell的Cell的位置。每次找到一个新的Cell,

  1.如果还没处理过,标上处理过标志,更新他们到起点的距离和记录最短距离到这个Cell的Cell的位置,再把这个Cell加入到堆中,重新形成一个堆,这样开始很容易得到离起点最近的点。

  2.如果处理过,看下新的距离是不是比老的距离短,如果短,更新上面的提到的两点。

  不断处理,直到访问了所有的点或者找到终点了。

  下面是代码:整个寻路算法的核心代码。

  1. typedef bool (*compareTwoCells)(Cell *c1, Cell *c2);
  2. bool compareTwoCellsByDistance(Cell *c1, Cell *c2){
  3.     if(c1->getDistance() <= c2->getDistance()){
  4.         return false;
  5.     }else{
  6.         return true;
  7.     }
  8. }
  9. void HelloWorld::startPathFinding(compareTwoCells compareMethod, int startX,int startY,int goalX,int goalY){
  10.     Cell *startCell = _m_Map.Get(startX, startY);
  11.     vector<Cell*> vecCells;
  12.     vecCells.push_back(startCell);
  13.     make_heap(vecCells.begin(),vecCells.end(),compareMethod);
  14.     startCell->setMarked(true);
  15.     Cell *nowProcessCell;

  16.     while(vecCells.size() != 0){
  17.         pop_heap(vecCells.begin(),vecCells.end(),compareMethod);
  18.         nowProcessCell = vecCells.back();
  19.         vecCells.pop_back();

  20.         if(nowProcessCell->getX() == _goalX && nowProcessCell->getY() == _goalY){//the goal is reach
  21.             return;
  22.         }

  23.         for(int i = 0; i < 8; ++i){ //check eight direction

  24.             int indexX = nowProcessCell->getX() + DIRECTION[i][0];
  25.             int indexY = nowProcessCell->getY() + DIRECTION[i][1];

  26.             if(indexX >= 0 && indexX < xLineCount && indexY >= 0 && indexY < yLineCount
  27.                 && _m_Map.Get(indexX,indexY)->getPassable() == true){//check is a OK cell or not
  28.                     Cell *cell = _m_Map.Get(indexX,indexY);
  29.                     float beforeDistance = DISTANCE[i] * cell->getWeight() + _m_Map.Get(nowProcessCell->getX(),
  30.                         nowProcessCell->getY())->getDistance();//calculate the distance
  31.                     if(cell->getMarked() == false){ 
  32.                         cell->setMarked(true);
  33.                         cell->setLastX(nowProcessCell->getX());
  34.                         cell->setLastY(nowProcessCell->getY());
  35.                         cell->setDistance(beforeDistance);
  36.                         vecCells.push_back(cell);//only push the unmarked cell into the vector
  37.                         push_heap(vecCells.begin(),vecCells.end(),compareMethod);
  38.                     }else{// if find a lower distance, update it 
  39.                         if(beforeDistance < cell->getDistance()){
  40.                             cell->setDistance(beforeDistance);
  41.                             cell->setLastX(nowProcessCell->getX());
  42.                             cell->setLastY(nowProcessCell->getY());
  43.                             make_heap(vecCells.begin(),vecCells.end(),compareMethod);//distance change,so make heap again
  44.                         }
  45.                     }
  46.             }

  47.         }
  48.     }
  49. }
  50. startPathFinding(compareTwoCellsByDistance,_playerX,_playerY,_goalX,_goalY);//demo

  4.寻路动态图:


  我只是简单地在起点和终点间加入了一个不可通过的墙,通过查看蓝色的区域会发现这个算法很慢。目标在右边,这个算法上下左右都找,虽然找到了也太浪费资源了吧?下篇我们来看看其他的寻路算法。

  5.项目下载:

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

  http://www.waitingfy.com/?attachment_id=828

  http://www.waitingfy.com/?p=820

原文链接

著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台