♻️ 资源大小266KB➡️资源下载https://download.csdn.net/download/s1t16/87472201勇闯迷宫游戏1.分析1.1 项目简介迷宫只有两个门一个门叫入口另一个门叫出口。一个骑士骑马从入口进入迷宫迷宫设置很多障碍骑士需要在迷宫中寻找通路以到达出口。1.2 功能分析迷宫问题的求解过程可以采用回溯法即在一定的约束条件下试探地搜索前进若前进中受阻则及时回头纠正错误另择通路继续搜索的方法。从入口出发按某一方向向前探索若能走通即某处可达则到达新点否则探索下一个方向若所有的方向均没有通路则沿原路返回前一点换下一个方向再继续试探直到所有可能的道路都探索到或找到一条通路或无路可走又返回入口点。在求解过程中为了保证在达到某一个点后不能向前继续行走时能正确返回前一个以便从下一个方向向前试探则需要在试探过程中保存所能够达到的每个点的下标以及该点前进的方向当找到出口时试探过程就结束了。由于课程要求迷宫已经提前设置完成,迷宫的路径也在可执行文件中显示了出来,方便读者的阅读。此迷宫的大小为21*212.设计2.1 算法设计2.1.1 文字表述此迷宫从入口到出口的路径是唯一的并且考虑到效率需要用户最快得到路径所以笔者采用基于递归的深度搜索(dfs)算法。从入口开始,按顺序访问其四周的结点,若出界或是障碍物或者是已经被访问过则访问其他的相邻结点若其相邻的结点没有被访问则标记这个点已被访问,再用DFS访问这个点。当访问的点为出口的时候开始回溯并把结点坐标保存起来形成路径。2.2.2 算法流程图2.2 数据结构设计该系统为一个平面迷宫系统需要从入口进入通过一定的算法找到从入口到出口的路径。所以使用(1)二维数组maze 来存储迷宫,同时使用DFS的算法,为了保证地图上的每一个点不会被多次访问故引入(2)二维数组 maze_map 来判断迷宫maze上的点是否已经被访问过。除了走迷宫以外,还需要输出路径,在迷宫中路径唯一且DFS算法是通过递归实现的,所以使用(3)栈 _stack 来存储路径坐标其后进先出的特点恰好和递归的回溯特点相符合。2.3 类结构设计(1)Maze 类用来表示迷宫以及与迷宫相关的信息(2) StackNode 类栈结点,用于存储路径坐标(3) Stack 类栈类,通过栈结点来存储,增删栈结点注因为栈 Stack 需要访问栈结点 StackNode 中的成员(尤其是私有成员)所以将栈 Stack 设置为了栈结点 StackNode 的友元2.4 成员与操作设计(1)全局的常量迷宫相关参数//迷宫总边长 const int maze_size 21; //围墙方块边长 const int block_size 25; //初始位置 const int left_side 75; const int right_side 100; const int top_side 10; const int bottom_side 35; const int init_left 75; const int init_top 10; const int dir_x[4] { 0,0,1,-1 }; const int dir_y[4] { 1,-1,0,0 };(2)Maze 类class Maze { private: //建立迷宫 T** maze; T** maze_map; Stackint _stack; //用于存放最终的坐标 //迷宫坐标 int _left left_side; int _top top_side; int _right right_side; int _bottom bottom_side; //出口坐标 int out_x 20; int out_y 19; protected: void setMaze(); bool isInRange(int x,int y); //判断搜索坐标是否在界内 public: //入口坐标 const int in_x1; const int in_y 0; Maze(); ~Maze(); void printPath(); //打印最终的路径 void runMaze(int x,int y); //DFS搜索路径 void printMaze(); //打印迷宫 };(3)StackNode 类templateclass T class StackNode //栈的结点 { private: T _x; T _y; StackNodeT* _next; public: StackNode(); StackNode(T x, T y); ~StackNode(); friend class StackT; };(4)Stack 类templateclass T class Stack { private: StackNodeT* _top; //栈顶指针 bool _flag; //目标位置是否入栈 public: Stack(); ~Stack(); void push(T x,T y); //入栈操作 void pop(T x,T y); //出栈操作 void setFlag(bool flag); //设置当前结点是否被访问过 bool getFlag()const; //当前结点没有被访问过 int getLength()const; //返回栈的长度 };2.5 特别说明在此次设计中,笔者设计的迷宫为21*21的迷宫,出于方便用户查看迷宫寻找路径的目的笔者使用了开源的C的库easyx.easy库完全开源,其源代码在03_1953608_WuYinghao文件夹中的easyx.h和graphics.h两个头文件中.最终效果如下:用户若想通过 03_1953608_WuYinghao.cpp 和 03_1953608_WuYinghao.h 编译运行生成可执行文件。可以(1)在 03_1953608_WuYinghao.h 中修改文件路径(2)将两个头文件 graphics.h 和 easyx.h 放在 IDE 对应的 include 文件中,在代码中直接引用(#include)即可①Visual Studio 2019将两个文件放在 VS2019 安装目录的\VC\Auxiliary\VS\include 中②Visual C6.0将两个文件放在 Visual C6.0 安装目录的\Microsoft Visual Studio\VC98\Include 中2.6 文件设计由于此系统使用了easyx库此库调用了文件windows.h所以此系统仅支持Windows平台不支持Linux平台。本系统文件放在03_1953608_WuYinghao_Windows文件夹中。本系统的源代码放在两个文件(03_1953608_WuYinghao.h和03_1953608_WuYinghao.cpp)中其中类的定义以及类成员函数定义均放在了03_1953608_WuYinghao.h中,main函数则放在了03_1953608_WuYinghao.cpp中两个文件的关系为03_1953608_WuYinghao.cpp包含 03_1953608_WuYinghao.h其中,03_1953608_WuYinghao.cpp和03_1953608_WuYinghao.h的编码格式均为简体中文(GB2312)-代码页 9363.实现3.1 深度搜索DFS功能的实现3.1.1 功能说明通过递归的方式来查找路径,再回溯的时候保存路径坐标(详细内容见2.1算法设计)3.1.2 DFS 核心代码templateclass T void MazeT::runMaze(int x,int y) { if (out_x x out_y y) //找到出口 { _stack.push(x, y); _stack.setFlag(true); return; } else { maze_map[x][y] 1; //这个点已经被找到过 for (int i 0; i 4; i) { if (_stack.getFlag()) break; int next_x x dir_x[i]; int next_y y dir_y[i]; if (isInRange(next_x, next_y) (maze_map[next_x][next_y]0))//下一个点没有出界并且没有被访问过 { runMaze(next_x, next_y); if (_stack.getFlag()) //已经找到出口 { _stack.push(x, y); } } } } }3.2 判断边界功能的实现3.2.1 功能说明对于迷宫中的坐标(x,y)分析其周围的四个点(x,y1) (x,y-1) (x1,y) (x-1,y).若这个点上为障碍物或这个点超出边界或这个点已经被访问过返回false若没有被访问过,返回true;isInRangex,y函数在类 Maze的protected部分,所以用户不能直接调用,只有Maze类或者其子类才能够调3.2.2 核心代码展示templateclass T bool MazeT::isInRange(int x, int y) { if ((x 0) (x maze_size) (y 0) (y maze_size)(maze[x][y]*)) //可以被访问 return true; else return false; }3.2.3 流程图展示3.3 画迷宫3.3.1 功能说明文件中已经设置了迷宫边界块的长度与宽度(全局const变量不可修改)const int block_size 25; //围墙方块边长使用 easyx 库内置的画矩形函数,画矩形方块来实现迷宫。3.3.2 核心代码展示templateclass T void MazeT::printMaze() { for (int i 0; i maze_size; i) { for (int j 0; j maze_size; j) { if (maze[i][j] #) { setfillcolor(LIGHTCYAN); //设置颜色 fillrectangle(_left, _top, _right, _bottom); // 画矩形 } _left block_size; _right block_size; } _left left_side; _right right_side; _top block_size; _bottom block_size; } }3.3.3 结果展示(截图)3.4 画路径3.4.1 功能说明由于在DFS搜索的是时候已经将路径结点存放在栈中且由于栈后进先出的特点以及递归的特点栈顶的元素(最后入栈的元素)为起点的坐标栈底的元素(最先入栈的结点)为终点的坐标.利用循环操作,对于有n个元素的栈,执行n-1次循环当栈不会空的时候弹出栈顶元素,在对应坐标上画一个圆点(便于用户观看)同时在屏幕上展示当前点的坐标.画圆的操作使用easyx库中的solidcircle(x,y)函数.输出坐标的操作使用了easyx库中的outtextxy()函数。3.4.2 核心代码展示templateclass T void MazeT::printPath() { setcolor(BLACK); outtextxy(750, 10, _T(此迷宫为21*21的迷宫)); outtextxy(700, 30, _T(迷宫从上至下从左至右坐标增大左上为(0,0))); outtextxy(700, 50, _T(路径坐标分成四列从上到下排列)); outtextxy(700,70,_T(每列坐标最左列上方为入口最右列下方为出口)); int x 0, y 0, loc_x0, loc_y 0, length _stack.getLength(); const int interval_x 10; const int interval_y 20; char words[20](00,00); int locx 700, locy 90, tempx 700; for (int i 0; i length; i) { _stack.pop(x,y); loc_x y * block_size (block_size / 2) init_left; //画路径 loc_y x * block_size (block_size / 2) init_top; setfillcolor(RED); //设置圆圈的颜色为红色 solidcircle(loc_x, loc_y, 5); //通过画圆画出坐标 words[1] x / 10 0; words[2] x % 10 0; words[4] y / 10 0; words[5] y % 10 0; //写出路径 for (int i 0; istrlen(words); i) { outtextxy(locx, locy, words[i]); //输出坐标 locx interval_x; } locy interval_y; if (locy 680) { locy 90; tempx80; } locx tempx; } }3.4.3 结果展示(截图)