迷宫算法 之 迷宫生成和迷宫寻路

本文讲解迷宫生成和迷宫寻路算法。

 

 

////////////////////////////////////////////////////////////////////////////////////////////////////

一、三种迷宫生成算法

　　　　1、 dfs（即深度优先）算法生成，分为递归和非递归方法。

　　　　2、 十字分割算法生成，分为递归和非递归方法。

　　　　3、 随机 prim 算法生成，一种非递归方法。

二、两种迷宫寻路算法

　　　　1、dfs 寻路，采用非递归实现。

　　　　2、a* 寻路，一种非递归方法。

 

 

////////////////////////////////////////////////////////////////////////////////////////////////////

进入讲解之前先给出一些说明

　　　　1、笔者所用语言：c++（包括部分 c++11 特性）。

　　　　2、笔者环境：win10 + vs2019。

　　　　3、迷宫生成后的界面由 easyx 绘图库生成。

　　　　4、以 easyx 制作的迷宫算法可视化程序，如有需要请移步：https://codebus.cn/teternity/post/mazealgorithm

　　　　5、迷宫统一要求：长宽均为奇数（且本文默认长宽均为 n）、最外围一圈是墙、入口坐标（0, 1）、出口坐标（n-1, n-2）。

　　　　6、本文由笔者原创，不涉及版权争议，仅用作学习。

　　　　7、阅读代码前，你至少需要熟练的掌握 栈和队列 等数据结构，以及一些 stl 容器，这会在后文提及。

 

 

////////////////////////////////////////////////////////////////////////////////////////////////////

// 接下来进入正文

////////////////////////////////////////////////////////////////////////////////////////////////////

一、三种迷宫生成算法（最外围是墙或入口，因此操作范围是：(1, 1) 到 (n-2, n-2) ）

1、 dfs 算法生成（是一种挖墙算法）

　　　　a、初始时全是墙（n是奇数）：

　　　　　　　　

　　　　b、x,y 均在 1~n-2 中的奇数随机选取一点（即该点坐标均为奇数），将其挖开，并将该点入栈

 　　　　　　　　

　　　　c、四个方向随机选取一个方向，设当前挖开坐标为 (x, y)，

　　　　若该方向上满足 (x + dx*2, y + dy*2) 是墙（dx 和 dy 代表方向，取值为 1 或 -1），则挖开 (x + dx, y + dy)，并重设当前点为 (x + dx*2, y + dy*2)，将当前点入栈

　　　　　　　　

　　　　d、以 cur 为当前点，重复操作步骤 c

　　　　　　　　　　　　

　　　　e、若 cur 不能挖开周围的墙，则栈执行 pop 操作，并将 cur 重置为此时栈中的 top 元素

　　　　f、直到栈为空，说明挖墙操作结束

至此，dfs 挖墙算法讲解结束，回看这个过程，像是一只地鼠打洞一般，其中有几个约束，为了能够连通起点到终点，需要使得挖墙点为奇数，且不能造成当前通道与另一通道挖穿

看看该算法下生成的迷宫形态吧（由 easyx 库绘制）：

　　　　　　　　

源码（包含迭代和非迭代版本算法。另：注释 easyx 的地方是用 easyx 绘图，如果不会 easyx 请删除相关代码）：

#include <iostream>
#include <ctime>
#include <stack>
#include <vector>
#include <algorithm>
#include <easyx.h>
using namespace std;


// 迷宫格子状态
enum cellstate：int { path = 0, wall, flag };

// 迷宫格二维点结构
struct point2
{
    int x, y;
    point2(int _x, int _y) :x(_x), y(_y) {}
};

// 迷宫大小（要求为奇数）
const int mazesize = 21;


