当前位置: 开发笔记 > 运维 > 正文

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

作者：小庄2502921871 | 来源：互联网 | 2021-08-16 01:56

这篇文章主要为大家详细介绍了C++DFS算法实现走迷宫自动寻路，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

C++ DFS算法实现走迷宫自动寻路，供大家参考，具体内容如下

深度优先搜索百度百科解释：

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

运行效果：

说明：

深度优先搜索算法是在我在图的部分接触到的，后来才发现它也可以不用在图的遍历上，它是一个独立的算法，它也可以直接用在一个二维数组上。

其算法原理和实现步骤在代码中已经有了很好的体现了，这里就不再赘述。

在程序中实现了手动操控走迷宫和自动走迷宫两种模式，并且可在自动走完迷宫后显示行走的路径。

如果要修改程序使用的迷宫地图只需要修改map二维地图数组和两个地图宽高的常量值即可。同样可以使用自动走迷宫的模式。

理论上这种算法可以对任意大小任意复杂的迷宫搜索路径，但是因为这种算法是用递归实现的，占用空间较大，地图大小增大也会多使用很多的空间，受限于堆栈空间的限制我在把地图大小增加到2020的时候运行自动寻路模式就会报堆栈溢出异常了。我在代码准备了1818和15*15的两个迷宫地图二维数组用于测试。

编译环境：

Windows VS2019

代码：

Game.h 游戏类

#pragma once
#include 
#include 
#include 
#include 
#include 
using namespace std;

//地图宽高常量
constexpr unsigned int mapWidth = 18;
constexpr unsigned int mapHeight = 18;

//游戏类
class Game
{
private:
 map cCMAEMap;  //地图数组元素对应字符
 map movDistanceMap; //按键对应移动距离
 int px, py;      //玩家坐标
 int dArr[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };  //数值和移动方向对应数组
 vector tempPathVec;  //路径向量
 vector> 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 <<"胜利！" <(i, cArr[i]));

  //输入字符和移动距离对应
  char kArr[4] = { 'w', 's', 'a', 'd' };

  for (int i = 0; i <4; i++)
   movDistanceMap.insert(pair (kArr[i], dArr[i]));
 }

 //找到玩家所在地图的位置
 void findPlayerPos(const int(*map)[mapWidth])
 {
  for (int i = 0; i  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 tempPathVec = allPathVec.at(findPath(map));

  for (int i = 1; i

迷宫.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，自动" <

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

推荐阅读

容器
Vue 2 中解决页面刷新和按钮跳转导致导航栏样式失效的问题

本文介绍了如何通过配置路由的 meta 字段，确保 Vue 2 项目中的导航栏在页面刷新或内部按钮跳转时，始终保持正确的 active 样式。具体实现方法包括设置路由的 meta 属性，并在 HTML 模板中动态绑定类名。 ... [详细]

蜡笔小新 2024-12-28 13:45:20
容器
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
容器
深入理解 Oracle 存储函数：计算员工年收入

本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程，并提供完整的代码示例。 ... [详细]

蜡笔小新 2024-12-28 09:49:42
shell
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
docker
Windows 10 系统中禁用 F1 至 F12 功能键的方法

在 Windows 10 中，F1 至 F12 键默认设置为快捷功能键。本文将介绍几种有效方法来禁用这些快捷键，并恢复其标准功能键的作用。请注意，部分笔记本电脑的快捷键可能无法完全关闭。 ... [详细]

蜡笔小新 2024-12-28 09:13:44
docker
2018回顾与2019展望

本文总结了2018年的关键成就，包括职业变动、购车、考取驾照等重要事件，并分享了读书、工作、家庭和朋友方面的感悟。同时，展望2019年，制定了健康、软实力提升和技术学习的具体目标。 ... [详细]

蜡笔小新 2024-12-28 09:10:26
linux
四载相伴，与51CTO学院共成长

在计算机技术的学习道路上，51CTO学院以其专业性和专注度给我留下了深刻印象。从2012年接触计算机到2014年开始系统学习网络技术和安全领域，51CTO学院始终是我信赖的学习平台。 ... [详细]

蜡笔小新 2024-12-28 08:20:07
grep
Linux 系统启动故障排除指南：MBR 和 GRUB 问题

本文详细介绍了 Linux 系统启动过程中常见的 MBR 扇区和 GRUB 引导程序故障及其解决方案，涵盖从备份、模拟故障到恢复的具体步骤。 ... [详细]

蜡笔小新 2024-12-27 20:40:29
grep
通过类型和标签选择元素

本文介绍了如何使用jQuery根据元素的类型（如复选框）和标签名（如段落）来获取DOM对象。这有助于更高效地操作网页中的特定元素。 ... [详细]

蜡笔小新 2024-12-27 19:44:14
tomcat
深入理解Cookie与Session会话管理

本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]

蜡笔小新 2024-12-27 18:20:43
tomcat
Xcode 中多行代码缩进技巧

本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进，包括右缩进和左缩进的具体操作方法。 ... [详细]

蜡笔小新 2024-12-27 17:52:34
tomcat
如何在PHPcms网站中添加广告

本文详细介绍了在PHPcms网站后台添加广告的方法，涵盖多种常见的广告形式，如百度广告和Google广告，并提供了相关设置的步骤。同时，文章还探讨了优化网站流量的SEO策略。 ... [详细]

蜡笔小新 2024-12-27 17:13:07
linux
在Linux系统中配置并启动ActiveMQ

本文详细介绍了如何在Linux环境中安装和配置ActiveMQ，包括端口开放及防火墙设置。通过本文，您可以掌握完整的ActiveMQ部署流程，确保其在网络环境中正常运行。 ... [详细]

蜡笔小新 2024-12-27 14:38:54
linux
Windows 系统下 MySQL 8.0.11 的安装与配置

本文详细介绍了在 Windows 操作系统中安装和配置 MySQL 8.0.11 的步骤，包括环境准备、安装过程以及后续配置，帮助用户顺利完成数据库的部署。 ... [详细]

蜡笔小新 2024-12-27 13:16:32
linux
在Windows系统上安装VMware Workstation 2022的详细步骤

本文将详细介绍如何在Windows系统上安装VMware Workstation 2022。包括从官方网站下载软件、选择合适的版本以及安装过程中的关键步骤。此外，还将提供一些激活密钥供参考。 ... [详细]

蜡笔小新 2024-12-27 12:58:18

小庄2502921871

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章