如何用C++实现一个简单的迷宫生成算法

递归DFS生成矩形迷宫最直观可靠，天然保证连通性与路径唯一性；从起点随机挖墙、递归访问未访问邻格，用vector标记已打通格子，array存四方向并shuffle打乱顺序，遍历时严格检查边界。

用深度优先搜索（DFS）生成矩形迷宫最可靠

直接用递归 DFS 是最直观、最容易调试的方案，适合初学者快速得到可通行的迷宫。它天然保证连通性，且路径唯一——这点对后续寻路或解谜逻辑很关键。

核心思路：从起点开始，随机选一个未访问的邻接方向“挖墙”，递归进入新格子；回溯时记录路径，所有被访问过的格子构成主通道，其余为墙。

• std::vector<:vector>></:vector> 存储格子是否已访问（true 表示已打通）
• 四个方向用 std::array<:pair int>, 4></:pair> 预定义，每次 std::shuffle 打乱顺序再遍历
• 边界检查必须做：x >= 0 && x = 0 && y ，漏掉会越界崩溃
• 每步只打通当前格子和下一个格子之间的墙——也就是把两个格子中间那堵墙设为可通行（通常用二维字符数组或布尔网格表示）

用 Prim 算法生成更“自然”的迷宫

Prim 版本更适合想要分支多、死路少、视觉上更均匀的迷宫。它从单点出发，不断从“前沿”随机选一个边扩展，比 DFS 更难出现长直道。

关键不是堆或优先队列——这里用 std::vector 存储候选边即可，每次 rand() % edges.size() 随机取一个，性能完全够用。

立即学习“C++免费学习笔记（深入）”；

• 维护一个已访问集合（std::set<:pair int>></:pair> 或布尔网格）
• 每轮把新加入格子的未访问邻居作为候选边（{x, y, nx, ny}），注意去重
• 选中一条边后，把 nx, ny 加入已访问集，并打通 (x,y) 和 (nx,ny) 之间的墙
• 别忘了在加入邻居前检查是否已在已访问集中，否则会重复添加、导致冗余边

字符画输出时别忽略行列顺序和换行

用 std::cout 打印迷宫时，习惯性按 y 循环外层、x 内层，否则输出是转了 90° 的——这是 C++ 新手最常踩的坑。

• 假设迷宫数据存为 grid[y][x]（先行后列），打印时外层 for (int y = 0; y ，内层 <code>for (int x = 0; x
• 每个格子输出一个字符：' ' 表示通道，'#' 表示墙，别漏掉 std::cout 换行
• 如果用 std::string 拼接一行再输出，记得每行末尾加 "n"，不然全部挤在一行

生成后验证连通性避免“孤岛”

哪怕算法逻辑正确，边界条件写错（比如方向偏移算错、坐标没+1/-1）也会导致部分区域不可达。不验证就直接交给寻路模块，后面 debug 会非常痛苦。

• 用一次 BFS 或 DFS 从起点出发，统计能到达的格子数；若小于总通道数，说明有孤岛
• 起点建议固定为 (1, 1)（避开外围墙），终点可设为 (width-2, height-2)
• 验证时只走通道格子（grid[y][x] == false 或对应通道值），别误把墙当路
• 调试时可在验证失败后输出整个 grid 布局，肉眼找断点比纯逻辑推演快得多

真正麻烦的不是算法本身，而是方向向量写反、边界判断少等号、坐标系混淆这三类低级错误——它们不会报编译错误，但会让迷宫看起来“差不多”，实则无法通行。