首页 > > 程序设计 > C/C++ >

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

2020-03-25 16:01:44来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

 

 

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

一、三种迷宫生成算法

　　　　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 为当前点，重复操作步骤 b

　　　　　　　　　　　　

　　　　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;
}
View Code

 

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

　　　　a、初始时除了四周全是通路（N是奇数）

　　　　　　　　

　　　　b、x,y 均在 1~N-2 中的偶数随机选取一点（即该点坐标均为偶数），然后十字建墙

　　　　　　　　

　　　　c、在建好的四面墙（不包含选取点）中随机选择三面，找奇数点开洞，使得四个子空间连通

　　　　　　　　

　　　　d、对四个子空间重复操作，直到子空间不可分割为止（淡黄色是开洞位置）（何时不可分割？长度 或 宽度 不大于 1 时）

　　　　　　　　

至此，十字分割补墙算法讲解结束。请注意，在选取建墙点时要求是偶数，挖墙时要求是奇数

看看该算法下生成的迷宫形态吧（由 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) {}
};

// 四维点，用于分割矩形区间
struct Point4
{
    int x1, x2;
    int y1, y2;
    Point4(int _x1, int _x2, int _y1, int _y2) :x1(_x1), x2(_x2), y1(_y1), y2(_y2) {}
};

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


// 迷宫生成接口--递归版
void Division_generator(int _l, int _r, int _t, int _b, std::vector<std::vector<int>>& maze)
{
    // 间隔大于 1 时可分割
    if (_r - _l > 1 && _b - _t > 1)
    {
        int i = 0;
        // 要求分割点 px,py 为偶数
        int px = ((rand() % (_r - _l) + _l + 1) | 1) - 1;
        int py = ((rand() % (_b - _t) + _t + 1) | 1) - 1;
        while (px + i <= _r || px - i >= _l || py + i <= _b || py - i >= _t)
        {
            if (px + i <= _r) maze[px + i][py] = WALL;
            if (px - i >= _l) maze[px - i][py] = WALL;
            if (py + i <= _b) maze[px][py + i] = WALL;
            if (py - i >= _t) maze[px][py - i] = WALL;
            ++i;
        }
        // 定义方向容器，随机在三面墙上开洞
        // 要求开洞位置是奇数
        std::vector<int> dir{ 0,1,2,3 };
        std::random_shuffle(dir.begin(), dir.end());
        for (int i = 0; i < 3; ++i)
        {
            if (dir[i] == 0)
            {
                int xx = (rand() % (px - _l) + _l) | 1;
                maze[xx][py] = PATH;
            }
            else if (dir[i] == 1)
            {
                int xx = (rand() % (_r - px) + px) | 1;
                maze[xx][py] = PATH;
            }
            else if (dir[i] == 2)
            {
                int yy = (rand() % (py - _t) + _t) | 1;
                maze[px][yy] = PATH;
            }
            else if (dir[i] == 3)
            {
                int yy = (rand() % (_b - py) + py) | 1;
                maze[px][yy] = PATH;
            }
        }
        // 递归分割
        Division_generator(_l, px - 1, _t, py - 1, maze);
        Division_generator(px + 1, _r, _t, py - 1, maze);
        Division_generator(_l, px - 1, py + 1, _b, maze);
        Division_generator(px + 1, _r, py + 1, _b, maze);
    }
}

