简单的迷宫生成算法 – 使用C++与EasyX生成迷宫

迷宫生成算法

这是一个非常朴素的迷宫生成算法,首先假设迷宫是由M×N个房间构成的,在一开始,每个房间与其周围房间都隔着一堵墙。

生成迷宫的方式就是通过砸开一部分墙,使所有的房间连通,我们假设有一个小人在这个迷宫里,他只能砸开自己所处房间四面的墙,从而进入下一个房间,而在这个过程中,他需要遵循以下三个条件:

  • 只有当隔壁房间没有去过的时候,墙才可以砸
  • 无墙可砸的时候,就随机传送到一个去过的房间
  • 每一个房间都要到达

这样一个普通的迷宫就产生了,小人需要砸掉M×N-1面墙,且保证迷宫有且仅有一个解。

关于算法的详细讲解可以看B站视频 从迷宫生成算法到创意编程

使用C++生成迷宫

程序分为三部分:

  • 生成迷宫
  • 绘制迷宫
  • 进度条

我定义了一个结构体Move,表示上左右下四个方向

struct {
    int x[4] = {-1, 0, 0, 1};
    int y[4] = {0, -1, 1, 0};
} Move; //up left right down

迷宫则用三维数组 maze[M][N][4] 表示,其中第三个维度表示当前房间四面有没有墙。

生成迷宫

遵循上述原则生成,使用 visited 二维数组记录每个房间有没有访问。

[warning]这鬼东西代码语言识别不出C++真是太离谱了[/warning]

#define random(x) (rand()%(x))
void generate() {
    srand((int) time(nullptr));
    int x = 0, y = 0;
    for (int cnt = 0; cnt < M * N - 1; cnt++) {
        loading(cnt);
        visited[x][y] = 1;
        vector<int> v;
        if (x - 1 >= 0 && !visited[x - 1][y]) v.push_back(0);
        if (y - 1 >= 0 && !visited[x][y - 1]) v.push_back(1);
        if (y + 1 < N && !visited[x][y + 1]) v.push_back(2);
        if (x + 1 < M && !visited[x + 1][y]) v.push_back(3);
        if (v.empty() || (x == M - 1 && y == N - 1)) {
            v.clear();
            vector<pair<int, int>> notVisited;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && ((i - 1 >= 0 && visited[i - 1][j]) || (j - 1 >= 0 && visited[i][j - 1]) ||
 (j + 1 < N && visited[i][j + 1]) || (i + 1 < M && visited[i + 1][j])))
                        notVisited.emplace_back(i, j);
                }
            }
            int r = random(notVisited.size());
            x = notVisited[r].first;
            y = notVisited[r].second;
            if (x - 1 >= 0 && visited[x - 1][y]) v.push_back(0);
            if (y - 1 >= 0 && visited[x][y - 1]) v.push_back(1);
            if (y + 1 < N && visited[x][y + 1]) v.push_back(2);
            if (x + 1 < M && visited[x + 1][y]) v.push_back(3);
            r = random(v.size());
            maze[x][y][v[r]] = 1;
            maze[x + Move.x[v[r]]][y + Move.y[v[r]]][3 - v[r]] = 1;
        } else {
            int r = random(v.size()); // NOLINT(cert-msc50-cpp)
            maze[x][y][v[r]] = 1;
            x += Move.x[v[r]];
            y += Move.y[v[r]];
            maze[x][y][3 - v[r]] = 1;
        }
    }
}

绘制迷宫

与迷宫生成方式相同,首先绘制出全部墙面,再擦除需要拆掉的墙。使用EasyX绘制,保存为 .tif 图片至本地。
MAP_SIZE 为一个房间边长的像素数。

void draw() {
    initgraph(MAP_SIZE * (N + 2) + 1, MAP_SIZE * (M + 2) + 1);
    for (int i = 1; i <= M + 1; i++) line(MAP_SIZE, MAP_SIZE * i, MAP_SIZE * (N + 1) + 1, MAP_SIZE * i);
    for (int i = 1; i <= N + 1; i++) line(MAP_SIZE * i, MAP_SIZE, MAP_SIZE * i, MAP_SIZE * (M + 1) + 1);
    setlinecolor(BLACK);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (maze[i][j][0])
                line(MAP_SIZE * (j + 1) + 1, MAP_SIZE * (i + 1), MAP_SIZE * (j + 2) - 1, MAP_SIZE * (i + 1));
            if (maze[i][j][1])
                line(MAP_SIZE * (j + 1), MAP_SIZE * (i + 1) + 1, MAP_SIZE * (j + 1), MAP_SIZE * (i + 2) - 1);
            if (maze[i][j][2])
                line(MAP_SIZE * (j + 2), MAP_SIZE * (i + 1) + 1, MAP_SIZE * (j + 2), MAP_SIZE * (i + 2) - 1);
            if (maze[i][j][3])
                line(MAP_SIZE * (j + 1) + 1, MAP_SIZE * (i + 2), MAP_SIZE * (j + 2) - 1, MAP_SIZE * (i + 2));
        }
    }
    saveimage(_T("maze.tif"));
}

