一篇关于自动寻径和图、邻接表的学习和启发

以后的游戏中可能会用到人物的自动寻径，在网上看到一个非常不错的博文，特学习了一下，并转了过来为以后留着。。。

再次感谢 Siliphen的分享，本文转载自 http://blog.csdn.net/stevenkylelee/article/details/38408253

本文乃Siliphen原创，转载请注明出处：http://blog.csdn.net/stevenkylelee

　　本文的实现使用的环境是：Cocos2d-x 3.2，VS2013

　　本文，我们最终实现的地图行走效果如下2图：

　　下面是2张屏幕录制的gif动画图，有点大，看不到的话，耐心等待一下，或者刷新页面试试。

1.什么是地图行走

　　很多游戏会有一个“世界”的概念。玩家在这个世界中行走，到达不同的地方去执行的任务，打怪或者是触发剧情等。下图是《锁链战记》的世界地图的截图。

　　不同游戏的世界地图行走表现不同，以锁链战记为例，对于打过的关卡，玩家角色是直接瞬移过去的。对与未打过的关卡，有一个玩家角色行走过去的动画。另一些游戏的地图行走则是到达任何地方都有玩家角色的行走动画。我个人比较青睐于后者。《锁链战记》的瞬移设计，可能是出于这样的考虑：行走动画的播放需要耗费时间，有时候看起来比较烦，拖慢游戏节奏。但行走动画，有一个“走过去的过程”，能更加表现现实，更有代入感。这是一个游戏策划的问题了，到底是瞬移过去，还是走过去。一个折中的方案是，任何行走都控制在指定的一段时间内完成。这样既有代入感也不会拖慢游戏节奏。

　　一般来说，制作行走过程要比直接瞬移复杂。做出了行走过程要改成瞬移是不难的，但反之则有点麻烦。所以，下面我们先实现地图行走。

2.图论简介

　　仔细观察游戏的世界地图就会发现，除去界面表现后，地图的结构非常类似《离散数学》或《数据结构》中的图论。图论的图表示如下图所示：

　　上图中，实心圆形在图论中叫做顶点（Vertex），连接2个顶点之间的线段叫做边（Edge）。顶点和边都是抽象的，顶点没有几何位置信息，边通常只是表示2个顶点之间有通路和这条通路的路过的代价。代价也是一个抽象的概念，上图中，顶点A到顶点B的代价是7，可以表示城堡A到城堡B的路程是7公里，也可以表示城堡A到城堡B的路费是7英镑。

　　下图中，图1和图2是等价的，尽管它们的几何形态不同。

　　判断它们相同的依据是：顶点相同，边相同，边上的代价也相同。因为顶点没有几何位置信息，所以把顶点A放在任何几何位置都可以，只要它到顶点B的代价不变（7），到顶点C的代价不变（20）。如果A到B的代价改变了，从7变到了50，那么图就改变了，尽管顶点A、B的几何位置不变。老实说，图论的这种抽象，让我刚接触图论时多少有点不适应。（学美术出身的我总是会关注图像的形态，之前总是觉得看起来的样子不同就是不同）但这种抽象恰恰是数学和编程解决问题的精妙之处。

　　以上说的是无向图。无向图就是图的边是没有方向的。如果，顶点A到顶点B之间有一条边，就认为可以从A到B也可以从B到A。还有另一种图是有向图，有向图如下所示：

　　有向图就是图的边是有方向的。如上图所示，顶点A到顶点B有一条有向边，但这条边只表示能从A到B，而B没有一条到A的有向边，所以不能从B直接到A。从B到A只有先到C再从C到A。有向图有自己的一些概念术语，顶点A和顶点B之间的那条边，对于顶点A来说叫做出度，对于顶点B来说叫做入度。为了让解释更加易懂，下面我们称出度叫出边，入度叫入边吧。

　　有向图一般用来表示什么含义呢？某些城市的某些路段是车辆单行线的，因为某种原因，扩路困难但同时某个方向的车流量又大，所以规定车辆只能往一个方向走。这种情况就可以用有向图来表示了。

　　上图中，顶点B到顶点C的代价是8，而反过来顶点C到顶点B的代价是50。这又是什么情况呢？

