迷宫自动生成以及基于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 max

int 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
#endif

using 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 = 0; i < m; i++) {

        for (int j = 0; j < m; j++) {

            maze[i][j].dig = false;

            if (i % 2 != 0 && j % 2 != 0)

                maze[i][j].cell = true;
        }

    }

    row_s.push(1);    col_s.push(1);

    srand(static_cast<unsigned int> (time(0)));

    maze[1][0].cell = true;

    maze[m - 2][m - 1].cell = true;



}

//判断周围情况，没有可挖的格子时返回-1
int dirrand() {

    vector <int> dirlist;        //用来记录可选择的方向

    int result = 0;
    int row = row_s.top(), col = col_s.top();

    //0 up, 1 down, 2 left, 3 right
    if (row - 2 > 0 && !maze[row - 2][col].dig)
        dirlist.push_back(0);

    if (row + 2 < m - 1 && !maze[row + 2][col].dig)
        dirlist.push_back(1);

    if (col - 2 > 0 && !maze[row][col - 2].dig)
        dirlist.push_back(2);

    if (col + 2 < m - 1 && !maze[row][col + 2].dig)
        dirlist.push_back(3);

    if (dirlist.size() == 0)
        result = -1;
    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 != -1) {     //前进

            if (dir == 0) {

                maze[row - 2][col].dig = maze[row - 1][col].dig = true;

                row_s.push(row - 2);
                col_s.push(col);

            }
            else if (dir == 1) {

                maze[row + 2][col].dig = maze[row + 1][col].dig = true;

                row_s.push(row + 2);
                col_s.push(col);

            }
            else if (dir == 2) {

                maze[row][col - 2].dig = maze[row][col - 1].dig = true;

                row_s.push(row);
                col_s.push(col - 2);

            }
            else if (dir == 3) {

                maze[row][col + 2].dig = maze[row][col + 1].dig = true;

                row_s.push(row);

                col_s.push(col + 2);
            }
        }
        else {

            row_s.pop();
            col_s.pop();        //后退

        }

    }

}
//输出迷宫
void outmaze() {      //输出迷宫

    for (int i = 0; i < m; i++) {

        for (int j = 0; j < m; j++) {
            if (maze[i][j].em == 3) {
                printf("%2c", '*');
                continue;
            }
            if (maze[i][j].cell || maze[i][j].dig) {
                printf("%2c", ' ');
                if (maze[i][j].em != 3)
                    maze[i][j].em = true;
            }
            else {

                //为了保证对齐，墙壁和道路宽都是2个字符
                cout << "■";
                if (maze[i][j].em != 3)
                    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 = 1;
    //待查找的节点
    stack<node> lopenlist;
    //节点不在地图范围 
    if (beginx < 0 || beginy < 0 || beginx >= m || beginy >= m)
        return 0;
    //起始点加入寻找列表
    closelist.push_back({ beginx,beginy });

    //找到节点
    if ((beginx == endx) && (beginy == endy)) {
        //将该节点添加到路径
        path.push({ beginx,beginy });
        return 1;
    }
#pragma region 查找目标节点周围四个节点，如果要增加斜线功能，可以在此添加

    //检查(beginx,beginy+1)节点
    if (beginy + 1 < m  && maze[beginx][beginy + 1].em == 1) {
        //该节点没找过 加入待查找节点列表
        if (!findcloselist({ beginx,beginy + 1 })) {

            lopenlist.push({ beginx,beginy + 1 });
        }
    }
    //检查(beginx,beginy-1)节点
    if (beginy - 1 >= 0 && maze[beginx][beginy - 1].em == 1)
    {
        if (!findcloselist({ beginx,beginy - 1 })) {

            lopenlist.push({ beginx,beginy - 1 });
        }
    }
    //检查(beginx-1,beginy)节点
    if (beginx - 1 >= 0 && maze[beginx - 1][beginy].em == 1) {

        if (!findcloselist({ beginx - 1,beginy })) {

            lopenlist.push({ beginx - 1,beginy });
        }
    }
    //检查(beginx+1,beginy)节点
    if (beginx + 1 < m  &&maze[beginx + 1][beginy].em == 1) {
        if (!findcloselist({ beginx + 1,beginy })) {

            lopenlist.push({ beginx + 1,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 0;
}



int main() {
    //初始化
    init();
    //制造迷宫
    genmaze();
    //输出迷宫
    outmaze();
    //寻找路径
    if (!findmaze(1, 0, m - 2, m - 1))
    {
        cout << "没找到出口";
        return -1;
    }
    //依次从栈中取出每一个路径
    while (!path.empty())
    {
        cout << "(" << path.top().x << "," << path.top().y << ")";
        maze[path.top().x][path.top().y].em = 3;
        path.pop();
        if (!path.empty())
            cout << ",";
    }
    cout << endl;
    cout << "--------------------------------------------" << endl;

    outmaze();
    system("pause");
    return 0;

}