迷宫自动生成以及基于DFS的自动寻路算法

直接贴代码

#include<ctime>
#include<conio.h>
#include<iostream>
#include<windows.h>
#include<deque>
#include<queue>
#include<list>
#include<vector>
#include<algorithm>
#include <ctime>
#include <cstdlib>
#include <stack>
using namespace std;#define MAX 50
#define X_MAX MAX
#define Y_MAX MAXint Map[X_MAX][Y_MAX];#define MA 10   //迷宫的规模不能过小//挖洞法造迷宫，为了包围，只能为奇数行列,过小的地图无法生成迷宫
#if MA<5
#undef  MA
#define MA 6
#endif
#if !(MA%2)
#define  M (MA+1)
#else
#define  M MA
#endifusing namespace std;//迷宫格子类型，记录了是否被挖过
class Grid {public:
    //是否访问 是否为空
    bool cell, dig;
    int em;};
struct Node
{
    int X, Y;    bool operator==(const Node& n)
    {
        return (this->X == n.X) && (this->Y == n.Y);
    }};Grid maze[M][M];#pragma region 网上抄的一段挖洞法造迷宫，懒得自己弄//用来存放路径的栈
stack<int> row_s, col_s;//初始化迷宫格子
void Init() {    for (int i = ; i < M; i++) {        for (int j = ; j < M; j++) {            maze[i][j].dig = false;            if (i %  !=  && j %  != )                maze[i][j].cell = true;
        }    }    row_s.push();    col_s.push();    srand(static_cast<unsigned int> (time()));    maze[][].cell = true;    maze[M - ][M - ].cell = true;}//判断周围情况，没有可挖的格子时返回-1
int DirRand() {    vector <int> dirlist;        //用来记录可选择的方向    int result = ;
    int row = row_s.top(), col = col_s.top();    //0 up, 1 down, 2 left, 3 right
    if (row -  >  && !maze[row - ][col].dig)
        dirlist.push_back();    if (row +  < M -  && !maze[row + ][col].dig)
        dirlist.push_back();    if (col -  >  && !maze[row][col - ].dig)
        dirlist.push_back();    if (col +  < M -  && !maze[row][col + ].dig)
        dirlist.push_back();    if (dirlist.size() == )
        result = -;
    else
        result = dirlist[rand() % ((int)dirlist.size())];
    return
        result;}
//制造迷宫
void GenMaze() {    while (!row_s.empty() && !col_s.empty()) {
        int dir = DirRand();
        int row = row_s.top(), col = col_s.top();        if (dir != -) {     //前进            if (dir == ) {                maze[row - ][col].dig = maze[row - ][col].dig = true;                row_s.push(row - );
                col_s.push(col);            }
            else if (dir == ) {                maze[row + ][col].dig = maze[row + ][col].dig = true;                row_s.push(row + );
                col_s.push(col);            }
            else if (dir == ) {                maze[row][col - ].dig = maze[row][col - ].dig = true;                row_s.push(row);
                col_s.push(col - );            }
            else if (dir == ) {                maze[row][col + ].dig = maze[row][col + ].dig = true;                row_s.push(row);                col_s.push(col + );
            }
        }
        else {            row_s.pop();
            col_s.pop();        //后退        }    }}
//输出迷宫
void OutMaze() {      //输出迷宫    for (int i = ; i < M; i++) {        for (int j = ; j < M; j++) {
            if (maze[i][j].em == ) {
                printf("%2c", '*');
                continue;
            }
            if (maze[i][j].cell || maze[i][j].dig) {
                printf("%2c", ' ');
                if (maze[i][j].em != )
                    maze[i][j].em = true;
            }
            else {                //为了保证对齐，墙壁和道路宽都是2个字符
                cout << "■";
                if (maze[i][j].em != )
                    maze[i][j].em = false;
            }
        }
        cout << endl;
    }
}//保存迷宫路径
stack<Node> path;//已经查找的点
vector<Node> closelist;//查看该点是否查找过 返回1在  返回0不在
bool FindCloseList(Node n)
{
    auto var = find(closelist.begin(), closelist.end(), n);
    return !(var == closelist.end());
}#pragma endregion//该函数可以抠出来放在自己程序，需要地图地图数组 起始坐标(beginX,beginY)终点坐标(endX,endY)，结果保留在一个栈中
//有待优化 在迷宫有环的时候，找到的路径不一定是最短的，问题先放在这，以后有时间再想办法
//返回>1为找到  返回0为没找到
int FindMaze(int beginX, int beginY, int endX, int endY) {    int kbz = ;
    //待查找的节点
    stack<Node> lopenlist;
    //节点不在地图范围
    if (beginX <  || beginY <  || beginX >= M || beginY >= M)
        return ;
    //起始点加入寻找列表
    closelist.push_back({ beginX,beginY });    //找到节点
    if ((beginX == endX) && (beginY == endY)) {
        //将该节点添加到路径
        path.push({ beginX,beginY });
        return ;
    }
#pragma region 查找目标节点周围四个节点，如果要增加斜线功能，可以在此添加    //检查(beginX,beginY+1)节点
    if (beginY +  < M  && maze[beginX][beginY + ].em == ) {
        //该节点没找过 加入待查找节点列表
        if (!FindCloseList({ beginX,beginY +  })) {            lopenlist.push({ beginX,beginY +  });
        }
    }
    //检查(beginX,beginY-1)节点
    if (beginY -  >=  && maze[beginX][beginY - ].em == )
    {
        if (!FindCloseList({ beginX,beginY -  })) {            lopenlist.push({ beginX,beginY -  });
        }
    }
    //检查(beginX-1,beginY)节点
    if (beginX -  >=  && maze[beginX - ][beginY].em == ) {        if (!FindCloseList({ beginX - ,beginY })) {            lopenlist.push({ beginX - ,beginY });
        }
    }
    //检查(beginX+1,beginY)节点
    if (beginX +  < M  &&maze[beginX + ][beginY].em == ) {
        if (!FindCloseList({ beginX + ,beginY })) {            lopenlist.push({ beginX + ,beginY });        }
    }
#pragma endregion     //遍历每一个待查找的节点
    while (!lopenlist.empty())
    {
        //取出一个节点
        int x = lopenlist.top().X;
        int y = lopenlist.top().Y;
        lopenlist.pop();
        //递归查找
        auto k = FindMaze(x, y, endX, endY);
        //找到就证明该节点为路径点，加入路径栈中
        if (k)
        {
            path.push({ beginX,beginY });
            return kbz + k;
        }
    }
    return ;
}int main() {
    //初始化
    Init();
    //制造迷宫
    GenMaze();
    //输出迷宫
    OutMaze();
    //寻找路径
    if (!FindMaze(, , M - , M - ))
    {
        cout << "没找到出口";
        return -;
    }
    //依次从栈中取出每一个路径
    while (!path.empty())
    {
        cout << "(" << path.top().X << "," << path.top().Y << ")";
        maze[path.top().X][path.top().Y].em = ;
        path.pop();
        if (!path.empty())
            cout << ",";
    }
    cout << endl;
    cout << "--------------------------------------------" << endl;    OutMaze();
    system("pause");
    return ;}