// 迷宫生成接口--迭代版
void Division_iterative_generator(std::vector<std::vector<int>>& maze)
{
    // 定义栈容器
    std::stack<Point4> sp;
    // 定义方向容器
    std::vector<int> dir{ 0,1,2,3 };
    // 要求参数为奇数
    Point4 temp(1, mazeSize - 2, 1, mazeSize - 2);
    sp.push(temp);
    // 后续迭代生成迷宫
    while (!sp.empty())
    {
        sp.pop();
        if (temp.x2 - temp.x1 > 1 && temp.y2 - temp.y1 > 1)
        {
            int i = 0;
            int px = ((rand() % (temp.x2 - temp.x1) + temp.x1 + 1) | 1) - 1;
            int py = ((rand() % (temp.y2 - temp.y1) + temp.y1 + 1) | 1) - 1;
            while (px + i <= temp.x2 || px - i >= temp.x1 || py + i <= temp.y2 || py - i >= temp.y1)
            {
                if (px + i <= temp.x2) maze[px + i][py] = WALL;
                if (px - i >= temp.x1) maze[px - i][py] = WALL;
                if (py + i <= temp.y2) maze[px][py + i] = WALL;
                if (py - i >= temp.y1) maze[px][py - i] = WALL;
                ++i;
            }
            // 随机在三面墙上开洞，要求开洞位置是奇数
            std::random_shuffle(dir.begin(), dir.end());
            for (int i = 0; i < 3; ++i)
            {
                if (dir[i] == 0)
                {
                    int xx = (rand() % (px - temp.x1) + temp.x1) | 1;
                    maze[xx][py] = PATH;
                }
                else if (dir[i] == 1)
                {
                    int xx = (rand() % (temp.x2 - px) + px) | 1;
                    maze[xx][py] = PATH;
                }
                else if (dir[i] == 2)
                {
                    int yy = (rand() % (py - temp.y1) + temp.y1) | 1;
                    maze[px][yy] = PATH;
                }
                else if (dir[i] == 3)
                {
                    int yy = (rand() % (temp.y2 - py) + py) | 1;
                    maze[px][yy] = PATH;
                }
            }
            // 将三个方块区间入栈
            sp.push(Point4(px + 1, temp.x2, py + 1, temp.y2));
            sp.push(Point4(temp.x1, px - 1, py + 1, temp.y2));
            sp.push(Point4(px + 1, temp.x2, temp.y1, py - 1));
            temp.x2 = px - 1;
            temp.y2 = py - 1;
            sp.push(temp);
        }
        else 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)
            (i == 0 || j == 0 || i == mazeSize - 1 || j == mazeSize - 1) ? maze[i].push_back(WALL) : maze[i].push_back(PATH);
    maze[start.x][start.y] = maze[end.x][end.y] = PATH;

    // 生成迷宫（迭代和非迭代二选一生成）
    Division_generator(1, mazeSize - 2, 1, mazeSize - 2, maze);
    // Division_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;
}
View Code

 

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

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

　　　　　　　　

　　　　b、构建一墙一通路形式

　　　　　　　　

　　　　c、随机选择一个通路，并将周围墙入容器，标记该通路

　　　　　　　　

　　　　d、在墙容器中随机选取一堵墙，如果墙两边的通路没有同时被标记，则打通该墙，并将原来未被标记的通路周围的墙加入容器，然后将该通路标记，最后移除该墙

　　　　　　　　　　

　　　　e、重复操作 d，直到墙容器为空，说明该算法完成，最后将被标记的通路清除标记

至此，随机 Prim 挖墙算法讲解结束

