EN中文
开发者社区 > 程序

Cocos2d-x 寻路算法解析（一）： 距离优先

发表于2015-12-15
评论4 2.2k浏览
寻路这块在游戏中一直很重要，花了点时间研究了下这个问题，主要参考的是《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

  4. #include <vector>

  6. using namespace std;

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

  34. };

  36. #endif

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

  1. #ifndef _CELL_H
  2. #define _CELL_H

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

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

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

  31.     }
  32.     inline int getWeight()const{ return _weight;}
  33. private:
  34.     int _weight;              //default is 1, 4 means this cell is impassable.
  35.                                //distance have relationship with weight
  36. };

  38. #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;

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

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

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

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

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

  53.         }
  54.     }
  55. }
  56. startPathFinding(compareTwoCellsByDistance,_playerX,_playerY,_goalX,_goalY);//demo

　　4.寻路动态图：


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

　　5.项目下载：

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

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

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

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

标签：

游戏开发寻路算法ListQueueSTL名作