　　情况1：假设B是山顶位置，C地山底位置，从山顶徒步下山耗费的体力是8，而要徒步上山耗费的体力是50。C到B还可以另加一条代价是1的边。表示坐缆车上山只需要耗费1的体力。这种建模，可以用来做某种策略的计算，比如：计算最节省体力达到山顶的策略。

　　情况2：图可以表示从一点到另一点驾车所耗费的时间。Siliphen驾车从家B出发，到达了途中的一个位置C，这时突然想起有一个重要文件落在家B了，需要回去取。B到C的时间是8分钟，而因为路况问题，下班车辆单向高峰期等原因，从C到B需要50分钟。Siliphen回家取文件的最快策略应该是先花费20分钟开车到A，再从A花费7分钟到B。总体耗时27分钟。

　　可以看到有向图很有用，可以为情况建模并设计算法去计算出要达到某种目的的策略。

　　有向图可以用2条有向边来模拟无向图的一条无向边。如下图所示：

3.图论的数据结构的实现

　　图是一种很重要的数据结构。路径寻找、人工智能、策略选择等都会用到。

　　一般来说有向图能够比无向图表达更多的内容，同时有向图也能够模拟出无向图。所以，这里我们选择实现有向图。

　　我们的目标是：“自己写一个图论的数据结构的类封装，在这里可以用来表示世界地图和寻路计算。也可以作为不同的使用目的、用在别的使用不同技术的项目中，例如：QT，MFC等。”

　　要做类封装，第一件事就是抽象出类了，什么东西应该成为一个类。我个人有一个经验：你看到的或者你意识到存在的东西都可以考虑定为一个类。从图中，我们看到了顶点和边。OK，我们有2个类了：class Vertex , class Edge。顶点和边的集合构成一张图。OK，class Graph 类有了。

　　图的数据结构表示通常有2种。1.邻接矩阵 2.邻接表。邻接表较为常用。如果邻接表的顶点类只保存其出度的信息，对于查询该顶点的入度信息就比较麻烦了，需要遍历其他所有的顶点来确定哪些顶点的出度是指向该顶点的。所以，也可以增加一个入度信息表来方便查询入度信息，这个做法称为逆邻接表。

　　我的封装实现是邻接表，顶点类Vertex有出边信息也有入边信息。因为，需要维护入边信息，所以插入、删除顶点和边的操作会复杂一些。

　　下面是我的有向图的封装的实现代码：

头文件：

　　实现文件：

　　说明下以上代码的设计。

　　要增加一个图顶点。需要先为顶点确定一个字符串类型的ID，new一个Vertex对象出来，然后Graph::AddVertex把顶点加入到图中。Graph管理顶点对象的释放，不用手动delete。

　　有一种设计是：Graph::NewVertex(); 用图类对象来创建顶点。表明这个顶点对象的内存由Graph来管理。TinyXml库的接口就是这样的。考虑到可能用户要继承自Vertex派生出自己的顶点类，所以没采用这种设计。

　　这里我们的图是用在cocos2d-x中作为地图行走的，有些人觉得Vertex类应该继承自Node。假如这样做的话，我们的图数据结构就依赖于cocos2d-x库了。尽管，我们是用在cocos2d-x的项目中，但为了通用考虑，应该尽量设计得与cocos2d-x无关。所以，我只用了C++语言本身来实现。考虑下这种情况，某一天策划需要一个完善的地图编辑器，可以编辑关卡内要触发的事件或者是敌人的生成规则。这种情况，由于cocos2d-x内置的控件较少，我们可能需要用QT写一个编辑器，这时，我们的图数据结构也可以放到QT的项目中使用。

　　地图行走上的节点涉及到了表现，我们可以另写一个类：class MapWalkVertex : public Node。MapWalkVertex 和Vertex互相关联，互相保存一个对方的引用（指针）。图类与图顶点类、地图行走的节点的关系如下：

