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
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。