欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-02-21 14:09:08
本文讲解迷宫生成和迷宫寻路算法。 //////////////////////////////////////////////////////////////////////////////////////////////////// 一、三种迷宫生成算法 1、 DFS(即深度优先)算法生成,分为递 ......

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

 

 

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

一、三种迷宫生成算法

    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、 十字分割算法生成(是一种十字补墙算法)

//

//