不再依赖A*，利用C++编写全新寻路算法

设计模式 前端之家
前端之家收集整理的这篇文章主要介绍了不再依赖A*，利用C++编写全新寻路算法，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

不再依赖A*，利用C++编写全新寻路算法

分类：C/C++ 2013-07-02 19:24 1841人阅读 评论(8) 收藏 举报
C++ 算法 寻路

目录(?)[+]

一，说在前面的话

大概在半年前，看见一到信息竞赛题：在任意方格阵中设置障碍物，确定起始点后，求这两点之间路径。当时觉得蛮有意思的，但是没有时间去做，今天花了两个小时来实现它。据说有一个更高级的寻路算法叫做a*,那我就把我的算法叫做W*。

这个算法主要用于解迷宫和实现战棋游戏(SLG)的寻路。


首先讲一讲我的算法的思路：
我们先确定起始点，然后从起点出发，按一定顺序判断这个位置上下左右是否有可走的位置，如果发现有可走的位置，则递归进入该位置的判断。在递归的同时记录所走的路线。当发现某个位置无路可走，则删除路线的最后一个位置并返回上级位置进行判断。如此反复尝试最终找到路线。


说了这么多，就来讲解一下代码吧。


二，讲解部分

包含头文件（全部都是stl中的）：

[cpp] view plain copy
  1. #include<map>
  2. #include<vector>
  3. #include<iostream>

为几个冗长的类型重命名，用来使后来的代码更明了。
copy
    typedefunsignedintuint;
  1. typedefstd::vector<int>CRow;
  2. //相当于把CLabyrinth定义成一个整型的二维数组
  3. typedefstd::vector<CRow>CLabyrinth;