看看该算法下生成的迷宫形态吧（由 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 Prim_generator(std::vector<std::vector<int>>& maze)
{
    // 构建墙隔开通路的迷宫，奇数点为通路
    for (int i = 1; i <= mazeSize - 2; i += 2)
        for (int j = 1; j <= mazeSize - 2; j += 2)
            maze[i][j] = PATH;
    // 维护一个墙容器
    std::vector<Point2> vp;
    // 先随机找一个通路
    Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1);
    // 将周围墙入栈
    if (temp.x - 1 >= 2) vp.push_back(Point2(temp.x - 1, temp.y));
    if (temp.x + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x + 1, temp.y));
    if (temp.y - 1 >= 2) vp.push_back(Point2(temp.x, temp.y - 1));
    if (temp.y + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x, temp.y + 1));
    // 标记该通路
    maze[temp.x][temp.y] = FLAG;
    int pos = 0;
    // 后续迭代生成迷宫
    while (!vp.empty())
    {
        // 在墙容器中随机选取一堵墙
        pos = rand() % vp.size();
        temp = vp[pos];
        // 记录该墙是否打通
        bool flag = false;
        // 后续 if else 判断墙所隔离通路在左右还是上下，并判断是否打通
        if (maze[temp.x + 1][temp.y] == WALL)
        {
            if (maze[temp.x][temp.y - 1] != maze[temp.x][temp.y + 1])
            {
                maze[temp.x][temp.y] = PATH;
                // 对新加入的通路进行标记
                if (maze[temp.x][temp.y - 1] == FLAG) { maze[temp.x][temp.y + 1] = FLAG; ++temp.y; }
                else { maze[temp.x][temp.y - 1] = FLAG; --temp.y; }
                flag = true;
            }
        }
        else
        {
            if (maze[temp.x - 1][temp.y] != maze[temp.x + 1][temp.y])
            {
                maze[temp.x][temp.y] = PATH;
                // 对新加入的通路进行标记
                if (maze[temp.x - 1][temp.y] == FLAG) { maze[temp.x + 1][temp.y] = FLAG; ++temp.x; }
                else { maze[temp.x - 1][temp.y] = FLAG; --temp.x; }
                flag = true;
            }
        }
        // 如果打通了墙，将进加入的通路周围的墙入容器
        if (flag)
        {
            if (temp.x - 1 >= 2 && maze[temp.x - 1][temp.y] == WALL) vp.push_back(Point2(temp.x - 1, temp.y));
            if (temp.x + 1 <= mazeSize - 3 && maze[temp.x + 1][temp.y] == WALL) vp.push_back(Point2(temp.x + 1, temp.y));
            if (temp.y - 1 >= 2 && maze[temp.x][temp.y - 1] == WALL) vp.push_back(Point2(temp.x, temp.y - 1));
            if (temp.y + 1 <= mazeSize - 3 && maze[temp.x][temp.y + 1] == WALL) vp.push_back(Point2(temp.x, temp.y + 1));
        }
        // 移除该墙
        vp[pos] = *(vp.end() - 1);
        vp.pop_back();
    }
    // 将被标记的通路还原
    for (auto& v1 : maze)
        for (auto& v2 : v1)
            if (v2 == FLAG) v2 = PATH;
}


// 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;

    // 生成迷宫
    Prim_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;
}
View Code

 

 

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

// 至此，以上三种迷宫生成算法讲解完成。这三种方式生成的迷宫形态有较大差异，需针对不同的游戏进行适当的选择，另外，对于不同的场景应灵活应用。

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

 

 

二、两种迷宫寻路算法（后文的迷宫默认使用前文中 随机 Prim 算法 所生成的迷宫）

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

　　　　该寻路方法，应该算是入门级算法了，学习数据结构栈时一般就会接触该算法。

　　　　从起点开始，将当前点入栈，向某一方向前进。若周围方向均不能继续前进，则回退，直到找到终点或栈为空。

看看 随机Prin生成 并在该算法下寻路后的迷宫形态吧（由 EasyX 库绘制）：

　　　　　　　　

源码（该代码中使用 std::list 实现栈并在寻路后返回 std::list。另：注释 EasyX 的地方是用 EasyX 绘图，如果不会 EasyX 请删除相关代码）：

#include <iostream>
#include <ctime>
#include <list>
#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) {}
    bool operator == (const Point2& p2) { return x == p2.x && y == p2.y; }
};

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


