快捷導(dǎo)航

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ù)組以保證重新開(kāi)始游戲時(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重新開(kāi)始：" << 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í)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: