文档章节

Cocos2d-x 地图行走的实现3:A*算法

piggybear
 piggybear
发布于 2015/02/16 10:33
字数 2135
阅读 17
收藏 0

我们先修改一下之前的Dijkstra的实现,让它变得更像A*的结构。然后,我们再把Dijkstra改成A*。要想对A*有更深的理解,应该先学习Dijkstra。其实A*是Dijkstra的一种改进。


1.修改一下Dijkstra的实现


  回顾一下之前Dijkstra的实现。Dijkstra需要从一个表Q中选出一个路径代价最小的顶点。之前我们的实现是,一开始就把所有的顶点都放入这个表Q中。仔细想下就会发现,那些被初始化为路径代价最大值0x0FFFFFFF的顶点是不可能会被选中的,对于这些顶点不需要遍历。从表中取出的路径代价最小的顶点,取出一个就表示从起点找到了到这个顶点的最短路径,这些顶点不需要再放回列表中。


  我们可以对Dijkstra做这样一个小小的优化,虽然还是O(N^2),时间复杂度没有改变:

    一开始只把起始顶点放入表中。

    如果松弛成功,就把边终点指向的顶点放入表中。


  这样做的话,Relax就要返回结果了。

  

  实现代码如下:


  1. void Dijkstra::Execute( const Graph& Graph , const string& VetexId  )  
  2. {  
  3.     m_Ret.PathTree.clear( ) ;  
  4.   
  5.     const auto& Vertexes = Graph.GetVertexes( ) ;   
  6.     Vertex* pVertexStart = Vertexes.find( VetexId )->second ;   
  7.     vector< Vertex* > Q ;   
  8.   
  9.     // 初始化顶点  
  10.     for ( auto& it : Vertexes )  
  11.     {  
  12.         it.second->PathfindingData.Cost = 0x0FFFFFFF ;  
  13.         pVertexStart->PathfindingData.pParent = 0 ;  
  14.     }  
  15.     // 初始化起始顶点  
  16.     pVertexStart->PathfindingData.Cost = 0 ;  
  17.     pVertexStart->PathfindingData.pParent = 0 ;   
  18.     // 把起始顶点放入列表中  
  19.     Q.push_back( pVertexStart ) ;  
  20.     pVertexStart->PathfindingData.Flag = true ;   
  21.   
  22.     for ( ; Q.size() > 0 ; )  
  23.     {  
  24.         // 选出最小路径估计的顶点  
  25.         auto v = ExtractMin( Q ) ;  
  26.         v->PathfindingData.Flag = false ;   
  27.   
  28.         // 对所有的出边进行“松弛”  
  29.         const auto& EO = v->GetEdgesOut( ) ;   
  30.         for (  auto& it : EO )  
  31.         {  
  32.             Edge* pEdge = it.second ;   
  33.             Vertex* pVEnd = pEdge->GetEndVertex( ) ;  
  34.   
  35.             bool bRet = Relax( v , pVEnd , pEdge->GetWeight( ) ) ;  
  36.             // 如果松弛成功,加入列表中。  
  37.             if ( bRet && pVEnd->PathfindingData.Flag == false )  
  38.             {  
  39.                 Q.push_back( pVEnd ) ;  
  40.                 pVEnd->PathfindingData.Flag = true ;  
  41.             }  
  42.         }  
  43.         // end for  
  44.     }  
  45.     // end for  
  46.   
  47. }  


  Dijkstra要比BFS聪明,BFS只是“盲目地”从队列中取出元素出来扩展,Dijkstra则知道每次应该选取路径代价最短的节点扩展。