// 迷宫生成接口
void Prim_generator(std::vector<std::vector<int>>& maze)
{
    // 构建墙隔开通路的迷宫，奇数点为通路
    for (int i = 1; i <= mazeSize - 2; i += 2)
        for (int j = 1; j <= mazeSize - 2; j += 2)
            maze[i][j] = PATH;
    // 维护一个墙容器
    std::vector<Point2> vp;
    // 先随机找一个通路
    Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1);
    // 将周围墙入栈
    if (temp.x - 1 >= 2) vp.push_back(Point2(temp.x - 1, temp.y));
    if (temp.x + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x + 1, temp.y));
    if (temp.y - 1 >= 2) vp.push_back(Point2(temp.x, temp.y - 1));
    if (temp.y + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x, temp.y + 1));
    // 标记该通路
    maze[temp.x][temp.y] = FLAG;
    int pos = 0;
    // 后续迭代生成迷宫
    while (!vp.empty())
    {
        // 在墙容器中随机选取一堵墙
        pos = rand() % vp.size();
        temp = vp[pos];
        // 记录该墙是否打通
        bool flag = false;
        // 后续 if else 判断墙所隔离通路在左右还是上下，并判断是否打通
        if (maze[temp.x + 1][temp.y] == WALL)
        {
            if (maze[temp.x][temp.y - 1] != maze[temp.x][temp.y + 1])
            {
                maze[temp.x][temp.y] = PATH;
                // 对新加入的通路进行标记
                if (maze[temp.x][temp.y - 1] == FLAG) { maze[temp.x][temp.y + 1] = FLAG; ++temp.y; }
                else { maze[temp.x][temp.y - 1] = FLAG; --temp.y; }
                flag = true;
            }
        }
        else
        {
            if (maze[temp.x - 1][temp.y] != maze[temp.x + 1][temp.y])
            {
                maze[temp.x][temp.y] = PATH;
                // 对新加入的通路进行标记
                if (maze[temp.x - 1][temp.y] == FLAG) { maze[temp.x + 1][temp.y] = FLAG; ++temp.x; }
                else { maze[temp.x - 1][temp.y] = FLAG; --temp.x; }
                flag = true;
            }
        }
        // 如果打通了墙，将进加入的通路周围的墙入容器
        if (flag)
        {
            if (temp.x - 1 >= 2 && maze[temp.x - 1][temp.y] == WALL) vp.push_back(Point2(temp.x - 1, temp.y));
            if (temp.x + 1 <= mazeSize - 3 && maze[temp.x + 1][temp.y] == WALL) vp.push_back(Point2(temp.x + 1, temp.y));
            if (temp.y - 1 >= 2 && maze[temp.x][temp.y - 1] == WALL) vp.push_back(Point2(temp.x, temp.y - 1));
            if (temp.y + 1 <= mazeSize - 3 && maze[temp.x][temp.y + 1] == WALL) vp.push_back(Point2(temp.x, temp.y + 1));
        }
        // 移除该墙
        vp[pos] = *(vp.end() - 1);
        vp.pop_back();
    }
    // 将被标记的通路还原
    for (auto& v1 : maze)
        for (auto& v2 : v1)
            if (v2 == FLAG) v2 = PATH;
}

// DFS 寻路
std::list<Point2> DFS_find(const Point2& start, const Point2& end, std::vector<std::vector<int>>& maze)
{
    // 定义方向容器（右、下、左、上）
    std::vector<std::vector<int>> dir{ {1,0},{0,1},{-1,0},{0,-1} };
    // 定义栈容器
    std::list<Point2> sp;
    Point2 temp = start;
    sp.push_back(temp);
    // 与生成算法相似，迭代 DFS 遍历
    while (!sp.empty())
    {
        int i = 0;
        // 若可向其他方向前进，则继续
        for (; i < 4; ++i)
        {
            if (temp.x + dir[i][0] >= 0 && temp.x + dir[i][0] <= mazeSize - 1 && temp.y + dir[i][1] >= 0 && temp.y + dir[i][1] <= mazeSize - 1
                && maze[temp.x + dir[i][0]][temp.y + dir[i][1]] == PATH)
            {
                // 对走过的路进行标记
                maze[temp.x][temp.y] = FLAG;
                temp.x += dir[i][0];
                temp.y += dir[i][1];
                sp.push_back(temp);
                if (temp == end) return sp;
                break;
            }
        }
        // 无路可走时回溯
        if (i == 4)
        {
            maze[temp.x][temp.y] = FLAG;
            sp.pop_back();
            if (!sp.empty()) temp = sp.back();
        }
    }
    // 将被标记的通路还原
    for (auto& v1 : maze)
        for (auto& v2 : v1)
            if (v2 == FLAG) v2 = PATH;

    return sp;
}


