C++ DFS算法实现走迷宫自动寻路，供大家参考，具体内容如下
深度优先搜索百度百科解释：
事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.
运行效果：
说明：
深度优先搜索算法是在我在图的部分接触到的，后来才发现它也可以不用在图的遍历上，它是一个独立的算法，它也可以直接用在一个二维数组上。
其算法原理和实现步骤在代码中已经有了很好的体现了，这里就不再赘述。
在程序中实现了手动操控走迷宫和自动走迷宫两种模式，并且可在自动走完迷宫后显示行走的路径。
如果要修改程序使用的迷宫地图只需要修改map二维地图数组和两个地图宽高的常量值即可。同样可以使用自动走迷宫的模式。
理论上这种算法可以对任意大小任意复杂的迷宫搜索路径，但是因为这种算法是用递归实现的，占用空间较大，地图大小增大也会多使用很多的空间，受限于堆栈空间的限制我在把地图大小增加到2020的时候运行自动寻路模式就会报堆栈溢出异常了。我在代码准备了1818和15*15的两个迷宫地图二维数组用于测试。
编译环境：
Windows VS2019
代码：
Game.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
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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
|
#pragma once#include <iostream>#include <map>#include <conio.h>#include <vector>#include <windows.h>using namespace std;//地图宽高常量constexpr unsigned int mapWidth = 18;constexpr unsigned int mapHeight = 18;//游戏类class Game{private: map<int, string> cCMAEMap; //地图数组元素对应字符 map<char, int*> movDistanceMap; //按键对应移动距离 int px, py; //玩家坐标 int dArr[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; //数值和移动方向对应数组 vector<int*> tempPathVec; //路径向量 vector<vector<int*>> allPathVec;//存储所有路径向量 //检查参数位置是否可走 bool check(int x, int y, int(*map)[mapWidth]) { //判断修改后的玩家坐标是否越界、修改后的玩家坐标位置是否可走 if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight || (map[y][x] != 0 && map[y][x] != 3)) return false; return true; } //控制玩家移动函数 bool controlMove (int(*map)[mapWidth]) { //键盘按下时 if (!_kbhit()) return false; char key = _getch(); if (key != 'w' && key != 's' && key != 'a' && key != 'd') return false; int temp_x = px, temp_y = py; //临时记录没有改变之前的玩家坐标 px += movDistanceMap[key][0]; py += movDistanceMap[key][1]; //如果位置不可走则撤销移动并结束函数 if (!check(px, py, map)) { px = temp_x, py = temp_y; return false; } //判断是否已到达终点 if (map[py][px] == 3) { //打印信息并返回true cout << "胜利！" << endl; return true; } map[temp_y][temp_x] = 0; //玩家原本的位置重设为0路面 map[py][px] = 2; //玩家移动后的位置设为玩家2 //清屏并打印修改后地图 system("cls"); printMap(map); return false; } //用对应图形打印地图 void printMap(int(*map)[mapWidth]) { for (int i = 0; i < mapHeight; i++) { for (int j = 0; j < mapWidth; j++) cout << cCMAEMap[map[i][j]]; cout << endl; } } //初始化map容器 void initMapContainer() { //数组元素和字符对应 string cArr[4] = { " ", "■", "♀", "★" }; for (int i = 0; i < 4; i++) cCMAEMap.insert(pair <int, string>(i, cArr[i])); //输入字符和移动距离对应 char kArr[4] = { 'w', 's', 'a', 'd' }; for (int i = 0; i < 4; i++) movDistanceMap.insert(pair <char, int*>(kArr[i], dArr[i])); } //找到玩家所在地图的位置 void findPlayerPos(const int(*map)[mapWidth]) { for (int i = 0; i < mapHeight; i++) for (int j = 0; j < mapWidth; j++) if (map[i][j] == 2) { px = j, py = i; return; } } //深度优先搜索 void dfs(int cx, int cy, int(*map)[mapWidth]) { //把当前玩家位置插入到数组 tempPathVec.push_back(new int[2] {cx, cy}); //循环四个方向上下左右 for (int i = 0; i < 4; i++) { int x = cx + dArr[i][0]; //玩家下一个位置的坐标 int y = cy + dArr[i][1]; //检查下一个位置是否可走 if (!check(x, y, map)) continue; if (map[y][x] == 3) //已到达终点 { tempPathVec.push_back(new int[2]{ x, y }); //把终点位置插入到向量中 allPathVec.push_back(tempPathVec); return; } //为普通路径 else { map[cy][cx] = -1; //当前位置临时设为-1，递归搜索时不可走原路，非0且非3的位置都不可走 dfs(x, y, map); //用下一个位置作为参数递归 map[cy][cx] = 0; //递归完成后将当前位置重设为0，可走路径 } } //最后没有找到可走的路径则删除向量最后一个元素，此时函数结束递归退回到上一层 tempPathVec.pop_back(); } //输出路径信息 void printPathInformation() { //int minSizePathIndex = 0; //记录最短路径在路径向量中的下标 //for (int i = 0; i < allPathVec.size(); i++) //{ // cout << allPathVec.at(i).size() << " "; // if (allPathVec.at(i).size() < allPathVec.at(minSizePathIndex).size()) // minSizePathIndex = i; //} //cout << endl << "最小长度：" << allPathVec.at(minSizePathIndex).size() << endl; 输出最短路径信息 //for (auto dArr2 : allPathVec.at(minSizePathIndex)) // cout << dArr2[0] << "_" << dArr2[1] << " "; //输出所有路径信息 //for (auto arr : allPathVec) //{ // for (auto dArr2 : arr) // cout << dArr2[0] << "__" << dArr2[1] << " "; // cout << endl; //} } //寻找路径 int findPath(int(*map)[mapWidth]) { findPlayerPos(map); //找到玩家所在地图中的位置 //如果多次调用findPaths函数，则需要先清除上一次调用时在向量中遗留下来的数据 tempPathVec.clear(); allPathVec.clear(); dfs(px, py, map); //找到所有路径插入到allPathVec //找到最短路径在allPathVec中的下标 int minSizePathIndex = 0; //记录最短路径在路径向量中的下标 for (int i = 0; i < allPathVec.size(); i++) { if (allPathVec.at(i).size() < allPathVec.at(minSizePathIndex).size()) minSizePathIndex = i; } return minSizePathIndex; } //显示路径 void showPath(int(*map)[mapWidth], vector<int*> tempPathVec) { //将能找到的最短的路径上的元素赋值全部赋值为2并输出 for (auto tempDArr : tempPathVec) map[tempDArr[1]][tempDArr[0]] = 2; system("cls"); printMap(map); //打印地图 } //手动模式 void manualMode(int(*map)[mapWidth]) { while (!controlMove(map)) //游戏循环 Sleep(10); } //自动模式 void automaticMode(int(*map)[mapWidth]) { //找到最短路径 vector<int*> tempPathVec = allPathVec.at(findPath(map)); for (int i = 1; i < tempPathVec.size(); i++) { map[tempPathVec[i - 1][1]][tempPathVec[i - 1][0]] = 0; map[tempPathVec[i][1]][tempPathVec[i][0]] = 2; system("cls"); printMap(map); //打印地图 Sleep(200); } cout << "胜利！是否打印完整路径？（Y / N）" << endl; char key = _getch(); if(key == 'Y' || key == 'y') showPath(map, tempPathVec); }public: //构造 Game(int(*map)[mapWidth], char mode) { initMapContainer(); //初始化map容器 findPlayerPos(map); //找到玩家所在地图中的位置 system("cls"); printMap(map); //先打印一遍地图 ♀ ■ ★ (mode == '1') ? manualMode(map) : automaticMode(map); } //析构释放内存 ~Game() { for (auto it = tempPathVec.begin(); it != tempPathVec.end(); it++) { delete* it; *it = nullptr; } tempPathVec.clear(); //这里不会释放allPathVec了 allPathVec.clear(); }}; |
迷宫.cpp main函数文件
|
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
|
#include "Game.h"//光标隐藏void HideCursor(){ CONSOLE_CURSOR_INFO cursor_info = { 1, 0 }; SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);}int main(){ HideCursor(); //光标隐藏 //0空地，1墙，2人， 3出口 //int map[mapHeight][mapWidth] = { // 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, // 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, // 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, // 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, // 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, // 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, // 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, // 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, // 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, // 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, // 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, // 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, // 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, // 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, // 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 3, //}; int map[mapHeight][mapWidth] { 2, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 3, }; //复制一个一样的数组以保证重新开始游戏时可以重置数组 int mapCopy[mapHeight][mapWidth]; memcpy(mapCopy, map, sizeof(mapCopy)); while (true) { cout << "选择模式：1，手动 2，自动" << endl; char key = _getch(); Game game(mapCopy, key); //进入游戏 cout << "输入r重新开始：" << endl; key = _getch(); if (key != 'r' && key != 'R') //输入值不为r则结束程序 break; memcpy(mapCopy, map, sizeof(mapCopy)); //重新赋值 system("cls"); } return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_46239972/article/details/107387149