　　MapWalkVertex头文件 代码如下：

  1 #pragma once  
  2 #include <vector>  
  3 #include <unordered_map>  
  4 using namespace std ;  
  5   
  6 class Edge ;   
  7 class Vertex ;   
  8 class Graph ;  
  9 class GraphPathfinding ;  
 10   
 11 /* 
 12     图顶点 
 13 */  
 14 class Vertex  
 15 {  
 16     friend class Graph ;  
 17     friend class GraphPathfinding ;   
 18     friend class Dijkstra ;  
 19   
 20 public:  
 21   
 22     Vertex( const string& Name )  
 23     {  
 24         m_strId = Name ;  
 25   
 26         m_Cost = 0 ;  
 27   
 28         m_pGraph = 0 ;  
 29     }  
 30   
 31     ~Vertex( ) { };  
 32   
 33 public:  
 34   
 35     // 附加数据  
 36     unordered_map< string , void*> UserData ;  
 37   
 38 public :   
 39   
 40     const unordered_map< string , Edge* >& GetEdgesOut( ) const { return m_EdgesOut ; }  
 41   
 42     const unordered_map< string , Edge* >& GetEdgesIn( ) const { return m_EdgesIn ; }  
 43   
 44     const string& GetId( ) const { return m_strId ; }  
 45   
 46     const string& GetText( ) const { return m_Text ; }  
 47     void SetText( const string& Text ) { m_Text = Text ; }  
 48   
 49     Graph * GetGraph( ) { return m_pGraph ; }  
 50       
 51 protected:   
 52   
 53     // 出边集合  
 54     unordered_map< string , Edge* > m_EdgesOut ;   
 55   
 56     // 入边集合  
 57     unordered_map< string , Edge* > m_EdgesIn ;  
 58   
 59     // 节点表示的字符串  
 60     string m_Text ;   
 61   
 62     // 节点的ID  
 63     string m_strId ;   
 64   
 65     // 用于寻路算法。路径代价估计  
 66     int m_Cost ;  
 67   
 68     // 所属的图  
 69     Graph * m_pGraph ;   
 70   
 71 };  
 72   
 73   
 74   
 75   
 76 /* 
 77     图顶点的边 
 78     有向边 
 79 */  
 80 class Edge  
 81 {  
 82     friend class Graph ;  
 83   
 84 public:  
 85   
 86     Edge( )  
 87     {  
 88         m_Weight = 0 ;  
 89   
 90         m_pStartVertex = m_pEndVertex = 0 ;  
 91     }  
 92   
 93     Edge( Vertex* pStartVertex , Vertex* pEndVertex , int Weight = 0 )  
 94     {  
 95         m_Weight = Weight ;  
 96   
 97         m_pStartVertex = pStartVertex ;  
 98         m_pEndVertex = pEndVertex ;  
 99     }  
100   
101 public:  
102   
103     int GetWeight( ) const { return m_Weight ; }  
104     void SetWeight( int var ) { m_Weight = var ; }  
105   
106     Vertex* GetStartVertex( ) const { return m_pStartVertex ; }  
107   
108     Vertex* GetEndVertex( ) const { return m_pEndVertex ; }  
109   
110 protected:  
111   
112     // 边的权值  
113     int m_Weight  ;  
114   
115     // 起点的顶点  
116     Vertex * m_pStartVertex ;  
117   
118     // 终点的顶点  
119     Vertex * m_pEndVertex ;  
120   
121 };  
122   
123   
124   
125 /* 
126     图. 
127     图会负责释放顶点和边的内存 
128 */  
129 class Graph  
130 {  
131 public :   
132   
133     Graph( ) ;   
134     ~Graph( ) ;  
135   
136 public :   
137   
138     // 添加一个顶点  
139     void AddVertex( Vertex* pV ) ;  
140   
141     // 删除一个顶点  
142     void DeleleVertex( const string& VertexName ) ;  
143   
144   
145     // 添加一条边。返回边对象  
146     Edge* AddEdge( const string& Vertex1Name , const string& Vertex2Name , int Weight = 0 ) ;  
147   
148     // 删除一条边  
149     void DeleteEdge( const string& StartVertexName , const string& EndVertexName ) ;  
150   
151 public :   
152   
153     const unordered_map< string , Vertex* >& GetVertexes( ) const { return m_Vertexes ; }  
154   
155 protected:   
156   
157     // 顶点的集合  
158     unordered_map< string , Vertex* > m_Vertexes ;   
159   
160     // 边的集合。Key的格式“顶点1name->顶点2name"  
161     unordered_map< string , Edge* > m_Edges ;  
162   
163 protected:  
164   
165 #define GetEdgeKey( pV1 , pV2 )(  pV1->m_strId + "->" + pV2->m_strId ) ;   
166   
167 }; 

　　在使用上，这样做有点绕，有点麻烦，互相关联来关联去的。设计可复用的组件就要在使用上付出一定的代价，没办法。