2.A*算法


  Dijkstra比BFS聪明,A*则比Dijkstra更聪明,运行更快。A*通过一个叫“启发式函数”的东东来改进扩展规则,它会尽量避免扩展其他无用的顶点,它的目标就是朝着目的地直奔而去的。这样说,好像A*长了眼睛一样能看到当前位置距离目标点还有多远。A*和上面的Dijkstra最大的区别就是有“眼睛”:启发式函数。

  启发式函数会告诉A*应该优先扩展哪个顶点。启发式函数是怎么回事呢?公式表示是:F = G + H。简单地说,就是:当前顶点的路径代价(G) + 当前顶点距离目标顶点估计花费的代价(F)

  之前对Dijkstra做修改优化,就是为了让它更加像A*算法。这里,把Dijkstra的启发式数据从选拥有最小路径代价的顶点改成选拥有最小的F(启发式函数的值)的顶点就变成了A*。估价函数H怎么设计呢?这里取顶点到目标顶点的距离即可。

  我们需要对上面的Dijkstra和数据结构做如下改造:

  1.顶点类的寻路数据结构体增加一个Heuristic字段。该字段用于A*算法,保存启发式函数计算出来的值。如下所示:


  1. class Vertex  
  2. {  
  3.     // ... 省略了一些无关函数和字段  
  4.     // 和以前一样  
  5.   
  6. public :   
  7.   
  8.     // 寻路算法需要的数据  
  9.     struct Pathfinding  
  10.     {  
  11.         // 顶点的前驱顶点。  
  12.         Vertex * pParent ;  
  13.   
  14.         // 路径代价估计  
  15.         int Cost ;   
  16.   
  17.         // 标识符  
  18.         int Flag ;  
  19.   
  20.         // 启发式函数的计算出来的值  
  21.         int Heuristic ;   
  22.   
  23.         Pathfinding( )  
  24.         {  
  25.             pParent = 0 ;  
  26.             Cost = 0 ;   
  27.             Flag = 0 ;   
  28.             Heuristic = 0 ;  
  29.         }  
  30.     }  
  31.     PathfindingData ;  
  32. }  


  2.Dijkstra的Relax松弛函数,改成限制启发式函数F的值。如果计算出来的F值小于这个顶点原先的F值,就更新该顶点的父节点、实际路径代价、F值。

  3.每次循环都判断下,找出来的最小F值的顶点是不是目标顶点。如果是目标顶点,说明找到了路径,算法结束。

  用在这里的A*伪代码如下:


  1. AStar( 图G,起始顶点S,目标顶点T)  
  2. {  
  3.     把起点S放入Open表中  
  4.   
  5.   
  6.     while( Open表不为空)  
  7.     {  
  8.         从Open表中取出估价值F最小的顶点v  
  9.         标记v不在Open表中  
  10.   
  11.         if( v 等于 目标顶点T)  
  12.         {  
  13.             // 找到了路径  
  14.             retrun ;   
  15.         }  
  16.   
  17.         foreach( v的所有出边的终点顶点vEnd )  
  18.         {  
  19.             Relax( v , vEnd , 边的权值 )  
  20.             if( Relax松弛成功 且 顶点vEnd不在Open表中 )  
  21.             {  
  22.                 把vEnd放入Open表中 ;   
  23.                 标记vEnd在Open表中 ;   
  24.             }  
  25.         }  
  26.     }  
  27.   
  28. }  
  29.   
  30. bool Relax( 顶点from , 顶点to , 边上的权值 )  
  31. {  
  32.     // A*启发式函数计算 F = G + H   
  33.     G = 顶点from的路径代价 + 边上的权值 ;   
  34.     H = 顶点to到目标顶点T的估计代价 ;   
  35.     F = G + H ;  
  36.   
  37.     if( F < 顶点to的F估价值)  
  38.     {  
  39.         记录to的父路径为from ;   
  40.         顶点to的路径代价值更新为G ;   
  41.         顶点to的启发式估价值F更新为F ;   
  42.           
  43.         return true ;  
  44.     }  
  45.   
  46.     return false ;   
  47. }  

  可以看到,A*和我们改造的Dijkstra算法,是很像的。如果我们让A*的启发式函数F=G+H的H一直返回0,那就是一个Dijkstra。这里要把A*改成Dijkstra只需要修改一句话。

  下面是我实现的A*算法。

  AStar.h


  1. #pragma once  
  2.   
  3. #include "GraphPathfinding.h"  
  4. #include <functional>  
  5.   
  6. class AStar : public GraphPathfinding  
  7. {  
  8. public:  
  9.     AStar( );  
  10.     ~AStar( );  
  11.   
  12.   
  13. public :   
  14.   
  15.     // 估计顶点到目标顶点的代价  
  16.     std::function<intconst Vertex* pVCurrent , const Vertex* pVTarget ) > Estimate ;   
  17.   
  18. public:  
  19.   
  20.     virtual void Execute( const Graph& Graph , const string& VetexId ) override ;   
  21.   
  22. private :   
  23.   
  24.     // 抽出最小路径估值的顶点  
  25.     inline Vertex* ExtractMin( vector< Vertex* >& Q ) ;  
  26.   
  27.     // 松弛  
  28.     inline bool Relax( Vertex* v1 , Vertex* v2 , int Weight ) ;  
  29.   
  30. public:  
  31.   
  32.     void SetTarget( Vertex* pVTarget ) { m_pVTarget = pVTarget ; }  
  33.   
  34. private:   
  35.   
  36.     Vertex* m_pVTarget ;  
  37.   
  38. };  


  AStar.cpp


  1. #include "AStar.h"  
  2.   
  3.   
  4. AStar::AStar( )  
  5. {  
  6. }  
  7.   
  8.   
  9. AStar::~AStar( )  
  10. {  
  11. }  
  12.   
  13. void AStar::Execute( const Graph& Graph , const string& VetexId )  
  14. {  
  15.     const auto& Vertexes = Graph.GetVertexes( ) ;  
  16.     Vertex* pVertexStart = Vertexes.find( VetexId )->second ;  
  17.     vector< Vertex* > Q ;  
  18.   
  19.     // 初始化顶点  
  20.     for ( auto& it : Vertexes )  
  21.     {  
  22.         Vertex* pV = it.second ;   
  23.   
  24.         pV->PathfindingData.Cost = 0 ;  
  25.         pV->PathfindingData.pParent = 0 ;  
  26.         pV->PathfindingData.Heuristic = 0x0FFFFFFF ;  
  27.         pV->PathfindingData.Flag = false ;  
  28.     }  
  29.     // 初始化起始顶点  
  30.     pVertexStart->PathfindingData.pParent = 0 ;  
  31.     pVertexStart->PathfindingData.Cost = 0 ;  
  32.     pVertexStart->PathfindingData.Heuristic = Estimate( pVertexStart , m_pVTarget ) ;  
  33.     // 把起始顶点放入列表中  
  34.     Q.push_back( pVertexStart ) ;  
  35.     pVertexStart->PathfindingData.Flag = true ;  
  36.   
  37.   
  38.     for ( ; Q.size( ) > 0 ; )  
  39.     {  
  40.         // 选出最小路径估计的顶点  
  41.         auto v = ExtractMin( Q ) ;  
  42.         v->PathfindingData.Flag = false ;  
  43.         if ( v == m_pVTarget )  
  44.         {  
  45.             return ;   
  46.         }  
  47.   
  48.         // 对所有的出边进行“松弛”  
  49.         const auto& EO = v->GetEdgesOut( ) ;  
  50.         for ( auto& it : EO )  
  51.         {  
  52.             Edge* pEdge = it.second ;  
  53.             Vertex* pVEnd = pEdge->GetEndVertex( ) ;  
  54.   
  55.             bool bRet = Relax( v , pVEnd , pEdge->GetWeight( ) ) ;  
  56.             // 如果松弛成功,加入列表中。  
  57.             if ( bRet && pVEnd->PathfindingData.Flag == false )  
  58.             {  
  59.                 Q.push_back( pVEnd ) ;  
  60.                 pVEnd->PathfindingData.Flag = true ;  
  61.   
  62.             }  
  63.         }  
  64.         // end for  
  65.     }  
  66.     // end for  
  67.   
  68. }  
  69.   
  70. Vertex* AStar::ExtractMin( vector< Vertex* >& Q )  
  71. {  
  72.     Vertex* Ret = 0 ;  
  73.   
  74.     Ret = Q[ 0 ] ;  
  75.     int pos = 0 ;  
  76.     for ( int i = 1 , size = Q.size( ) ; i < size ; ++i )  
  77.     {  
  78.         if ( Ret->PathfindingData.Heuristic > Q[ i ]->PathfindingData.Heuristic )  
  79.         {  
  80.             Ret = Q[ i ] ;  
  81.             pos = i ;  
  82.         }  
  83.     }  
  84.   
  85.     Q.erase( Q.begin( ) + pos ) ;  
  86.   
  87.     return Ret ;  
  88. }  
  89.   
  90. bool AStar::Relax( Vertex* v1 , Vertex* v2 , int Weight )  
  91. {  
  92.     // 这里就是启发式函数  
  93.     int G = v1->PathfindingData.Cost + Weight ;  // 取得从V1到V2的实际路径代价  
  94.     int H = Estimate( v2 , m_pVTarget ) ;   // 估计V2到目标节点的路径代价  
  95.     int nHeuristic = G + H ;    // 实际 + 估算 = 启发式函数的值  
  96.   
  97.     // 如果从此路径达到目标会被之前计算的更短,就更新  
  98.     if ( nHeuristic < v2->PathfindingData.Heuristic )  
  99.     {  
  100.         v2->PathfindingData.Cost = G ;  
  101.         v2->PathfindingData.pParent = v1 ;  
  102.   
  103.         v2->PathfindingData.Heuristic = nHeuristic ;  
  104.   
  105.         return true ;  
  106.     }  
  107.   
  108.     return false ;  
  109. }  


  H函数(估计当前顶点到目标顶点的代价)”外包“到外部执行了。因为AStart类是不知道MapWalkVertex顶点类的存在的。为什么要”外包“执行,而不是在AStar类中做呢?如果要在AStar类中做,就需要知道每个顶点的几何位置,而顶点的几何位置是Cocos2D-x的Node类的属性。AStar类不应该和其他东西耦合,为了”独立“,”通用“,计算H就用观察者模式思想,”外包“执行了。


  AStar类的使用,如下:


  1. // A*的H估价函数  
  2. auto Estimate = [ ]( const Vertex* pVCurrent , const Vertex* pVTarget )->int  
  3. {  
  4.     MapWalkVertex * pMwv1 = ( MapWalkVertex* )pVCurrent->UserData.find( "mwv" )->second ;  
  5.     MapWalkVertex * pMwv2 = ( MapWalkVertex* )pVTarget->UserData.find( "mwv" )->second ;  
  6.     Point v = pMwv1->getPosition( ) - pMwv2->getPosition( ) ;   
  7.     int H = v.getLength( ) ;   
  8.     return H ;   
  9.   
  10. } ;   
  11.   
  12. AStar AStar ;  
  13. // 设置目的顶点  
  14. AStar.SetTarget( pVertexTarget ) ;    
  15. // 设置H估价函数  
  16. AStar.Estimate = Estimate ;   
  17. // 开始执行  
  18. AStar.Execute( *m_pGraph , pMwvStart->GetGraphVertex( )->GetId( ) ) ;   


  OK ,A* 完成了。测试运行一下:





  经过测试。我们的A*能找到最短路径。并且执行速度比Dijkstra和Spfa都快。


