C++ DFS算法实现走迷宫自动寻路
C++ DFS算法实现走迷宫自动寻路，供大家参考，具体内容如下
深度优先搜索百度百科解释：事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.
运行效果：
深度优先搜索算法是在我在图的部分接触到的，后来才发现它也可以不用在图的遍历上，它是一个独立的算法，它也可以直接用在一个二维数组上。
其算法原理和实现步骤在代码中已经有了很好的体现了，这里就不再赘述。
在程序中实现了手动操控走迷宫和自动走迷宫两种模式，并且可在自动走完迷宫后显示行走的路径。
如果要修改程序使用的迷宫地图只需要修改map二维地图数组和两个地图宽高的常量值即可。同样可以使用自动走迷宫的模式。
理论上这种算法可以对任意大小任意复杂的迷宫搜索路径，但是因为这种算法是用递归实现的，占用空间较大，地图大小增大也会多使用很多的空间，受限于堆栈空间的限制我在把地图大小增加到2020的时候运行自动寻路模式就会报堆栈溢出异常了。我在代码准备了1818和15*15的两个迷宫地图二维数组用于测试。
编译环境：Windows VS2019
代码：Game.h 游戏类
#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函数文件
#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;
}
