答案：使用DFS结合随机性生成迷宫，从起点开始标记访问，随机打乱方向顺序，打通相邻未访问格子间的墙并递归探索，最终形成连通无环的迷宫结构。
用深度优先搜索（DFS）结合随机性来生成迷宫，是一种常见且效果不错的算法。核心思路是模拟“回溯探索”的过程，从起点出发，随机选择未访问的方向前进，打通墙壁，直到所有格子都被访问过，形成一个连通无环的迷宫。
算法基本原理
将迷宫看作一个二维网格，每个格子是一个“房间”。通过打破格子之间的墙来连接它们。使用深度优先搜索，但每次选择下一个方向时采用随机顺序，这样可以生成结构多变的迷宫。
关键点：
从任意起点开始（通常选左上角） 标记当前格子为已访问 随机打乱上下左右四个方向的探索顺序 对每个方向，若相邻格子未访问，则打通中间的墙，递归进入该格子 使用栈或递归实现回溯
代码实现（递归版本）
#include #include #include #include #include using namespace std;const int WIDTH = 21; // 宽度必须为奇数，方便表示墙和格子const int HEIGHT = 21; // 高度也必须为奇数vector<vector> visited(HEIGHT, vector(WIDTH, false));vector<vector> maze(HEIGHT, vector(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 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 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;}
关键细节说明
网格尺寸为何是奇数？ 因为每个格子之间有墙，若用 21×21 的网格，实际表示 10×10 个房间，墙和通路交错分布。坐标 (1,1)、(1,3) 等为房间位置，偶数坐标多为墙。
立即学习“C++免费学习笔记（深入）”；
如何打通墙？ 从 (x,y) 走到 (x+2,y)，中间墙在 (x+1,y)，所以将该位置设为 false。
random_shuffle 提升随机性 每次随机打乱方向顺序，避免固定模式，让迷宫更自然。
递归深度问题 大迷宫可能导致栈溢出。可改用显式栈迭代实现，逻辑一致但更安全。
基本上就这些。算法简单，生成的迷宫连通性好，适合游戏或演示使用。
以上就是C++迷宫生成算法 深度优先随机生成的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1472998.html
微信扫一扫 
支付宝扫一扫 