// 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;

    // 生成迷宫
    Prim_generator(maze);

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

    // 寻路
    auto sp = DFS_find(start, end, maze);
    // 打印路径
    cout << endl << "寻路路径：" << endl;
    int i = 0;
    for (auto p2 : sp)
    {
        if (i++ == 5)
        {
            i = 0;
            cout << "(" << p2.x << ", " << p2.y << ")" << endl;
            continue;
        }
        cout << "(" << p2.x << ", " << p2.y << ")" << "、";
    }
    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);
        setfillcolor(YELLOW);
        for (auto p2 : sp) fillrectangle(p2.x * width, p2.y * width, p2.x * width + width - 1, p2.y * width + width - 1);
        // saveimage(_T("D:\\maze.png"));
        ret = _getwch();
        closegraph();
    }

    return 0;
}
View Code

 

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

　　　　讲解 A* 寻路算法的文章很多，笔者就不再重复造轮子了

　　　　这里推荐程序员小灰的文章：https://mp.weixin.qq.com/s/FYKR_1yBKR4GJTn0fFIuAA

一些说明：

　　　　1、用 F 值评估最短路径，公式 F = G + H

　　　　2、G 代表从起点走到当前点的步数，在代码中等于 父节点 的 G 值加 1

　　　　3、H 值是当前点到终点距离的评估，可简单认为是无阻碍时到终点所需的步数 |dx| + |dy|

　　　　4、openList 和 closeList 应该如何选用容器？

　　　　　　closeList：只需要将节点加入而不需要其他操作，因此可以使用 vector，list 等容器

　　　　　　openList：由于需要从该容器中取出 F 值最小的节点，因此可以考虑使用能够自排序的容器，如 priority_queue，multiset 等

　　　　　　本文使用 list 及 multiset 来实现，且从终点向起点寻路，最终返回一个包含寻路路径的 list 容器

看看 随机Prin生成 并在该算法下寻路后的迷宫形态吧（由 EasyX 库绘制）：

　　　　　　　　

源码（注：注释 EasyX 的地方是用 EasyX 绘图，如果不会 EasyX 请删除相关代码）：

#include <iostream>
#include <ctime>
#include <set>
#include <list>
#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) {}
    bool operator == (const Point2& p2) const { return x == p2.x && y == p2.y; }
};

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


