文档章节

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

piggybear
 piggybear
发布于 2015/02/16 10:33
字数 2135
阅读 15
收藏 0
点赞 0
评论 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
西安
技术主管
Android 游戏开发之主角的移动与地图的平滑滚动

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

无鸯 ⋅ 2011/10/03 ⋅ 5

Android 游戏开发之主角的移动与地图的平滑滚动(十五)

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

晨曦之光 ⋅ 2012/03/07 ⋅ 0

Cocos2d-x3.1.1 lua 反转贪吃蛇V1

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

Nov_Eleven ⋅ 2014/08/24 ⋅ 1

Android 游戏开发之主角的移动与地图的平滑滚动(十五)

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

彭博 ⋅ 2012/03/09 ⋅ 0

Cocos2d-x游戏开发之图片元素

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

长平狐 ⋅ 2013/03/19 ⋅ 0

Cocos2d-x游戏开发之图片元素

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

长平狐 ⋅ 2012/11/19 ⋅ 0

忍者无敌-实例讲解Cocos2d-x瓦片地图

实例比较简单,如图所示,地图上有一个忍者精灵,玩家点击他周围的上、下、左、右,他能够向这个方向行走。当他遇到障碍物后是无法穿越的,障碍物是除了草地以为部分,包括了:树、山、河流等...

智捷课堂 ⋅ 2014/09/19 ⋅ 1

AS3 做webGame 地图寻路实例 .

总结目的 在地图中,通过鼠标或者由程序自动运行,让一个人物自动从地图的一点走到另一点。需要计算两点之间的最优路线,要实现这样的寻路算法。最常规和最简单的方法,使用A算法。本篇总结不...

小木头的冬天 ⋅ 2016/07/27 ⋅ 0

Cocos2d-x优化中关于背景图片优化

由于背景图片长时间在场景中保存,而且图片很多,我们可以对其进行一些优化。我们通过如下几个方面考虑优化: 1、不要Alpha通道 背景图片的特点是不需要透明的,所以纹理格式可以采用不带有A...

智捷课堂 ⋅ 2014/11/11 ⋅ 0

Cocos2d-x3.0游戏实例之《别救我》第三篇——循环滚动背景(下)

51cto对文章长度有限制,所以第三篇分开两次来发。 统一控制游戏逻辑 地图滚动,其实就是不断改变2张地图的坐标,要不断改变坐标,就要用schedule来实现,schedule可以在游戏每一帧或者每隔一...

musicvs ⋅ 2014/05/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CENTOS7防火墙命令记录

安装Firewall命令: yum install firewalld firewalld-config Firewall开启常见端口命令: firewall-cmd --zone=public --add-port=80/tcp --permanent firewall-cmd --zone=public --add-po......

cavion ⋅ 55分钟前 ⋅ 0

【C++】【STL】利用chromo来测量程序运行时间与日志时间打印精确到微秒

直接上代码吧,没啥好说的。头疼。 #include <iostream>#include <string>#include <ctime>#include <sstream>#include <iomanip>#include <thread>#include <chrono>using ......

muqiusangyang ⋅ 58分钟前 ⋅ 0

Mac环境下svn的使用

在Windows环境中,我们一般使用TortoiseSVN来搭建svn环境。在Mac环境下,由于Mac自带了svn的服务器端和客户端功能,所以我们可以在不装任何第三方软件的前提下使用svn功能,不过还需做一下简...

故久呵呵 ⋅ 今天 ⋅ 0

破解公司回应苹果“USB限制模式”:已攻破

本周四,苹果发表声明称 iOS 中加入了一项名为“USB 限制模式”的功能,可以防止 iPhone 在连接其他设备的时候被破解,并且强调这一功能并不是针对 FBI 等执法部门,为的是保护用户数据安全。...

六库科技 ⋅ 今天 ⋅ 0

MyBtais整合Spring Boot整合,TypeHandler对枚举类(enum)处理

概要 问题描述 我想用枚举类来表示用户当前状态,枚举类由 code 和 msg 组成,但我只想把 code 保存到数据库,查询处理,能知道用户当前状态,这应该怎么做呢?在 Spring 整合MyBatis 的时候...

Wenyi_Feng ⋅ 今天 ⋅ 0

synchronized与Lock的区别

# <center>王梦龙的读书笔记第一篇</center> ## <center>-synchronized与Lock的区别</centre> ###一、从使用场景来说 + synchronized 是能够注释代码块、类、方法但是它的加锁是和解锁使用一......

我不想加班 ⋅ 今天 ⋅ 0

VConsole的使用

手机端控制台打印输出,方便bug的排查。 首先需要引入vconsole.min.js 文件,然后在文件中创造实例。就能直接使用了。 var vConsole = new VConsole(); vConsole的文件地址...

大美琴 ⋅ 今天 ⋅ 0

Java NIO之字符集

1 字符集和编解码的概念 首先,解释一下什么是字符集。顾名思义,就是字符的集合。它的初衷是把现实世界的符号映射为计算机可以理解的字节。比如我创造一个字符集,叫做sex字符集,就包含两个...

士别三日 ⋅ 今天 ⋅ 0

Spring Bean基础

1、Bean之间引用 <!--如果Bean配置在同一个XML文件中,使用local引用--><ref bean="someBean"/><!--如果Bean配置在不同的XML文件中,使用ref引用--><ref local="someBean"/> 其实两种......

霍淇滨 ⋅ 今天 ⋅ 0

05、基于Consul+Upsync+Nginx实现动态负载均衡

1、Consul环境搭建 下载consul_0.7.5_linux_amd64.zip到/usr/local/src目录 cd /usr/local/srcwget https://releases.hashicorp.com/consul/0.7.5/consul_0.7.5_linux_amd64.zip 解压consu......

北岩 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部