4.图编辑器的实现思路

　　一般编辑器应该用普通应用软件开发的技术来做。如：Winform , QT , MFC等。这里方便起见，图的编辑也在cocos2d-x中做了。做可视化的图形编辑器首先是定义操作状态类型。比如：鼠标点了一点屏幕，这个操作是放置人物，还是放置一个节点。像Photoshop这样的软件，在画布上点了一点，是用画笔点画了一下，还是用魔棒选取工具做了选择。操作状态类型就是用来区分动作（比如，点击）的不同含义。

　　操作状态定义如下：

　　然后，我们在onTouchBegan，onTouchMoved， onTouchEnded 3个触摸函数中针对不同情况做不同的处理。

　　由于编辑处理的代码较多，就不直接贴代码了，截图演示一下大概的思路。

　　这也是手游实现复杂操作的一种处理方法。在不同的操作状态下，执行不同的代码。状态的切换大部分是通过按下左边的按钮。如下图：

　　这组按钮是用CocoStudio的UI编辑器做的。善用各种工具，事半功倍。

　　有必要说下顶点之间边和拖曳边的显示的实现。该操作如下图：

　　边的显示，其实是一张图片。如何让一个Sprite当作直线来用呢？先准备一个水平线段的图片，大小没关系，可以用10*5像素。有2个操作：1.算出起点到终点的长度，根据长度进行Sprite的缩放。2.起点到终点是一条直线，计算这条直线与水平的角度，Sprite进行相应的旋转。

　　实现代码如下：

5.图数据结构的保存和载入

　　我们编辑好的图，需要持久化。下次可以载入使用。对于地图行走节点需要保存的信息有：顶点ID，节点的位置。边需要保存的信息有：起始顶点的ID，终点顶点的ID，边上的权值

　　我们选择用xml进行保存。Cocos2d-x集成有TinyXml库，读写xml是比较方便的。

　　上图中的图，保存为xml后的数据是这样：

　　咦，图中有3条边，为什么保存为xml后，有6条边的信息？回顾下之前，我们实现的是有向图的数据结构，有向图模拟无向图，就是多加一条反向的有向边。所以有向图模拟无向图，有向图边的数量是无向图边的数量的2倍。

　　图数据的保存和读取，也就是场景数据的持久化，我们可以用一个单独的类来做。避免Layer层的代码过多。我们写的类叫：MapWalkConfigManager（地图行走配置管理器）。

　　该类头文件代码：

　　Cpp代码

6.经典的最短路径算法Dijkstra

　　到此为止，图的创建、编辑、保存、载入都做完了。是时候让玩家角色实现地图行走了。一般角色从一点到另一点走的是一个最短路径，而不会是乱走。

　　图的最短路径的计算，需要依赖边上的权值。这里我们需要计算的是一点到另一点在几何距离上最短的路径，所以我们边上的权值就是2个顶点的几何距离。这个在编辑图创建边的时候计算好。

　　计算图最短路径的算法很多，这里介绍并实践经典的Dijkstra算法。Dijkstra的执行类似BFS（广度优先搜索），并且使用了贪心策略。很多最短路径算法都使用了一种叫做“松弛（Relax）”操作，Dijkstra也不例外，Relax是个怎样的操作呢？

　　松弛是针对边的，但可能会改变出边终点对应的顶点的路径代价估计值。顶点的路径代价估计值又是什么？要计算最短路径，每个顶点还需要一个属性，这个属性就是路径代价估计。回头看看Vertex类的代码，找到一个int m_Cost ; 的字段，这个字段就是路径代价估计。

　　一个顶点的路径代价估计属性表示从起始顶点出发到达该顶点所花费的代价。这个花费的代价是怎样计算出来的呢？通过累加边上的权值。看下图：

　　从A点出发，目的地是D。A到C边上的权值是1，A到B边上的权值是5。A的路径估计为0，因为它到起点的代价为0，显然，自己到自己是无代价的。C的路径代价是1。因为从A到C的边上的权值是1。B的路径代价是5，因为从A到B的边上的权值是5。D有2个可能的路径代价值，8和11。8是B本身的路径代价值加上B到C边上的权值，11是C本身的路径代价值加上从C到D边上的权值。最短路径就是，路径代价相加起来最小的那条路径。显然，A到B的最短路径是A- >B->D，而不是A->C->D。