// 迷宫生成接口
void Prim_generator(std::vector<std::vector<int>>& maze)
{
    // 构建墙隔开通路的迷宫，奇数点为通路
    for (int i = 1; i <= mazeSize - 2; i += 2)
        for (int j = 1; j <= mazeSize - 2; j += 2)
            maze[i][j] = PATH;
    // 维护一个墙容器
    std::vector<Point2> vp;
    // 先随机找一个通路
    Point2 temp((rand() % (mazeSize - 2) + 1) | 1, (rand() % (mazeSize - 2) + 1) | 1);
    // 将周围墙入栈
    if (temp.x - 1 >= 2) vp.push_back(Point2(temp.x - 1, temp.y));
    if (temp.x + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x + 1, temp.y));
    if (temp.y - 1 >= 2) vp.push_back(Point2(temp.x, temp.y - 1));
    if (temp.y + 1 <= mazeSize - 3) vp.push_back(Point2(temp.x, temp.y + 1));
    // 标记该通路
    maze[temp.x][temp.y] = FLAG;
    int pos = 0;
    // 后续迭代生成迷宫
    while (!vp.empty())
    {
        // 在墙容器中随机选取一堵墙
        pos = rand() % vp.size();
        temp = vp[pos];
        // 记录该墙是否打通
        bool flag = false;
        // 后续 if else 判断墙所隔离通路在左右还是上下，并判断是否打通
        if (maze[temp.x + 1][temp.y] == WALL)
        {
            if (maze[temp.x][temp.y - 1] != maze[temp.x][temp.y + 1])
            {
                maze[temp.x][temp.y] = PATH;
                // 对新加入的通路进行标记
                if (maze[temp.x][temp.y - 1] == FLAG) { maze[temp.x][temp.y + 1] = FLAG; ++temp.y; }
                else { maze[temp.x][temp.y - 1] = FLAG; --temp.y; }
                flag = true;
            }
        }
        else
        {
            if (maze[temp.x - 1][temp.y] != maze[temp.x + 1][temp.y])
            {
                maze[temp.x][temp.y] = PATH;
                // 对新加入的通路进行标记
                if (maze[temp.x - 1][temp.y] == FLAG) { maze[temp.x + 1][temp.y] = FLAG; ++temp.x; }
                else { maze[temp.x - 1][temp.y] = FLAG; --temp.x; }
                flag = true;
            }
        }
        // 如果打通了墙，将进加入的通路周围的墙入容器
        if (flag)
        {
            if (temp.x - 1 >= 2 && maze[temp.x - 1][temp.y] == WALL) vp.push_back(Point2(temp.x - 1, temp.y));
            if (temp.x + 1 <= mazeSize - 3 && maze[temp.x + 1][temp.y] == WALL) vp.push_back(Point2(temp.x + 1, temp.y));
            if (temp.y - 1 >= 2 && maze[temp.x][temp.y - 1] == WALL) vp.push_back(Point2(temp.x, temp.y - 1));
            if (temp.y + 1 <= mazeSize - 3 && maze[temp.x][temp.y + 1] == WALL) vp.push_back(Point2(temp.x, temp.y + 1));
        }
        // 移除该墙
        vp[pos] = *(vp.end() - 1);
        vp.pop_back();
    }
    // 将被标记的通路还原
    for (auto& v1 : maze)
        for (auto& v2 : v1)
            if (v2 == FLAG) v2 = PATH;
}

// A*寻路容器
class A_Container
{
    struct Node
    {
        Point2 p2;
        int gVal, hVal, fVal;
        Node* parent;
        Node(const Point2& _p2, int _g, int _h, Node* _p) :p2(_p2), gVal(_g), hVal(_h), fVal(_g + _h), parent(_p) {}
    };

public:
    A_Container(const Point2& _start) :destPos(_start) {}
    ~A_Container()
    {
        for (auto& no : openList) delete no;
        for (auto& no : closeList) delete no;
    }

    // 将节点加入 openList
    void pushOpenList(const Point2& _p2)
    {
        int gVal = 0;
        Node* par = nullptr;
        if (!closeList.empty()) { par = *(--closeList.end()); gVal = par->gVal + 1; }
        Node* temp = new Node(_p2, gVal, abs(_p2.x - destPos.x) + abs(_p2.y - destPos.y), par);
        if (_p2.x == destPos.x && _p2.y == destPos.y) p_destNode = temp;
        openList.insert(temp);
        temp = nullptr;
    }

    // 从 openList 中取出 fVal 值最小的节点加入 closeList
    auto getMinNode()
    {
        auto it = openList.begin();
        Point2 ret = (*it)->p2;
        closeList.push_back(*it);
        openList.erase(it);
        return ret;
    }

    // 获取寻路终点，用于回溯得到最短路径
    Node* getDestNode() { return p_destNode; }

