C++ DFS算法实现走迷宫自动寻路
程序员文章站
2022-06-27 10:35:01
c++ dfs算法实现走迷宫自动寻路,供大家参考,具体内容如下深度优先搜索百度百科解释:事实上,深度优先搜索属于图算法的一种,英文缩写为dfs即depth first search.其过程简要来说是对...
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; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
上一篇: QT实现贪吃蛇游戏