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

作者: 容易吗我30141521
来源: 51数据库
2021-09-04

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;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。