1.效果圖
其中正方形代表障礙物，實心菱形代表移動者（人），空心菱形代表目標位置（都是可以在代碼中修改的）
本例使用隊列(鏈表實現(xiàn))，以廣度優(yōu)先進行自動尋路。
2.實現(xiàn)代碼
1.隊列方法類
coolQueue.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#pragma once#include <iostream>using namespace std;//隊列//坐標結(jié)構(gòu)體struct Point{ int x; int y; Point() { x = 0; y = 0; } Point(int in_x, int in_y) { x = in_x; y = in_y; } Point& operator=(const Point& right_p) { this->x = right_p.x; this->y = right_p.y; return *this; }};//隊列結(jié)構(gòu)體struct coolQueue{ int data; Point cool_p; coolQueue* next_p; coolQueue(int in_data) { data = in_data; next_p = NULL; } coolQueue(int in_x, int in_y, int in_data = 0) { cool_p.x = in_x; cool_p.y = in_y; data = in_data; next_p = NULL; }};//隊列方法類，限制訪問方式class queueClass{protected: coolQueue* Head_p = NULL; coolQueue* End_p = NULL;public: queueClass() {} void push(int data); //入隊 void push(int in_x, int in_y, int in_data = 0); bool pop(int& re_data); //出隊 bool pop(coolQueue& in_coolQueue); void reverse_order(); //翻轉(zhuǎn) void clear() { for (int data; pop(data);); } ~queueClass() { clear(); }}; |
coolQueue.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#include "coolQueue.h"/*入隊函數(shù)* 傳參：* in_data：入隊的數(shù)據(jù)*/void queueClass::push(int in_data){ if (Head_p == NULL) //隊列為空 { Head_p = new coolQueue(in_data); End_p = Head_p; } else if(Head_p == End_p) //隊列只有一個元素 { End_p = new coolQueue(in_data); Head_p->next_p = End_p; } else { coolQueue* temp_p = new coolQueue(in_data); End_p->next_p = temp_p; End_p = temp_p; }}/*出隊* 傳參：* re_data：接收出隊返回值* 返回值：* 成功返回true，隊列為空返回false* * 把值寫入re_data中返回*/bool queueClass::pop(int& re_data){ if (Head_p == NULL) //隊列為空 return false; re_data = Head_p->data; coolQueue* temp_p = Head_p; if (Head_p == End_p) //隊列只有一個元素 { Head_p = NULL; End_p = NULL; } else Head_p = Head_p->next_p; delete temp_p; return true;}/*同鏈表采用以尾指針為頭的頭插法實現(xiàn)倒序*/void queueClass::reverse_order(){ if (Head_p == NULL || Head_p == End_p) return; coolQueue* p = Head_p, * temp_p; do { temp_p = p; p = p->next_p; temp_p->next_p = End_p->next_p; End_p->next_p = temp_p; } while (p != End_p); p = Head_p; Head_p = End_p; End_p = p;}//以下重載用于輔助自動尋路實現(xiàn)//in_data = 0void queueClass::push(int in_x, int in_y, int in_data){ if (Head_p == NULL) { Head_p = new coolQueue(in_x, in_y, in_data); End_p = Head_p; } else if (Head_p == End_p) { End_p = new coolQueue(in_x, in_y, in_data); Head_p->next_p = End_p; } else { coolQueue* temp_p = new coolQueue(in_x, in_y, in_data); End_p->next_p = temp_p; End_p = temp_p; }}bool queueClass::pop(coolQueue& in_coolQueue){ if (Head_p == NULL) return false; in_coolQueue.data = Head_p->data; //不直接使用復制是因為可能把Head_p的next_p也復制出去導致限制訪問權(quán)限失效 in_coolQueue.cool_p = Head_p->cool_p; coolQueue* temp_p = Head_p; if (Head_p == End_p) { Head_p = NULL; End_p = NULL; } else Head_p = Head_p->next_p; delete temp_p; return true;} |
2.地圖方法類
mapClass.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#pragma once#include "coolQueue.h"#include "windows.h"#include <cmath>using namespace std;#ifndef PI#define PI 3.14159265358979323846#endif // !PI#ifndef Sleep_num#define Sleep_num 500#endif // !打印輸出地圖時的暫停時間#ifndef Map_size#define Map_size 10#endif // !地圖大小/*地圖操作類* 保護繼承隊列，防止外部調(diào)用隊列的函數(shù)*/class mapClass : protected queueClass{protected: int map[Map_size][Map_size]; //地圖 Point persion_p; //起點位置坐標 void new_map(); void reflash_map(); bool auto_find_way(Point& target_p); void auto_move(int in_x, int in_y);public: mapClass(const Point& in_p); bool auto_main(); void into_map(int in_data, int num = 1); bool into_map(int in_x, int in_y, int in_data); void show_map(); void clear_map(const Point& in_p);}; |
mapClass.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
#include "mapClass.h"/*初始化地圖* * 把map置零后設置邊界*/void mapClass::new_map(){ memset(map, 0, Map_size * Map_size);//清零 for (int num = Map_size; num--;) //設置邊緣障礙物 { map[num][0] = 1; map[0][num] = 1; map[num][Map_size - 1] = 1; map[Map_size - 1][num] = 1; }}/*刷新地圖* * 由于在auto_find_way()中會修改地圖中的值作為方向標記* 移動后會殘留一些標記，此函數(shù)將會把這些標記清理（即把標記置回0）*/void mapClass::reflash_map(){ for (int x = Map_size - 1; --x;) for (int y = Map_size - 1; --y;) map[x][y] = map[x][y] % 1000; /*方向標記為1000，2000，3000 和 4000，故 %1000 即可保留其他東西并清理標記*/}/*自動尋路* * 傳參：* &target_p：傳出參數(shù)，找到路徑后寫入目標的坐標* 返回值：* 有路徑返回true，沒有返回false* * 基于隊列尋找到達目標的最優(yōu)路徑，會在地圖上留下方向標記* 如果找到，在其他函數(shù)可以 以目標位置開始，通過方向標記倒推回起點，即為路徑*/bool mapClass::auto_find_way(Point& target_p){ coolQueue out_queue(0, 0, 0); for (int push_num = 1; push_num;) { push_num = 0; //如果push_num在while循環(huán)后仍然為0，說明隊列空且無路可走了 while (this->pop(out_queue)) { for (int i = 1, temp_x, temp_y; i <= 4; ++i)//判斷它的旁邊4個位置 { //此處使用sin()是為了在不同i時(temp_x, temp_y)指向以out_queue為中心的不同方向 //效果同auto_move()中的switch()的使用 temp_x = out_queue.cool_p.x + int(sin(PI / 2 * (i - 2.0))); temp_y = out_queue.cool_p.y + int(sin(PI / 2 * (i - 3.0))); switch (map[temp_x][temp_y]) { case 0: //可走 { map[temp_x][temp_y] = i * 1000; //寫入方向標記 this->push(temp_x, temp_y, 0); //入隊 ++push_num; }break; case 10: //抵達目標位置 { map[temp_x][temp_y] += i * 1000; target_p.x = temp_x; //寫入目標位置 target_p.y = temp_y; this->clear(); //清空隊列 return true; }break; } } if (out_queue.data == -1) //每一輪隊列的最后一個的data標記為-1 break; //以起點位置往外一步為一輪 } if (this->End_p != NULL) this->End_p->data = -1; } this->clear(); return false;}/*自動移動（遞歸函數(shù)）* 傳參：* * 后序遞歸：先調(diào)用遞歸，再移動地點* 因此此函數(shù)目的是一開始傳入目標位置，* 再以地圖上的方向標記倒推上一個位置，* 直到回到起點位置則開始移動，每次移動調(diào)用show()刷新地圖顯示* 即可實現(xiàn)從起點到終點移動的效果*/void mapClass::auto_move(int in_x, int in_y){ /*switch ()可替換為 * temp_x = in_x + int(sin(PI / 2 * (map[in_x][in_y] / 1000)); * temp_y = in_y + int(sin(PI / 2 * (map[in_x][in_y] / 1000 - 1.0)); */ int temp_x = in_x, temp_y = in_y; switch (map[in_x][in_y] / 1000) //解析地圖標記 { case 0:return; break; case 1:++temp_x; break; case 2:++temp_y; break; case 3:--temp_x; break; case 4:--temp_y; break; } /*由于函數(shù)是從終點位置遞歸回起點的，所以上一個調(diào)用此函數(shù)的應該是更接近終點的 * 因此此函數(shù)接受的傳入值（in_x, in_y）是下一個移動點 * （temp_x,temp_y）為本次的移動點 */ auto_move(temp_x, temp_y); //遞歸調(diào)用，讓起點移動到本位置（即temp_x, temp_y） map[temp_x][temp_y] = 0; //把現(xiàn)在的位置清零 map[in_x][in_y] = 100; //把下一個移動點置100，即可實現(xiàn)從現(xiàn)在的位置移動到下一個位置的效果 show_map(); //顯示打印 Sleep(Sleep_num); return;}/*構(gòu)造函數(shù)* 傳參：* in_p：起點位置*/mapClass::mapClass(const Point& in_p){ new_map(); persion_p = in_p;}/*自動尋路主導函數(shù)*/bool mapClass::auto_main(){ show_map(); //顯示地圖 Sleep(Sleep_num); this->clear(); //清空隊列 this->push(persion_p.x, persion_p.y, -1);//把起點入隊 Point target_p; //目標坐標 if (auto_find_way(target_p) == false) //調(diào)用自動尋路 { reflash_map(); return false; } auto_move(target_p.x, target_p.y); //移動 reflash_map(); //清理地圖殘留標記 persion_p = target_p; //重置起點位置，抵達終點后起點即為終點 return true;}/*對地圖寫入數(shù)據(jù)標記* * 傳參：* in_data：寫入的數(shù)據(jù)值* num： 次數(shù)* * 在地圖的隨機空位置上寫入 num 次 in_data 標記* * 存在bug：* 如果地圖坐標已滿，寫入次數(shù)不夠會陷入死循環(huán)* 可考慮加入循環(huán)次數(shù)限制解決*/void mapClass::into_map(int in_data, int num){ if (num <= 0) return; for (int i = 0, j = 0; num--;) { i = rand() % Map_size; j = rand() % Map_size; if (map[i][j] == 0) map[i][j] = in_data; else ++num; }}/*對地圖寫入數(shù)據(jù)標記* * 傳參：* in_x,in_y：寫入的地圖位置* in_data： 寫入的數(shù)據(jù)值* * 返回值：* 如果(in_x, in_y)位置為空則寫入成功返回true，否則返回false* * 在地圖的(in_x, in_y)位置寫入 in_data*/bool mapClass::into_map(int in_x, int in_y, int in_data){ if (map[in_x][in_y] == 0) { map[in_x][in_y] = in_data; return true; } return false;}/*打印顯示地圖*/void mapClass::show_map(){ system("cls"); //清空控制臺輸出 for (int i = 0; i < Map_size; ++i) { for (int j = 0; j < Map_size; ++j) switch (map[i][j] % 1000) { case 0: cout << " "; break;//空白位置 case 1: cout << "□"; break;//障礙物 case 10: cout << "◇"; break;//目標 case 100: cout << "◆"; break;//自己 default: cout << " "; break; } cout << endl; }}/*重置地圖* 傳參：* in_p：起點位置* * 清空地圖，僅保留 起點 和 邊界 標記* 用于輔助循環(huán)刷新障礙物尋路的實現(xiàn)*/void mapClass::clear_map(const Point& in_p){ for (int x = Map_size - 1; --x;) //把地圖中的所有位置置零 for (int y = Map_size - 1; --y;) map[x][y] = 0; persion_p = in_p; //重新設置起點 map[in_p.x][in_p.y] = 100;} |
3.main函數(shù)
main.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>#include <time.h>#include <cmath>#include "mapClass.h"using namespace std;int main(){ srand(int(time(0))); Point persion_p(1, 1), target_p(1, 1); mapClass test_map(persion_p); test_map.into_map(1, 1, 100); //寫入起點 test_map.into_map(1, 20); //寫入障礙物 while (1) { //重置障礙物位置, 取消下面兩句的注釋即可啟用 //test_map.clear_map(target_p); //清空地圖 //test_map.into_map(1, 20); //生成障礙物 do { target_p.x = rand() % (Map_size - 2) + 1; target_p.y = rand() % (Map_size - 2) + 1; } while (test_map.into_map(target_p.x, target_p.y, 10) == false); if (test_map.auto_main() == false) { cout << endl << "<< 走不了！" << endl; Sleep(1500); } } return 0;} |
3.思路
總體和數(shù)據(jù)結(jié)構(gòu)的教科書上的大差不差：以起點為中心，每向外一步作為一輪循環(huán)，循環(huán)中把可走的位置入隊，下一輪循環(huán)把上一輪入隊的位置出隊并再以這些位置為中心往外走一步，把可走位置入隊，一直這樣循環(huán)，直到遇到終點位置或者隊列中為空（因為每一個方向都走不了則隊列循環(huán)后為空）。
（想象一下在沒有障礙物的地圖中，以起點為中心向外擴散）
在上述過程中，把可走位置入隊的同時留下方向標記（上一個位置走到此位置的方向），在循環(huán)結(jié)束后從終點位置倒推即可找到一條回到起點的路徑。
此路徑為最優(yōu)解（最優(yōu)解可能不止一條），因為算法中是從起點往外每一步進行一輪判斷，因此如果找到了終點，那么就是在最少的步數(shù)內(nèi)找到了終點，此時即可結(jié)束循環(huán)，此為最優(yōu)解。如果不結(jié)束，繼續(xù)找下去可能可以找到用更多步數(shù)的路徑。
本例與書中的不同：
1.在找到路徑后利用system("cls")清屏重新輸出，來實現(xiàn)逐步走向終點的效果。
2.在一些細節(jié)的實現(xiàn)上使用不同的嘗試(例如 mapClass::auto_find_way()中使用sin()，直接使用地圖做方向標記等)
3.支持循環(huán)多次尋路，支持重置障礙物位置
到此這篇關于C++ 基于BFS算法的走迷宮自動尋路的實現(xiàn)的文章就介紹到這了,更多相關C++ 內(nèi)容請搜索服務器之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://www.cnblogs.com/coolight7/p/15521930.html
