C++ DFS算法如何实现走迷宫自动寻路

小编给大家分享一下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;}

以上是“C++ DFS算法如何实现走迷宫自动寻路”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网其他教程频道！