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; }
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。