4.简要总结Djikstra,SPFA,A*算法


  Dijsktra : 选出一个具有最小路径代价的顶点,松弛其所有的边。

  SPFA : 用一个队列存放顶点,从队列中取出队头顶点,松弛其所有边,如果松弛成功,边上顶点入队。

  A* : 是Djikstra的改进版。选出具有启发式函数值最小的顶点,松弛其所有的边。


4.本文源代码工程下载:


  http://download.csdn.net/detail/stevenkylelee/7734787


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

© 著作权归作者所有

共有 人打赏支持
piggybear
粉丝 3
博文 237
码字总数 37552
作品 0
西安
技术主管
Cocos2d-x3.1.1 lua 反转贪吃蛇V1

使用cocos2d-x lua和code ide编写的贪吃蛇小游戏 https://github.com/skyhacker2/SnakeGameLua 本版本为游戏体验版,轻装上阵,给你不一样的贪食蛇游戏体验! 反转贪食蛇一改传统贪食蛇的玩法...

Nov_Eleven
2014/08/24
0
1
Android 游戏开发之主角的移动与地图的平滑滚动

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

无鸯
2011/10/03
3.9K
5
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
Cocos2d-x游戏开发之图片元素

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

长平狐
2013/03/19
49
0

没有更多内容

加载失败,请刷新页面

