文档章节

Cocos2d-x 地图行走的实现2:SPFA算法

piggybear
 piggybear
发布于 2015/02/16 10:28
字数 2023
阅读 7
收藏 0

本节实践另一种求最短路径算法:SPFA


1.寻路算法实现上的优化


  上一节我们实现的Dijkstra用了一个哈希表来保存搜索到的路径树。如果能用直接的访问的方式,就不要用哈希表,因为直接访问的方式会比哈希表更快。我们修改一下图顶点的数据结构。如下:


  1. /* 
  2.     图顶点 
  3. */  
  4. class Vertex  
  5. {  
  6.     friend class Graph ;  
  7.   
  8. public:  
  9.   
  10.     Vertex( const string& Name )  
  11.     {  
  12.         m_strId = Name ;  
  13.   
  14.         m_pGraph = 0 ;  
  15.     }  
  16.   
  17.     ~Vertex( ) { };  
  18.   
  19. public:  
  20.   
  21.     // 附加数据  
  22.     unordered_map< string , void*> UserData ;  
  23.   
  24. public :   
  25.   
  26.     const unordered_map< string , Edge* >& GetEdgesOut( ) const { return m_EdgesOut ; }  
  27.   
  28.     const unordered_map< string , Edge* >& GetEdgesIn( ) const { return m_EdgesIn ; }  
  29.   
  30.     const string& GetId( ) const { return m_strId ; }  
  31.   
  32.     const string& GetText( ) const { return m_Text ; }  
  33.     void SetText( const string& Text ) { m_Text = Text ; }  
  34.   
  35.     Graph * GetGraph( ) { return m_pGraph ; }  
  36.       
  37. protected:   
  38.   
  39.     // 出边集合  
  40.     unordered_map< string , Edge* > m_EdgesOut ;   
  41.   
  42.     // 入边集合  
  43.     unordered_map< string , Edge* > m_EdgesIn ;  
  44.   
  45.     // 节点表示的字符串  
  46.     string m_Text ;   
  47.   
  48.     // 节点的ID  
  49.     string m_strId ;   
  50.   
  51.     // 所属的图  
  52.     Graph * m_pGraph ;   
  53.   
  54. public :   
  55.   
  56.     // 寻路算法需要的数据  
  57.     struct Pathfinding  
  58.     {  
  59.         // 路径代价估计  
  60.         int Cost ;   
  61.   
  62.         // 标识符  
  63.         int Flag ;  
  64.   
  65.         // 顶点的前驱顶点。  
  66.         Vertex * pParent ;   
  67.   
  68.         Pathfinding( )  
  69.         {  
  70.             Cost = 0 ;   
  71.             Flag = 0 ;   
  72.             pParent = 0 ;   
  73.         }  
  74.     }  
  75.     PathfindingData ;  
  76.   
  77. };  

  修改的地方是:把int m_Cost成员变量删掉,末尾增加了一个Pathfinding类型的字段。这个结构体负责保存寻路算法所需要的一些变量。虽然我们可以像这样unordered_map< Vertex* , int > , unordered_map< Vertex* , Vertex*> 动态地为顶点增加一些“临时属性”,但这种做法运行起来比较慢。Pathfinding的pParent字段表示寻路算法执行完后,该顶点到起始顶点的一条”反向路径“,一直查找pParent直到为空,可追溯到起始顶点,这就是一条路径。起始顶点的Pathfinding::pParent肯定为空,因为它就是路径树的根节点。如果非起始顶点的Pathfinding::pParent为空,表示起始顶点到该顶点没有通路。


  上一节我们实现的Dijkstra是按照Dijkstra算法的思想用最简单的方法直接做的。这样做是为了更简单地表达出算法的思想。Dijkstra的算法优化就是在于怎样做”选出拥有最小路径估计的顶点“。关于这个问题的优化,可以搜索下 优先级队列二项堆斐波那契堆


  std有一个叫 priority_queue 的容器,就是优先级队列。是用priority_queue还是自己写一个优先级队列来优化,你们自己考虑吧。俗话说,师傅领进门,修行靠个人。(什么堆来堆去的数据结构,哥早已忘得一干二净了 睡觉


2.SPFA算法介绍


  SPFA是 Shortest Path Faster Algorithm 的缩写,中文直译过来就是:最短路径快速算法。作用在稀疏图上通常比Dijkstra更快,是一种高效的求最短路径算法。和Dijkstra一样,也是求某个顶点到其他所有顶点的最短路径的一种算法。用我自己理解的话来说,SPFA是这样:


  2.1.SPFA算法需要什么

  SPFA需要用到一个先进先出的队列Q。

  SPFA需要对图中的所有顶点做一个标示,标示其是否在队列Q中。可以用哈希表做映射,也可以为顶点增加一个字段。后者的实现效率更高。


  2.2.SPFA是怎样执行的

  2.2.1 SPFA的初始化

  SPFA的初始化和Dijkstra类似。

  先把所有顶点的路径估计值初始化为代价最大值。比如:0x0FFFFFFF。

  所有顶点都标记为不在队列中。

  起始顶点放入队列Q中。

  起始顶点标记在队列中。

  起始顶点的最短路径估计值置为最小值,比如0。

  然后下面是一个循环

  2.2.2 SPFA循环

  循环结束的条件是队列Q为空。第一次进入循环的时候,只有起始顶点一个元素。

  每次循环,弹出队列头部的一个顶点。

  对这个顶点的所有出边进行松弛。如果松弛成功,就是出边终点上对应的那个顶点的路径代价值被改变了,且这个被松弛的顶点不在队列Q中,就把这个被松弛的顶点入队Q。注意,这里顶点入队的条件有2:1.松弛成功。2.且不在队列Q中。

  当队列Q没有了元素。算法结束。


  2.3.SPFA伪代码


[plain]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. void Spfa( 图G,起始顶点VStart )  
  2. {  
  3.     foreach( 对图G中的所有顶点进行遍历,迭代对象v表示遍历到的每一个顶点对象)  
  4.     {  
  5.         设置顶点v的路径代价估计值为代价最大值,例如:0x0FFFFFFF  
  6.         设置标示顶点v不在队列中  
  7.         顶点v的前驱顶点都为空  
  8.     }  
  9.     起始顶点VStart路径代价估计值为最小值0  
  10.     起始顶点VStart入队Q  
  11.   
  12.     for( 如果队列Q不为空)  
  13.     {  
  14.         队列Q弹出一个队头元素v  
  15.         记录v已经不在队列Q中了  
  16.         for( 遍历从队列Q中弹出的队头顶点v的每一个出边)  
  17.         {  
  18.             u = 边终点上的顶点   
  19.             Relax( v , u,边上的权值)  
  20.             if( Relax松弛成功了 && 顶点u不在队列Q中)  
  21.             {  
  22.                 u入队Q  
  23.                 记录u在队列中了  
  24.             }  
  25.         }  
  26.     }  
  27. }  

  

  从以上伪代码来看,SPFA和BFS很像:都用了队列,都是从队列弹出一个元素进行扩展子节点。SPFA不同于BFS的扩展:SPFA的扩展子节点是有条件的,根据松弛的结果。


3.SPFA算法的实现


  Dijkstra不需要关心松弛的结果,所以之前的Dijkstra的Relax函数返回值为void。而SPFA是需要知道松弛是否成功的,它根据此结果决定松弛的顶点是否需要入队。所以,我们实现的SPFA的Relax函数需要返回bool。


  以下,是我的SPFA实现代码


  Spfa.h


  1. #pragma once  
  2.   
  3. #include "Graph\GraphPathfinding.h"  
  4.   
  5. class Spfa :  
  6.     public GraphPathfinding  
  7. {  
  8. public:  
  9.     Spfa( );  
  10.     ~Spfa( );  
  11.   
  12. public :   
  13.   
  14.     virtual void Execute( const Graph& Graph , const string& VetexId ) ;   
  15.   
  16. private:  
  17.   
  18.     inline bool Relax( Vertex* pStartVertex , Vertex* pEndVertex , int Weight ) ;  
  19.   
  20. };  


  Spfa.cpp


  1. #include "Spfa.h"  
  2. #include <queue>  
  3. using namespace std ;  
  4.   
  5. Spfa::Spfa( )  
  6. {  
  7. }  
  8.   
  9.   
  10. Spfa::~Spfa( )  
  11. {  
  12. }  
  13.   
  14. void Spfa::Execute( const Graph& Graph , const string& VetexId )  
  15. {  
  16.     // 取得图的顶点集合  
  17.     const auto& Vertexes = Graph.GetVertexes( ) ;   
  18.     //  取得起始顶点对象  
  19.     Vertex *pVStart = Vertexes.find( VetexId )->second   ;  
  20.   
  21.     // Spfa算法需要一个队列保存顶点  
  22.     queue< Vertex* > Q ;   
  23.   
  24.     // 初始化  
  25.     for ( auto& it : Vertexes )  
  26.     {  
  27.         Vertex *pV = it.second ;   
  28.   
  29.         pV->PathfindingData.Cost = 0x0FFFFFFF ;  
  30.         //IsInQueue[ pV ] = false ;   
  31.         pV->PathfindingData.Flag = false ;  
  32.         pV->PathfindingData.pParent = 0 ; // 顶点的父路径都设置为空  
  33.     }  
  34.     pVStart->PathfindingData.Cost = 0 ;          // 起始顶点的路径代价为0  
  35.     pVStart->PathfindingData.Flag = true ;       // 起始顶点在队列中  
  36.     //m_Ret.PathTree[ pVStart ] = 0 ;               //  起始顶点的父路径为空  
  37.     Q.push( pVStart ) ;                                 // 起始顶点先入队  
  38.       
  39.   
  40.     // spfa算法  
  41.     for ( ; Q.size( ) ;  )  
  42.     {  
  43.         auto pStartVertex = Q.front( ) ; Q.pop( ) ; // 队列弹出一个顶点v  
  44.         pStartVertex->PathfindingData.Flag = false ;  
  45.   
  46.         // 松弛v的所有出边  
  47.         const auto& Eo = pStartVertex->GetEdgesOut( ) ;  
  48.         for ( auto& it : Eo )  
  49.         {  
  50.             auto pEdge = it.second ;   
  51.             auto pEndVertex = pEdge->GetEndVertex( ) ;  
  52.             bool bRelaxRet = Relax( pStartVertex , pEndVertex , pEdge->GetWeight( ) ) ;  
  53.             if ( bRelaxRet )  
  54.             {  
  55.                 // 如果对于出边松弛成功,且出边对应的终点顶点不在队列中的话,就插入队尾  
  56.                 if ( pEndVertex->PathfindingData.Flag == false )  
  57.                 {  
  58.                     Q.push( pEndVertex ) ;  
  59.                     pEndVertex->PathfindingData.Flag = false ;  
  60.                 }  
  61.   
  62.             }  
  63.   
  64.         }  
  65.         // end for  
  66.   
  67.     }  
  68.     // end for  
  69.   
  70.   
  71. }  
  72.   
  73. bool Spfa::Relax( Vertex* pStartVertex , Vertex* pEndVertex , int Weight )  
  74. {  
  75.     int n = pStartVertex->PathfindingData.Cost + Weight ;  
  76.     if ( n < pEndVertex->PathfindingData.Cost )  
  77.     {  
  78.         // 更新路径代价  
  79.         pEndVertex->PathfindingData.Cost = n ;  
  80.         // 更新路径  
  81.         //m_Ret.PathTree[ pEndVertex ] = pStartVertex ;   
  82.         pEndVertex->PathfindingData.pParent = pStartVertex ;  
  83.   
  84.         return true ;  
  85.     }  
  86.   
  87.     return false ;   
  88. }  

4.Dijkstra与SPFA在实际上的比较


  下图是构造了一个比较大的图,对于一次寻路同时用了Dijkstra和SPFA。图的左下角显示2个算法所用的时间。




  对于上图来说,SPFA的执行要快于Dijkstra。当然,是和没有用任何优化的Dijkstra比较的结果。一般来说Dijkstra运行比较稳定,优化后也可以得到不错的性能。而SPFA的优势在于稀疏图,也就是边数较少的图。原因很明显,SPFA不需要像Dijkstra那样去选最小路径代价的顶点出来松弛,它只是从队列里面弹出一个即可。如果边数越少,入队的顶点也就越少。


5.本文工程源代码下载


  上一节的工程代码不小心弄成了8分。这次设置为0分啦。

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


转自:http://blog.csdn.net/stevenkylelee/article/details/38440663

本文转载自:http://blog.csdn.net/aa294194253/article/details/38492133

共有 人打赏支持
piggybear
粉丝 3
博文 237
码字总数 37552
作品 0
西安
技术主管
Android 游戏开发之主角的移动与地图的平滑滚动

人物移动地图的平滑滚动处理 玩过rpg游戏的朋友应该都知道RPG的游戏地图一般都比较大 今天我和大家分享一下在RPG游戏中如何来处理超出手机屏幕大小的游戏地图。 如图所示为程序效果动画图 地...

无鸯
2011/10/03
3.9K
5
Cocos2d-x游戏开发之图片元素

[Cocos2d-x相关教程来源于红孩儿的游戏编程之路 CSDN博客地址:http://blog.csdn.net/honghaier] 红孩儿Cocos2d-X学习园地QQ群:249941957 加群写:Cocos2d-x 本章为我的Cocos2d-x教程一书初...

长平狐
2013/03/19
49
0
Cocos2d-x游戏开发之图片元素

[Cocos2d-x相关教程来源于红孩儿的游戏编程之路 CSDN博客地址:http://blog.csdn.net/honghaier] 红孩儿Cocos2d-X学习园地QQ群:249941957 加群写:Cocos2d-x 本章为我的Cocos2d-x教程一书初...

长平狐
2012/11/19
1K
0
Android 游戏开发之主角的移动与地图的平滑滚动(十五)

雨松MOMO带你走进游戏开发的世界之主角的移动与地图的平滑滚动 雨松MOMO原创文章如转载,请注明:转载自雨松MOMO的博客原文地址:http://blog.csdn.net/xys289187120/article/details/664927...

晨曦之光
2012/03/07
156
0
Android 游戏开发之主角的移动与地图的平滑滚动(十五)

雨松MOMO带你走进游戏开发的世界之主角的移动与地图的平滑滚动 雨松MOMO原创文章如转载,请注明:转载自雨松MOMO的博客原文地址:http://blog.csdn.net/xys289187120/article/details/664927...

彭博
2012/03/09
47
0

没有更多内容

加载失败,请刷新页面

加载更多

记一次winserver2003系统,https无法访问,内存占用持续增加,解决办法

先交代一下环境: win server2003系统,系统装在hyper-v虚拟机里 大概2016年底的镜像,距离今天两年左右 病症:大概9月10号左右用这个镜像还可以访问https,但是今天用这个镜像新装的系统,就...

阳阳露
7分钟前
0
0
jdbc连接orcal数据库

import java.sql.Connection;  import java.sql.DriverManager;  import java.sql.ResultSet;  import java.sql.SQLException;  import java.sql.Statement;    ......

小橙子的曼曼
32分钟前
0
0
Vue学习资料

一直以为Vue是依赖nodejs的。 作为前端也可以耦合性就很低了。 //npm包管理器 进行管理npm install vue//初始化一个项目vue init//本地调试npm run dev//编译完成 ...

大灰狼wow
41分钟前
1
0
fullcalendar重新渲染

uiCalendarConfig.calendars.lesson_calendar.fullCalendar('removeEvents');var ym = uiCalendarConfig.calendars.lesson_calendar.fullCalendar('getView').title;$scope.get_lesson(y......

人来疯啊
45分钟前
1
0
多渠道打包总结

https://www.jianshu.com/p/2130db7584c8 https://blog.csdn.net/u011153817/article/details/50772496...

塔塔米
54分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部