    // 用于 multiset 比较 的函数对象
    struct Compare
    {
        bool operator ()(const Node* _n1, const Node* _n2) const { return _n1->fVal < _n2->fVal; }
    };

private:
    Point2 destPos;                                // 目标位置
    std::list<Node*> closeList;                    // closeList 容器
    std::multiset<Node*, Compare> openList;        // openList 自动排序
    Node* p_destNode = nullptr;                    // 用于返回终点的位置指针
};

// A* 寻路
list<Point2> A_find(const Point2& start, const Point2& end, std::vector<std::vector<int>>& maze)
{
    // 从目标位置开始寻找起点，之后回溯即可得到起点到终点的路径
    Point2 temp = end;
    // 创建高效容器
    A_Container cont(start);
    // 将目标位置加入 openList
    cont.pushOpenList(temp);
    // 后续迭代进行，根据 A* 寻路规则，利用高效容器寻找最短路径
    while (true)
    {
        // 将 openList 中 F 值最小的节点放到 closeList 中
        temp = cont.getMinNode();
        // 标记节点加入到 openList 中的节点
        maze[temp.x][temp.y] = FLAG;
        // 后续 if 将周围通路加入 openList
        if (temp.x - 1 >= 0 && maze[temp.x - 1][temp.y] == PATH)
        {
            maze[temp.x - 1][temp.y] = FLAG;
            cont.pushOpenList(Point2(temp.x - 1, temp.y));
            if (start == Point2(temp.x - 1, temp.y)) break;
        }
        if (temp.y - 1 >= 0 && maze[temp.x][temp.y - 1] == PATH)
        {
            maze[temp.x][temp.y - 1] = FLAG;
            cont.pushOpenList(Point2(temp.x, temp.y - 1));
            if (start == Point2(temp.x, temp.y - 1)) break;
        }
        if (temp.x + 1 <= mazeSize - 1 && maze[temp.x + 1][temp.y] == PATH)
        {
            maze[temp.x + 1][temp.y] = FLAG;
            cont.pushOpenList(Point2(temp.x + 1, temp.y));
            if (start == Point2(temp.x + 1, temp.y)) break;
        }
        if (temp.y + 1 <= mazeSize - 1 && maze[temp.x][temp.y + 1] == PATH)
        {
            maze[temp.x][temp.y + 1] = FLAG;
            cont.pushOpenList(Point2(temp.x, temp.y + 1));
            if (start == Point2(temp.x, temp.y + 1)) break;
        }
    }
    // 将被标记的通路还原
    for (auto& v1 : maze)
        for (auto& v2 : v1)
            if (v2 == FLAG) v2 = PATH;
    // 找到起点后，获取高效容器中的起点，回溯得到最短路径
    auto st = cont.getDestNode();
    list<Point2> retList;
    while (st != nullptr)
    {
        retList.push_back({ st->p2 });
        st = st->parent;
    }
    return retList;
}


// 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;

    // 生成迷宫
    Prim_generator(maze);

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

    // 寻路
    auto sp = A_find(end, start, maze);
    // 打印路径
    cout << endl << "寻路路径：" << endl;
    int i = 0;
    for (auto p2 : sp)
    {
        if (i++ == 5)
        {
            i = 0;
            cout << "(" << p2.x << ", " << p2.y << ")" << endl;
            continue;
        }
        cout << "(" << p2.x << ", " << p2.y << ")" << "、";
    }
    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);
        setfillcolor(YELLOW);
        for (auto p2 : sp) fillrectangle(p2.x * width, p2.y * width, p2.x * width + width - 1, p2.y * width + width - 1);
        // saveimage(_T("D:\\maze.png"));
        ret = _getwch();
        closegraph();
    }

    return 0;
}
View Code

 

至此，迷宫生成算法及迷宫寻路算法已讲述完毕。以 EasyX 制作的迷宫算法可视化程序，如有需要请移步：https://codebus.cn/teternity/post/MazeAlgorithm

 


原文链接:https://www.cnblogs.com/teternity/p/MazeAlgorithm.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：用C++实现：回形取数

下一篇：C++ 多态

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签