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

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++ 多态