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

目录(?)[+]

一，说在前面的话

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

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

二，讲解部分

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

1. #include<map>
2. #include<vector>
3. #include<iostream>

typedefunsignedintuint;
1. typedefstd::vector<int>CRow;
2. //相当于把CLabyrinth定义成一个整型的二维数组
3. typedefstd::vector<CRow>CLabyrinth;

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;

{
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(//查找起点
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. };

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!