　　一开始，我们只知道起点A的路径代价为0，B和C的路径代价都是不知道的，但我们知道从A到C和B的边上的权值。通过A路径代价值和边权值的累加，我们就可以知道B和C的路径代价了。OK，来看看Relax对出度顶点的路径代价的影响。

　　Relax松弛A到B的边。如果A的路径代价加上边上的权值的和小于B的路径代价的值，就把B的路径代价值更新为这个和。

　　中文伪代码是这样：

　　结合我们的图数据结构代码，Relax的C语言代码是这样：

　　注意，这里是顶点1到顶点2的出边。Relax只可能会修改顶点2的路径代价值，而不会修改顶点1的。理解了Relax对顶点的路径代价的影响后，我们模拟这样一个过程：

　　1.对所有顶点的路径代价值进行初始化，比如都为1000。然后设置起点A的路径代价值为0。

　　2.对A的所有出边进行松弛，B的路径代价会被更新为5，C的路径代价会被更新为1。

　　3.对B的所有出边进行松弛，D的路径代价会被更新为8。

　　4.对C的所有出边进行松弛，D的路径代价不变。因为11大于8，不满足Relax 函数里面的判断条件。

　　Relax实际上是“紧缩”出边终点上的顶点的路径代价，让路径代价值不断变小。通过模拟这样一个过程，我们发现找到了D的最短路径的路径代价值8。但我们没有记录这个相加边权值的路径是怎样走过来的。要记录路径，我们可以用一个哈希映射表，比如：unordered_map< Vertex* , Vertex* > PathTree ;

　　PathTree[pVertex2] = pVertex1 ; 表示设置pVertex1顶点的前驱路径顶点是pVertex2。完整的Relax操作不光是改进出边终点顶点的路径代价估计值，还会更新出边终点顶点的前驱顶点。完整的Relax操作C代码如下：

　　这个时候，我们再模拟上面的过程。就会发现PathTree记录了A达到D的最短路径。以D对象为key查找映射表会查到B对象，以B对象为key查找映射表会查到A对象。这个就是A到D的最短路径了。

　　实际上，整个unordered_map<Vertex* , Vertex* > PathTree表示的是一个路径树。

　　之前我们模拟的那4步过程，是人为地挑选顶点出来进行松弛，从而找到最短路径。Dijkstra其实就是一个挑选顶点出来松弛的一个算法，这个挑选过程使用贪心策略。OK，看下Dijkstra是怎样执行的。

　　Dijkstra的核心思想其实是非常简短的。说Dijkstra用了贪心策略，就是它会从列表Q中选出一个路径估值最小的顶点v进行Relax松弛。注意：这里的“选出”是这样的含义，在列表中找出一个路径估值最小的顶点，然后列表移除该顶点。Dijkstra的结束条件是把列表Q给选空了。也可以把结束条件修改一下，当选出了目的顶点时就终止。

　　Dijkstra执行完后，会对整个图输出一个路径树。也就是PathTree表达的内容。这个路径树包括了起始顶点到其他顶点的最短路径。

　　我的Dijkstra算法继承自GraphPathfinding类。GraphPathfinding作为基类主要是为了以后增加一些其他的路径搜索算法类。

　　GraphPathfinding头文件

　　Dijjkstra 类.h

　　Dijkstra Cpp

　　我的Dijkstra选出最小路径估计的顶点的方法，用的是列表遍历。要优化Dijkstra的话，可以用优先级队列，终极优化是斐波那契堆。

　　计算出了最短路径，就可以用Sequene动作序列串联MoveTo动作把行走的动画表现出来了。

7.本文工程源代码下载

　　由于实现代码比较多，我就不贴完了。直接发工程，大家自己去看吧。

　　整个cocos2d-x的项目比较大，我只上传Classes和Resources 2个关键的文件夹。大家本地创建一个cocos2d-x的项目，然后覆盖掉这2个文件夹，应该就可以了。

　　下载地址：http://download.csdn.net/detail/stevenkylelee/7723917

　　有一些朋友说编译源代码不过。我的开发环境是：Cocos2d-x 3.2，VS2013。搭建为和我一样的环境试试。如果用VS2012编译，出现“error C2338: The C++ Standard doesn't provide a hash for this type. (..\Classes\Graph\GraphPathfinding.cpp)”错误的话，请 在Graph.h 头文件加上一句：#include <string>