// 迷宫生成接口--递归版
void dfs_generator(int _x, int _y, std::vector<std::vector<int>>& maze)
{
    // 定义方向容器
    std::vector<std::vector<int>> dir{ {1,0},{-1,0},{0,1},{0,-1} };
    // 随机打乱方向
    std::random_shuffle(dir.begin(), dir.end());
    // 递归生成迷宫
    maze[_x][_y] = path;
    for (int i = 0; i < 4; ++i)
    {
        if (_x + 2 * dir[i][0] >= 1 && _x + 2 * dir[i][0] <= mazesize - 2 && _y + 2 * dir[i][1] >= 1 && _y + 2 * dir[i][1] <= mazesize - 2
            && maze[_x + 2 * dir[i][0]][_y + 2 * dir[i][1]] == wall)
        {
            maze[_x + dir[i][0]][_y + dir[i][1]] = path;
            dfs_generator(_x + 2 * dir[i][0], _y + 2 * dir[i][1], maze);
        }
    }
}

// 迷宫生成接口--迭代版
void dfs_iterative_generator(std::vector<std::vector<int>>& maze)
{
    // 定义栈容器
    std::stack<point2> sp;
    // 定义方向容器
    std::vector<std::vector<int>> dir{ {1,0},{-1,0},{0,1},{0,-1} };
    // 要求参数为奇数
    point2 temp((rand() % (mazesize - 2) + 1) | 1, (rand() % (mazesize - 2) + 1) | 1);
    sp.push(temp);
    // 后续迭代生成迷宫，并绘制
    while (!sp.empty())
    {
        if (maze[temp.x][temp.y] != path)
            maze[temp.x][temp.y] = path;
        // 随机打乱方向
        std::random_shuffle(dir.begin(), dir.end());
        int i = 0;
        for (; i < 4; ++i)
        {
            if (temp.x + 2 * dir[i][0] >= 1 && temp.x + 2 * dir[i][0] <= mazesize - 2 && temp.y + 2 * dir[i][1] >= 1 && temp.y + 2 * dir[i][1] <= mazesize - 2
                && maze[temp.x + 2 * dir[i][0]][temp.y + 2 * dir[i][1]] == wall)
            {
                maze[temp.x + dir[i][0]][temp.y + dir[i][1]] = path;
                temp.x += 2 * dir[i][0];
                temp.y += 2 * dir[i][1];
                sp.push(temp);
                break;
            }
        }
        if (i == 4) sp.pop();
        if (!sp.empty()) temp = sp.top();
    }
}


// main 函数
int main()
{
    srand((unsigned)time(nullptr));

    // 入口出口
    point2 start(0, 1);
    point2 end(mazesize - 1, mazesize - 2);

    // 二维迷宫容器
    std::vector<std::vector<int>> maze;

    // 初始化迷宫
    for (int i = 0; i < mazesize; ++i) maze.push_back(std::vector<int>());
    for (int i = 0; i < mazesize; ++i)
        for (int j = 0; j < mazesize; ++j)
            maze[i].push_back(wall);
    maze[start.x][start.y] = maze[end.x][end.y] = path;

    // 生成迷宫（迭代和非迭代二选一生成）
    dfs_generator((rand() % (mazesize - 2) + 1) | 1, (rand() % (mazesize - 2) + 1) | 1, maze);
    // dfs_iterative_generator(maze);

    // 打印迷宫
    for (int j = 0; j < mazesize; ++j)
    {
        for (int i = 0; i < mazesize; ++i)
            cout << maze[i][j] << " ";
        cout << endl;
    }

    // easyx
    {
        auto ret = _getwch();
        const int width = 15;
        initgraph(mazesize * width, mazesize * width);
        setlinecolor(darkgray);
        setfillcolor(lightgray);
        for (int j = 0; j < mazesize; ++j)
            for (int i = 0; i < mazesize; ++i)
                if (maze[i][j] == wall)
                    fillrectangle(i * width, j * width, i * width + width - 1, j * width + width - 1);
        // saveimage(_t("d:\\maze.png"));
        ret = _getwch();
        closegraph();
    }

    return 0;
}

 

2、 十字分割算法生成（是一种十字补墙算法）

//

//