定义一个类类型表示二维数组中的位置：
copy
    classCPoint
  1. {
  3. public:
  4. intcol;//列
  5. introw;//行
  7. public:
  8. //构造函数，接受行和列的初始化
  9. CPoint(intc=0,intr=0)
  10. :col(c)
  11. ,row(r)
  12. {
  13. return;
  14. }
  15. //赋值操作
  16. CPoint&operator=(constCPoint&pt)
  17. col=pt.col;
  18. row=pt.row;
  19. return*this;
  20. //比较操作
  21. booloperator==(returncol==pt.col&&row==pt.row;
  22. //判断该位置是否合法
  23. boolallRight()
  24. returncol>=0&&row>=0;
  25. };
  26. typedefstd::vector<CPoint>CRoute;

然后到了核心类类型CLabyrinthAI
copy
    {
  1. protected:
  2. //装有迷宫数据的二维数组
  3. CLabyrinthm_xLabyrinth;
  4. //起点位置
  5. CPointm_ptBeginning;
  6. //终点位置
  7. CPointm_ptEnding;
  8. //记录路线的数组
  9. CRoutem_vRoute;
  10. //枚举表示起点、终点的值
  11. enum{Beginning=-1,Ending=-2};
  12. //枚举表示障碍物与可走区的值
  13. enum{CanntGo=0,CanGo=1};
  14. //枚举是否找到终点
  15. enum{FoundEnding=0,NotFoundEnding=1};
  16. //判断某个位置是否已在路线数组中，用于别走重复的路
  17. boolisRepeat(boolbRes=false;
  18. CRoute::iteratorit=m_vRoute.begin();
  19. for(;it!=m_vRoute.end();it++){
  20. CPointpt0=*it;
  21. if(pt0==pt){
  22. bRes=true;
  23. break;
  24. }
  25. returnbRes;
  26. //将某一位置加入路线数组
  27. voidadvance(constCPoint&ptTo)
  28. m_vRoute.push_back(ptTo);
  29. //将路线数组最后一个位置弹出
  30. voidback()
  31. m_vRoute.pop_back();
  32. //判断某一位置是否是起点
  33. boolisBeginning(constCPoint&pt)
  34. returnm_ptBeginning==pt;
  35. //判断某一位置是否是终点
  36. boolisEnding(returnm_ptEnding==pt;
  37. /*-----------------核心算法------------------------*/
  38. //判断某一位置是否可以向上移动
  39. CPointcanUp(constCPoint&ptCurrent)//接受当前位置
  40. CPointptRes=CPoint(-1,-1);
  41. intcol=ptCurrent.col;
  42. introw=ptCurrent.row;
  43. if(row>0){
  44. CPointptNext=CPoint(col,row-1);//上移后位置
  45. //检查上移后位置是否已经走过，以免寻路过程中绕圈子进入死循环
  46. if(!isRepeat(ptNext)){
  47. //获得迷宫二维数组中上移后位置的属性（起点、终点、可走、障碍）
  48. intnAttr=m_xLabyrinth[ptNext.row][ptNext.col];
  49. //如果上移后位置为可走或到达终点，则设定返回值为上移后的位置
  50. if(nAttr==CanGo||nAttr==Ending){
  51. ptRes=ptNext;
  52. returnptRes;//如果上移后位置不可走则返回非法的位置
  53. //以下判断某一位置可否移动的原理大致与上相同，就不多说了
  54. //判断某一位置是否可以向下移动
  55. CPointcanDown(constCPoint&ptCurrent)
  56. CPointptRes=CPoint(-1,-1);
  57. intcol=ptCurrent.col;
  58. introw=ptCurrent.row;
  59. if(row<m_xLabyrinth.size()-1){
  60. CPointptNext=CPoint(col,row+1);
  61. intnAttr=m_xLabyrinth[ptNext.row][ptNext.col];
  62. returnptRes;
  63. //判断某一位置是否可以向左移动
  64. CPointcanLeft(if(col>0){
  65. CPointptNext=CPoint(col-1,row);
  66. //判断某一位置是否可以向右移动
  67. CPointcanRight(if(col<m_xLabyrinth[0].size()-1){
  68. CPointptNext=CPoint(col+1,0); background-color:inherit">/*
  69. *判断某一位置是否可以向四周移动，如果判断到某一位置可以移动，则递归进入该位置判断。
  70. *如果该位置没有任何位置可移动，则返会上级位置并且调用back函数。如果走到终点，
  71. *则立刻返回枚举值FoundEnding，上级位置检查到返回值为FoundEnding，也直接返回。
  72. */
  73. intfindRoute(intnRes=NotFoundEnding;//默认返回值为没有找到终点
  74. CPointptNext=CPoint(-1,248); line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> advance(ptCurrent);//将当前位置加入路线数组
  75. //判断当前位置是否是终点，如果是终点则不进行下面的判断，将返回值设置为找到终点
  76. if(isEnding(ptCurrent)){
  77. nRes=FoundEnding;
  78. }else{//按上左下右的顺序判断有无可走路径
  79. //尝试向上
  80. ptNext=canUp(ptCurrent);//获取向上走后的位置
  81. //判断向上走后的位置是否是合法位置，若不合法，则表明上走到了迷宫的边缘，或者上面没有可走路径
  82. if(ptNext.allRight()){
  83. //上述判断成功，则将向上移动后的位置传入给自己，进行递归。当该函数退出，查看返回值是否为找到终点。若找到终点则立刻返回FoundEnding
  84. if(findRoute(ptNext)==FoundEnding){
  85. returnnRes;
  86. //下列尝试四周位置是否可走的代码与上述大体相同，就不多说了
  87. //尝试向左
  88. ptNext=canLeft(ptCurrent);
  89. if(findRoute(ptNext)==FoundEnding){
  90. nRes=FoundEnding;
  91. returnnRes;
  92. //尝试向下
  93. ptNext=canDown(ptCurrent);
  94. //尝试向右
  95. ptNext=canRight(ptCurrent);
  96. //检测是否到达终点，若没有到达终点，则立刻从路线表中删除该位置
  97. if(nRes!=FoundEnding){
  98. back();
  99. //构造函数
  100. CLabyrinthAI()
  101. return;
  102. //带有初始化迷宫数组构造函数
  103. CLabyrinthAI(constCLabyrinth&vLabyrinth)
  104. m_xLabyrinth=vLabyrinth;
  105. getBeginning();
  106. getEnding();
  107. //初始化迷宫数组
  108. voidsetLabyrinth(@H_502_983@//查找起点
  109. voidgetBeginning()
  110. uintnRow=0;
  111. for(;nRow<m_xLabyrinth.size();nRow++){
  112. CRowxRow=m_xLabyrinth[nRow];
  113. uintnCol=0;
  114. for(;nCol<xRow.size();nCol++){
  115. intn=xRow[nCol];
  116. if(n==Beginning){
  117. m_ptBeginning=CPoint(nCol,nRow);
  118. break;
  119. //查找终点
  120. voidgetEnding()
  121. uintnRow=0;
  122. for(;nRow<m_xLabyrinth.size();nRow++){
  123. CRowxRow=m_xLabyrinth[nRow];
  124. uintnCol=0;
  125. for(;nCol<xRow.size();nCol++){
  126. intn=xRow[nCol];
  127. if(n==Ending){
  128. m_ptEnding=CPoint(nCol,nRow);
  129. //调用核心算法函数，输出获得的路线
  130. voidAI()
  131. findRoute(m_ptBeginning);
  132. if(!m_vRoute.empty()){
  133. CPointpt=*it;
  134. std::cout<<"("<<pt.row<<","<<pt.col<<")";
  135. if(it!=m_vRoute.end()-1){
  136. std::cout<<"->";
  137. else{
  138. std::cout<<std::endl;
  139. //如果没有找到路线到达终点
  140. std::cout<<"Sorrycannotfileanywaystogetending."<<std::endl;
  141. };
代码都加上了注释，大家可以慢慢看。
如果上述过程把你搅晕了，那就用图来为你解答吧。

然后来到main函数

copy
    //用VC6.0貌似不需要给main传参数，那我就偷一下懒
  1. intmain()
  2. //定义迷宫数组，定义成C风格的二维数组方便查看
  3. intvLabyrinthArray[][4]={
  4. {1,-1,1}
  5. ,{1,1}
  6. };
  7. //以下代码为将C风格的二维数组导入成C++风格的二维数组
  8. intnRowNum=sizeof(vLabyrinthArray)/sizeof(vLabyrinthArray[0]);
  9. intnColNum=sizeof(vLabyrinthArray[0])/sizeof(int);
  10. CLabyrinthvLabyrinth;
  11. for(introw=0;row<nRowNum;row++){
  12. CRowxRow;
  13. intcol=0;col<nColNum;col++){
  14. intn=vLabyrinthArray[row][col];
  15. xRow.push_back(n);
  16. vLabyrinth.push_back(xRow);
  17. //实例化CLabyrinthAI
  18. CLabyrinthAIxAI(vLabyrinth);
  19. //打出路线
  20. xAI.AI();
  21. //使程序暂停，方便查看数据
  22. system("Pause");
  23. return0;
  24. }

以上代码同样加了注释，相信了解C++的同学都能看懂。

运行截图：


（Dos的，有点丑……）

三，Javascript版

顺便我也把C++版的移植到了Javascript上，代码如下：

[javascript] copy
    functionCLabyrinthAI(){
  1. vars= s.m_xLabyrinth=newArray(newArray());
  2. s.m_ptBeginning={};
  3. s.m_ptEnding={};
  4. s.m_vRoute=newArray();
  5. s.Beginning=-1;
  6. s.Ending=-2;
  7. s.CannotGo=0;
  8. s.CanGo=1;
  9. s.FoundEnding=0;
  10. s.NotFoundEnding=1;
  11. CLabyrinthAI.prototype.initAI=function(){
  12. this;
  13. s.getBeginning();
  14. s.getEnding();
  15. CLabyrinthAI.prototype.isRepeat=function(pt){
  16. varbRes=false;
  17. for(varn=0;n<s.m_vRoute.length;n++){
  18. varpt0=s.m_vRoute[n];
  19. if(pt0.col==pt.col&&pt0.row==pt.row){
  20. CLabyrinthAI.prototype.advance=function(ptTo){
  21. this.m_vRoute.push(ptTo);
  22. CLabyrinthAI.prototype.back=this.m_vRoute.splice(this.m_vRoute.length-1,1);
  23. CLabyrinthAI.prototype.isBeginning=if(this.m_ptBeginning.col==pt.col&&this.m_ptBeginning.row==pt.row){
  24. return }else{
  25. CLabyrinthAI.prototype.isEnding=function(pt){
  26. this.m_ptEnding.col==pt.col&&this.m_ptEnding.row==pt.row){
  27. true;
  28. CLabyrinthAI.prototype.canUp=function(ptCurrent){
  29. varptRes={col:-1,row:-1};
  30. varcol=ptCurrent.col;
  31. varrow=ptCurrent.row;
  32. if(row>0){
  33. varptNext={col:col,row:row-1};
  34. if(!s.isRepeat(ptNext)){
  35. varnAttr=s.m_xLabyrinth[ptNext.row][ptNext.col];
  36. if(nAttr==s.CanGo||nAttr==s.Ending){
  37. CLabyrinthAI.prototype.canDown=if(row<s.m_xLabyrinth.length-1){
  38. CLabyrinthAI.prototype.canLeft=varptNext={col:col-1,row:row};
  39. CLabyrinthAI.prototype.canRight=if(col<s.m_xLabyrinth[0].length-1){
  40. varptNext={col:col+1,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> CLabyrinthAI.prototype.allRight=function(p){
  41. if(p.col>=0&&p.row>=0){
  42. CLabyrinthAI.prototype.findRoute=function(ptCurrent){
  43. varnRes=s.NotFoundEnding;
  44. varptNext={col:-1,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> s.advance(ptCurrent);
  45. if(s.isEnding(ptCurrent)){
  46. nRes=s.FoundEnding;
  47. ptNext=s.canUp(ptCurrent);
  48. if(s.allRight(ptNext)){
  49. if(s.findRoute(ptNext)==s.FoundEnding){
  50. nRes=s.FoundEnding;
  51. ptNext=s.canLeft(ptCurrent);
  52. ptNext=s.canDown(ptCurrent);
  53. ptNext=s.canRight(ptCurrent);
  54. if(nRes!=s.FoundEnding){
  55. s.back();
  56. CLabyrinthAI.prototype.getBeginning=varnRow=0;nRow<s.m_xLabyrinth.length;nRow++){
  57. varxRow=s.m_xLabyrinth[nRow];
  58. varnCol=0;nCol<xRow.length;nCol++){
  59. varn=xRow[nCol];
  60. if(n==s.Beginning){
  61. s.m_ptBeginning={col:nCol,row:nRow};
  62. CLabyrinthAI.prototype.getEnding=function(){
  63. varnRow=0;nRow<s.m_xLabyrinth.length;nRow++){
  64. varxRow=s.m_xLabyrinth[nRow];
  65. varnCol=0;nCol<xRow.length;nCol++){
  66. varn=xRow[nCol];
  67. if(n==s.Ending){
  68. s.m_ptEnding={col:nCol,row:nRow};
  69. CLabyrinthAI.prototype.AI=function(data){
  70. s.m_xLabyrinth=data;
  71. s.initAI();
  72. s.findRoute(s.m_ptBeginning);
  73. returns.m_vRoute;
  74. };
设计原理和C++版差不多，只是没有CPoint类而已。

虽然这套算法是研究出来了，但是还不能判断是否为最近路线，因此有待更新。不过以现在的算法，开发一个SLG应该不是问题了。

※感谢我的哥哥与我一起讨论其中的原理。

源代码下载：

http://files.cnblogs.com/yorhom/findRoute.rar

原文链接：https://www.f2er.com/javaschema/286172.html

猜你在找的设计模式相关文章

适配器模式-让不兼容的接口得以适配
适配器模式将一个类的接口转换成客户期望的另一个接口，使得原本接口不兼容的类可以相互合...
策略模式-定义一个算法族
策略模式定义了一系列算法族，并封装在类中，它们之间可以互相替换，此模式让算法的变化独...
设计模式之高质量代码
设计模式讲的是如何编写可扩展、可维护、可读的高质量代码，它是针对软件开发中经常遇到的...
模板方法模式-封装一套算法流程
模板方法模式在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中，使得子类可以在...
迭代器模式-统一集合的遍历方式
迭代器模式提供了一种方法，用于遍历集合对象中的元素，而又不暴露其内部的细节。
单例模式的五种实现方式及优缺点
单例模式（Singleton Design Pattern）保证一个类只能有一个实例，并提供一个全局访问点。
组合模式-统一的处理个别对象与组合对象
组合模式可以将对象组合成树形结构来表示“整体-部分”的层次结构，使得客户可以用一致的方...
装饰者模式-动态的包装原有对象的行为
装饰者模式能够更灵活的，动态的给对象添加其它功能，而不需要修改任何现有的底层代码。
观察者模式-将消息通知给观察者
观察者模式（Observer Design Pattern）定义了对象之间的一对多依赖，当对象状态改变的时候...
代理模式-访问对象的代理而非其本身
代理模式为对象提供一个代理，来控制对该对象的访问。代理模式在不改变原始类代码的情况下...
算法设计模式多媒体技术正则表达式ElasticsearchFlinkHadoopIDE
受约束摘*day25Java常用类库置信lamda留存持续录入年后正则表达式303.17regularexpre匹多模适20130322基础理论pathmunge涵义reectok需要转义的特资源分享validationex简明魔法里弄形如源码实现完备actionscript