C++ DFS算法實(shí)現(xiàn)走迷宮自動(dòng)尋路
更新時(shí)間：2021年05月17日 15:34:18 作者：白家名
這篇文章主要為大家詳細(xì)介紹了C++ DFS算法實(shí)現(xiàn)走迷宮自動(dòng)尋路，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
C++ DFS算法實(shí)現(xiàn)走迷宮自動(dòng)尋路，供大家參考，具體內(nèi)容如下
深度優(yōu)先搜索百度百科解釋：
事實(shí)上，深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過(guò)程簡(jiǎn)要來(lái)說(shuō)是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問(wèn)一次.
運(yùn)行效果：
說(shuō)明：
深度優(yōu)先搜索算法是在我在圖的部分接觸到的，后來(lái)才發(fā)現(xiàn)它也可以不用在圖的遍歷上，它是一個(gè)獨(dú)立的算法，它也可以直接用在一個(gè)二維數(shù)組上。
其算法原理和實(shí)現(xiàn)步驟在代碼中已經(jīng)有了很好的體現(xiàn)了，這里就不再贅述。
在程序中實(shí)現(xiàn)了手動(dòng)操控走迷宮和自動(dòng)走迷宮兩種模式，并且可在自動(dòng)走完迷宮后顯示行走的路徑。
如果要修改程序使用的迷宮地圖只需要修改map二維地圖數(shù)組和兩個(gè)地圖寬高的常量值即可。同樣可以使用自動(dòng)走迷宮的模式。
理論上這種算法可以對(duì)任意大小任意復(fù)雜的迷宮搜索路徑，但是因?yàn)檫@種算法是用遞歸實(shí)現(xiàn)的，占用空間較大，地圖大小增大也會(huì)多使用很多的空間，受限于堆?？臻g的限制我在把地圖大小增加到2020的時(shí)候運(yùn)行自動(dòng)尋路模式就會(huì)報(bào)堆棧溢出異常了。我在代碼準(zhǔn)備了1818和15*15的兩個(gè)迷宮地圖二維數(shù)組用于測(cè)試。
編譯環(huán)境：
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; //地圖數(shù)組元素對(duì)應(yīng)字符
map<char, int*> movDistanceMap; //按鍵對(duì)應(yīng)移動(dòng)距離
int px, py; //玩家坐標(biāo)
int dArr[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; //數(shù)值和移動(dòng)方向?qū)?yīng)數(shù)組
vector<int*> tempPathVec; //路徑向量
vector<vector<int*>> allPathVec;//存儲(chǔ)所有路徑向量
//檢查參數(shù)位置是否可走
bool check(int x, int y, int(*map)[mapWidth])
{
//判斷修改后的玩家坐標(biāo)是否越界、修改后的玩家坐標(biāo)位置是否可走
if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight || (map[y][x] != 0 && map[y][x] != 3))
return false;
return true;
}
//控制玩家移動(dòng)函數(shù)
bool controlMove (int(*map)[mapWidth])
{
//鍵盤按下時(shí)
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; //臨時(shí)記錄沒(méi)有改變之前的玩家坐標(biāo)
px += movDistanceMap[key][0];
py += movDistanceMap[key][1];
//如果位置不可走則撤銷移動(dòng)并結(jié)束函數(shù)
if (!check(px, py, map))
{
px = temp_x, py = temp_y;
return false;
}
//判斷是否已到達(dá)終點(diǎn)
if (map[py][px] == 3)
{
//打印信息并返回true
cout << "勝利！" << endl;
return true;
}
map[temp_y][temp_x] = 0; //玩家原本的位置重設(shè)為0路面
map[py][px] = 2; //玩家移動(dòng)后的位置設(shè)為玩家2
//清屏并打印修改后地圖
system("cls");
printMap(map);
return false;
}
//用對(duì)應(yīng)圖形打印地圖
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()
{
//數(shù)組元素和字符對(duì)應(yīng)
string cArr[4] = { " ", "■", "♀", "★" };
for (int i = 0; i < 4; i++)
cCMAEMap.insert(pair <int, string>(i, cArr[i]));
//輸入字符和移動(dòng)距離對(duì)應(yīng)
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;
}
}
//深度優(yōu)先搜索
void dfs(int cx, int cy, int(*map)[mapWidth])
{
//把當(dāng)前玩家位置插入到數(shù)組
tempPathVec.push_back(new int[2] {cx, cy});
//循環(huán)四個(gè)方向上下左右
for (int i = 0; i < 4; i++)
{
int x = cx + dArr[i][0]; //玩家下一個(gè)位置的坐標(biāo)
int y = cy + dArr[i][1];
//檢查下一個(gè)位置是否可走
if (!check(x, y, map))
continue;
if (map[y][x] == 3) //已到達(dá)終點(diǎn)
{
tempPathVec.push_back(new int[2]{ x, y }); //把終點(diǎn)位置插入到向量中
allPathVec.push_back(tempPathVec);
return;
}
//為普通路徑
else
{
map[cy][cx] = -1; //當(dāng)前位置臨時(shí)設(shè)為-1，遞歸搜索時(shí)不可走原路，非0且非3的位置都不可走
dfs(x, y, map); //用下一個(gè)位置作為參數(shù)遞歸
map[cy][cx] = 0; //遞歸完成后將當(dāng)前位置重設(shè)為0，可走路徑
}
}
//最后沒(méi)有找到可走的路徑則刪除向量最后一個(gè)元素，此時(shí)函數(shù)結(jié)束遞歸退回到上一層
tempPathVec.pop_back();
}
//輸出路徑信息
void printPathInformation()
{
//int minSizePathIndex = 0; //記錄最短路徑在路徑向量中的下標(biāo)
//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 << "最小長(zhǎng)度：" << 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); //找到玩家所在地圖中的位置
//如果多次調(diào)用findPaths函數(shù)，則需要先清除上一次調(diào)用時(shí)在向量中遺留下來(lái)的數(shù)據(jù)
tempPathVec.clear();
allPathVec.clear();
dfs(px, py, map); //找到所有路徑插入到allPathVec
//找到最短路徑在allPathVec中的下標(biāo)
int minSizePathIndex = 0; //記錄最短路徑在路徑向量中的下標(biāo)
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); //打印地圖
}
//手動(dòng)模式
void manualMode(int(*map)[mapWidth])
{
while (!controlMove(map)) //游戲循環(huán)
Sleep(10);
}
//自動(dòng)模式
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:
//構(gòu)造
Game(int(*map)[mapWidth], char mode)
{
initMapContainer(); //初始化map容器
findPlayerPos(map); //找到玩家所在地圖中的位置
system("cls");
printMap(map); //先打印一遍地圖 ♀ ■ ★
(mode == '1') ? manualMode(map) : automaticMode(map);
}
//析構(gòu)釋放內(nèi)存
~Game()
{
for (auto it = tempPathVec.begin(); it != tempPathVec.end(); it++)
{
delete* it;
*it = nullptr;
}
tempPathVec.clear();
//這里不會(huì)釋放allPathVec了
allPathVec.clear();
}
};
迷宮.cpp main函數(shù)文件
#include "Game.h"
//光標(biāo)隱藏
void HideCursor()
{
CONSOLE_CURSOR_INFO cursor_info = { 1, 0 };
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}
int main()
{
HideCursor(); //光標(biāo)隱藏
//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,
};
//復(fù)制一個(gè)一樣的數(shù)組以保證重新開始游戲時(shí)可以重置數(shù)組
int mapCopy[mapHeight][mapWidth];
memcpy(mapCopy, map, sizeof(mapCopy));
while (true)
{
cout << "選擇模式：1，手動(dòng) 2，自動(dòng)" << endl;
char key = _getch();
Game game(mapCopy, key); //進(jìn)入游戲
cout << "輸入r重新開始：" << endl;
key = _getch();
if (key != 'r' && key != 'R') //輸入值不為r則結(jié)束程序
break;
memcpy(mapCopy, map, sizeof(mapCopy)); //重新賦值
system("cls");
}
return 0;
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C++連接數(shù)據(jù)庫(kù)SqlServer、MySql、Oracle、Access、SQLite、PostgreSQL、Mong
C++是一種通用的編程語(yǔ)言,可以使用不同的庫(kù)和驅(qū)動(dòng)程序來(lái)連接各種數(shù)據(jù)庫(kù),以下是一些示例代碼,演示如何使用?C++?連接?SQL?Server、MySQL、Oracle、ACCESS、SQLite?、?PostgreSQL、MongoDB、Redis數(shù)據(jù)庫(kù)2024-08-08
今天小編就為大家分享一篇基于ROS 服務(wù)通信模式詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12
C語(yǔ)言對(duì)CSV文件從最后往前一行一行讀取的實(shí)現(xiàn)方法
今天小編就為大家分享一篇關(guān)于C語(yǔ)言對(duì)CSV文件從最后往前一行一行讀取的實(shí)現(xiàn)方法，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
c++讀取數(shù)據(jù)文件到數(shù)組的實(shí)例
今天小編就為大家分享一篇c++讀取數(shù)據(jù)文件到數(shù)組的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07
這篇文章主要介紹了c++利用函數(shù)指針示例,需要的朋友可以參考下2014-04-04
C++實(shí)現(xiàn)LeetCode(10.正則表達(dá)式匹配)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(10.正則表達(dá)式匹配),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
自己簡(jiǎn)單封裝的一個(gè)CDialog類實(shí)例
這篇文章主要介紹了自己簡(jiǎn)單封裝的一個(gè)CDialog類,實(shí)例分析了自定義封裝CDialog類的相關(guān)技巧,比較簡(jiǎn)單易懂,需要的朋友可以參考下2015-04-04
講解C++編程中Address-of運(yùn)算符&的作用及用法
這篇文章主要介紹了C++編程中Address-of運(yùn)算符&的作用及用法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)獲取文件夾下所有文件名，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下2022-09-09
這篇文章主要介紹了QString的常用方法(小結(jié))，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12