C++迷宫生成算法深度优先随机生成-C++-PHP中文网

C++迷宫生成算法深度优先随机生成

P粉602998670

发布： 2025-08-26 12:07:01

原创

804人浏览过

答案：使用DFS结合随机性生成迷宫，从起点开始标记访问，随机打乱方向顺序，打通相邻未访问格子间的墙并递归探索，最终形成连通无环的迷宫结构。

c++迷宫生成算法深度优先随机生成

用深度优先搜索（DFS）结合随机性来生成迷宫，是一种常见且效果不错的算法。核心思路是模拟“回溯探索”的过程，从起点出发，随机选择未访问的方向前进，打通墙壁，直到所有格子都被访问过，形成一个连通无环的迷宫。

算法基本原理

将迷宫看作一个二维网格，每个格子是一个“房间”。通过打破格子之间的墙来连接它们。使用深度优先搜索，但每次选择下一个方向时采用随机顺序，这样可以生成结构多变的迷宫。

关键点：

从任意起点开始（通常选左上角）
标记当前格子为已访问
随机打乱上下左右四个方向的探索顺序
对每个方向，若相邻格子未访问，则打通中间的墙，递归进入该格子
使用栈或递归实现回溯

代码实现（递归版本）

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

const int WIDTH = 21;  // 宽度必须为奇数，方便表示墙和格子
const int HEIGHT = 21; // 高度也必须为奇数

vector<vector<bool>> visited(HEIGHT, vector<bool>(WIDTH, false));
vector<vector<bool>> maze(HEIGHT, vector<bool>(WIDTH, true)); // true 表示墙

// 四个方向：上、右、下、左
int dx[4] = {0, 2, 0, -2};
int dy[4] = {-2, 0, 2, 0};

void generate(int x, int y) {
    visited[y][x] = true;
    maze[y][x] = false; // 当前格子设为通路

    // 定义方向索引并随机打乱
    vector<int> dirs = {0, 1, 2, 3};
    random_shuffle(dirs.begin(), dirs.end());

    for (int i : dirs) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx > 0 && nx < WIDTH-1 && ny > 0 && ny < HEIGHT-1 && !visited[ny][nx]) {
            maze[ny + dy[i]/2][nx + dx[i]/2] = false; // 打通中间墙
            generate(nx, ny);
        }
    }
}

void printMaze() {
    for (int i = 0; i < HEIGHT; ++i) {
        for (int j = 0; j < WIDTH; ++j) {
            cout << (maze[i][j] ? "#" : " ");
        }
        cout << endl;
    }
}

int main() {
    srand(time(0));

    // 起点设在 (1,1)
    generate(1, 1);

    // 可选：设置入口和出口
    maze[0][1] = false;
    maze[HEIGHT-1][WIDTH-2] = false;

    printMaze();

    return 0;
}

登录后复制