进度条

由于算法十分简陋,在生成大迷宫的时候需要耗费大量时间,为了显示电脑并没有死机,便加入了一个进度显示。

void loading(int cnt) {
    int x;
    if (((cnt + 2) * 100) % (M * N) == 0) {
        x = ((cnt + 2) * 100) / (M * N);
        cout << "[";
        for (int i = 1; i <= x / 2; i++) cout << "=";
        if (x % 2 == 1) cout << "-";
        for (int i = 50; i > (x + 1) / 2; i--) cout << " ";
        cout << "] " << x << "%" << endl;
    }
}

完整代码

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <utility>
#include <graphics.h>

#define random(x) (rand()%(x))
using namespace std;
const int M = 10;
const int N = 10;
const int MAP_SIZE = 50;
struct {
    int x[4] = {-1, 0, 0, 1};
    int y[4] = {0, -1, 1, 0};
} Move; //up left right down
int maze[M][N][4], visited[M][N];

void generate();

void draw();

void loading(int);

int main() {
    generate();
    draw();
    return 0;
}

void generate() {
    srand((int) time(nullptr));
    int x = 0, y = 0;
    for (int cnt = 0; cnt < M * N - 1; cnt++) {
        loading(cnt);
        visited[x][y] = 1;
        vector<int> v;
        if (x - 1 >= 0 && !visited[x - 1][y]) v.push_back(0);
        if (y - 1 >= 0 && !visited[x][y - 1]) v.push_back(1);
        if (y + 1 < N && !visited[x][y + 1]) v.push_back(2);
        if (x + 1 < M && !visited[x + 1][y]) v.push_back(3);
        if (v.empty() || (x == M - 1 && y == N - 1)) {
            v.clear();
            vector<pair<int, int>> notVisited;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && ((i - 1 >= 0 && visited[i - 1][j]) || (j - 1 >= 0 && visited[i][j - 1]) ||
                                           (j + 1 < N && visited[i][j + 1]) || (i + 1 < M && visited[i + 1][j])))
                        notVisited.emplace_back(i, j);
                }
            }
            int r = random(notVisited.size()); // NOLINT(cert-msc50-cpp)
            x = notVisited[r].first;
            y = notVisited[r].second;
            if (x - 1 >= 0 && visited[x - 1][y]) v.push_back(0);
            if (y - 1 >= 0 && visited[x][y - 1]) v.push_back(1);
            if (y + 1 < N && visited[x][y + 1]) v.push_back(2);
            if (x + 1 < M && visited[x + 1][y]) v.push_back(3);
            r = random(v.size());
            maze[x][y][v[r]] = 1;
            maze[x + Move.x[v[r]]][y + Move.y[v[r]]][3 - v[r]] = 1;
        } else {
            int r = random(v.size());
            maze[x][y][v[r]] = 1;
            x += Move.x[v[r]];
            y += Move.y[v[r]];
            maze[x][y][3 - v[r]] = 1;
        }
    }
}

void loading(int cnt) {
    int x;
    if (((cnt + 2) * 100) % (M * N) == 0) {
        x = ((cnt + 2) * 100) / (M * N);
        cout << "[";
        for (int i = 1; i <= x / 2; i++) cout << "=";
        if (x % 2 == 1) cout << "-";
        for (int i = 50; i > (x + 1) / 2; i--) cout << " ";
        cout << "] " << x << "%" << endl;
    }
}

void draw() {
    initgraph(MAP_SIZE * (N + 2) + 1, MAP_SIZE * (M + 2) + 1);
    for (int i = 1; i <= M + 1; i++) line(MAP_SIZE, MAP_SIZE * i, MAP_SIZE * (N + 1) + 1, MAP_SIZE * i);
    for (int i = 1; i <= N + 1; i++) line(MAP_SIZE * i, MAP_SIZE, MAP_SIZE * i, MAP_SIZE * (M + 1) + 1);
    setlinecolor(BLACK);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (maze[i][j][0])
                line(MAP_SIZE * (j + 1) + 1, MAP_SIZE * (i + 1), MAP_SIZE * (j + 2) - 1, MAP_SIZE * (i + 1));
            if (maze[i][j][1])
                line(MAP_SIZE * (j + 1), MAP_SIZE * (i + 1) + 1, MAP_SIZE * (j + 1), MAP_SIZE * (i + 2) - 1);
            if (maze[i][j][2])
                line(MAP_SIZE * (j + 2), MAP_SIZE * (i + 1) + 1, MAP_SIZE * (j + 2), MAP_SIZE * (i + 2) - 1);
            if (maze[i][j][3])
                line(MAP_SIZE * (j + 1) + 1, MAP_SIZE * (i + 2), MAP_SIZE * (j + 2) - 1, MAP_SIZE * (i + 2));
        }
    }
    saveimage(_T("maze.tif"));
}

效果图

1000×1000的迷宫,看不清可以电脑保存到本地放大看(

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