用C++实现迷宫生成器，核心任务并不是画图，而是构建一个由单元格和墙组成的网格模型，然后通过遍历算法决定哪些墙应该打通。深度优先搜索配合递归回溯能够生成“完美迷宫”——任意两个格子之间有且仅有一条通路，没有环路，也没有孤立区域。这种算法的实现量小、代码直观，非常适合用来练习递归、随机化和二维数组操作。

一、从网格到数据结构：迷宫模型设计

迷宫可以抽象为一个二维网格，每个格子称为一个单元格，单元格与上下左右四个邻居之间各有一堵墙。生成算法的任务就是遍历这些单元格，并在合适的时机把相邻单元格之间的墙拆掉，从而形成一条条通路。用C++表达这种结构时，最直接的方法是使用struct保存每个单元格的状态：一个布尔数组记录四面墙是否还存在，另一个布尔变量标记该格子是否已经被访问过。

墙的编号需要和方向数组严格对应，否则在打通墙壁时容易出现逻辑错误。例如将上下左右四个方向分别编号为0、1、2、3，那么walls[0]就表示当前格子的上墙，walls[1]表示下墙，walls[2]表示左墙，walls[3]表示右墙。当从当前格子向上移动到邻居格子时，需要同时拆掉当前格子的上墙和邻居格子的下墙，这样才能形成双向通路。这样做的好处是迷宫数据独立于渲染方式，之后无论是输出到控制台、画布还是文件，都只需要读取每个格子的墙状态即可。

存储上使用std::vector嵌套std::vector是比较方便的选择。行数对应高度，列数对应宽度，访问坐标为grid[y][x]。如果迷宫规模非常大，也可以考虑将墙状态压缩到一个整数位中，但初学阶段直接使用结构体数组更清晰，而且现代计算机内存足够承载数万规模的网格。

二、深度优先搜索与递归回溯原理

深度优先搜索生成迷宫的基本流程是：从起始格子出发，把当前格子标记为已访问，然后在四个方向中随机选择一个尚未访问的邻居。如果存在这样的邻居，就打通当前格子与邻居之间的墙，并递归进入邻居格子继续探索。如果四个方向都已经被访问过，则返回到上一个格子，再从上一个格子剩余的方向中继续尝试。这个过程不断重复，直到所有格子都被访问完毕。

这个算法生成的迷宫有一个显著特点：路径通常蜿蜒曲折，长通道较多，分支相对较少。原因在于DFS会沿着一个随机方向尽可能深入，直到撞到已访问区域或边界才回溯。递归调用栈天然承担了回溯路径的记录工作，不需要手动维护栈。不过递归深度在最坏情况下可能接近单元格总数，当迷宫非常大时，存在栈溢出的风险。此时可以显式使用std::stack保存待处理的格子，将递归改写为迭代版本，逻辑完全一致但更安全。

随机性是保证每次生成结果不同的关键。简单做法是使用rand()配合srand(time(nullptr))，但rand()的随机质量一般，且在部分平台上范围不够均匀。更推荐使用C++11引入的std::mt19937和std::random_device，配合std::shuffle对方向数组进行随机排序。这样每次进入一个新的格子时，四个方向的尝试顺序都是随机的，迷宫形态不会出现固定模式。

三、C++完整实现与关键细节

下面给出一个可在控制台输出迷宫的可运行示例。代码中定义了Cell结构体表示单元格，Maze类负责生成和打印。生成过程使用递归DFS，打印部分将上墙和左墙转换为字符画，这样不需要额外处理右墙和下墙，因为它们会被右侧和下方格子的左墙、上墙自然表示。

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <random>
struct Cell {
    bool walls[4] = {true, true, true, true}; // 上 下 左 右
    bool visited = false;
};
class Maze {
public:
    Maze(int w, int h) : width(w), height(h), grid(h, std::vector<Cell>(w)) {}
    void generate(int startX, int startY) {
        std::srand(static_cast<unsigned int>(std::time(nullptr)));
        dfs(startX, startY);
    }
    void print() const {
        for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width; ++x) {
                std::cout << (grid[y][x].walls[0] ? "+---" : "+   ");
            }
            std::cout << "+\n";
            for (int x = 0; x < width; ++x) {
                std::cout << (grid[y][x].walls[2] ? "|   " : "    ");
            }
            std::cout << "|\n";
        }
        for (int x = 0; x < width; ++x) {
            std::cout << "+---";
        }
        std::cout << "+\n";
    }
private:
    int width, height;
    std::vector<std::vector<Cell>> grid;
    const int dx[4] = {0, 0, -1, 1}; // 上 下 左 右
    const int dy[4] = {-1, 1, 0, 0};
    const int opposite[4] = {1, 0, 3, 2};
    bool inBounds(int x, int y) const {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
    void dfs(int cx, int cy) {
        grid[cy][cx].visited = true;
        std::vector<int> dirs = {0, 1, 2, 3};
        std::shuffle(dirs.begin(), dirs.end(), std::mt19937(std::random_device()()));
        for (int dir : dirs) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if (inBounds(nx, ny) && !grid[ny][nx].visited) {
                grid[cy][cx].walls[dir] = false;
                grid[ny][nx].walls[opposite[dir]] = false;
                dfs(nx, ny);
            }
        }
    }
};
int main() {
    Maze maze(20, 10);
    maze.generate(0, 0);
    maze.print();
    return 0;
}

代码中opposite数组用来快速获取相对方向：上对下、下对上、左对右、右对左。拆墙时必须同时修改两个格子，否则会出现单向通路，后续遍历可能产生逻辑冲突。边界判断inBounds防止访问越界，这是所有二维网格操作中必须优先处理的细节。另外，随机数生成器的种子可以在main函数中设置一次，而不建议放在递归函数内部重复初始化，那样既降低效率又可能因为时间种子相同导致随机序列重复。

从输出结果可以看到，迷宫的外边界始终保持闭合，内部则根据DFS的访问顺序形成不规则的通道。如果希望指定入口和出口，可以在生成完成后额外打通起点上方或终点的某一面外墙，具体位置可以根据实际需求修改。

四、算法对比与可视化扩展

深度优先搜索并不是唯一能生成迷宫的算法。Prim算法从任意格子开始，维护一个候选墙列表，每次随机选择一堵连接已访问区域和未访问区域的墙并打通，然后把新格子加入已访问区域。Prim算法生成的迷宫通常分支更多，短通道更密集，整体形态像一堆不规则的树杈。Kruskal算法则把每堵墙看作一条边，随机选择边并合并不在同一集合中的格子，生成结果往往具有较多小环路的倾向，不过如果实现正确仍然可以生成完美迷宫。

如果想要直观比较不同算法的差异，可以将迷宫保存为PPM图片文件。PPM格式非常简单，只需要写入文件头、图像尺寸和每个像素的RGB值。也可以将字符画输出到文本文件，例如用#表示墙，空格表示通道，这样无需额外依赖即可查看结果。对于需要交互式展示的场景，可以考虑使用SDL、SFML或OpenGL绑定纹理，把每个格子的墙状态转换为绘制线段。

在扩展功能方面，可以为迷宫增加入口和出口标记，或者在生成完成后使用BFS计算起点到终点的最短路径，并高亮显示。DFS生成的迷宫路径虽然长，但最短路径仍然唯一且可求解。理解这种生成与求解之间的对偶关系，对学习图算法很有帮助。整个项目代码量不大，但覆盖了结构体设计、二维数组、递归回溯、随机数、边界检查和字符输出等多个重要知识点，适合作为C++练习项目反复改进。