加载更多

安全管理标准

安全生产严重等级分类: 故障频次: 风险等级矩阵:

乔老哥
11分钟前
1
0
数据结构“树”的相关微视频

今天在腾讯视频上闲逛,然後发现一个叫“岚人”的用户上传了几段小视频,基本上都在5分钟以内,讲解了关于树的一些结构和算法。零代码,非常适合初学者入门。不过,对于老鸟来说,这也是非常...

Iridium
23分钟前
0
0
10-利用思维导图梳理JavaSE-Java 集合

10-利用思维导图梳理JavaSE-Java 集合 主要内容 1.Collection接口 2.Set接口 2.1.Set接口概述 2.2.HashSet类 2.3.TreeSet类 2.4.SortedSet接口 3.List接口 3.1.List接口概述 3.2.ArrayList类...

飞鱼说编程
34分钟前
3
0
活动推荐|互联网3.0与区块链新时代论坛(北京)

1 时间地点 **时间:**9月22日 14:00 - 18:00 地点:(北京海淀)西大街70号 3w咖啡 二层 2 活动详情 Harmony创始人Stephen及团队将介绍他们的区块链分片扩容技术。Stephen曾任Apple地图服务...

HiBlock
52分钟前
1
0
如何优雅的删除Redis的大key

关于Redis大键(Key),我们从[空间复杂性]和访问它的[时间复杂度]两个方面来定义大键。前者主要表示Redis键的占用内存大小;后者表示Redis集合数据类型(set/hash/list/sorted set)键,所含有的...

IT--小哥
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部