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

P粉602998670

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

825人浏览过

来源于php中文网

原创

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

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

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

算法基本原理

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

关键点：

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

代码实现（递归版本）

#include 
#include 
#include 
#include 
#include 

using namespace std;

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

vector> visited(HEIGHT, vector(WIDTH, false));
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 < 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;
}

关键细节说明

网格尺寸为何是奇数？ 因为每个格子之间有墙，若用 21x21 的网格，实际表示 10x10 个房间，墙和通路交错分布。坐标 (1,1)、(1,3) 等为房间位置，偶数坐标多为墙。

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

网趣网上购物系统HTML静态版

网趣购物系统静态版支持网站一键静态生成，采用动态进度条模式生成静态，生成过程更加清晰明确，商品管理上增加淘宝数据包导入功能，与淘宝数据同步更新!采用领先的AJAX+XML相融技术，速度更快更高效！系统进行了大量的实用性更新，如优化核心算法、增加商品图片批量上传、谷歌地图浏览插入等，静态版独特的生成算法技术使静态生成过程可随意掌控，从而可以大大减轻服务器的负担，结合多种强大的SEO优化方式于一体，使

下载

如何打通墙？ 从 (x,y) 走到 (x+2,y)，中间墙在 (x+1,y)，所以将该位置设为 false。

random_shuffle 提升随机性 每次随机打乱方向顺序，避免固定模式，让迷宫更自然。

递归深度问题 大迷宫可能导致栈溢出。可改用显式栈迭代实现，逻辑一致但更安全。

基本上就这些。算法简单，生成的迷宫连通性好，适合游戏或演示使用。

如何用C++实现一个ECS（实体组件系统）？C++游戏引擎架构模式【游戏开发】

C++如何实现一个简单的A*寻路算法_C++游戏AI开发中的路径规划实战

C++如何实现一个简单的行为树_C++游戏AI中决策逻辑的行为树实现

c++ 矩阵乘法代码 c++矩阵运算实现教程

c++怎么使用ONNX Runtime来运行一个AI模型_C++与ONNX Runtime集成运行AI模型实践

相关标签:

ai c++ 递归栈算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：C++内存模型教育学习资源与教学方法下一篇：C++栈溢出预防递归深度与局部变量控制

作者最新文章

如何减少Golang内存碎片化_Golang内存分配与回收优化方法

2026-01-01 20:54

如何使用Golang构建基础消息队列模拟_Golang消息发送与消费实现方法

2026-01-01 20:56

如何使用Golang搭建Web开发环境_快速启动HTTP服务

2026-01-01 20:57

如何在Golang中优化文件读写性能_使用缓冲和并发处理

2026-01-01 20:57

如何使用Golang log设置日志输出格式_Golang log日志格式示例

2026-01-01 20:59

如何使用Golang recover捕获panic_防止程序崩溃并处理异常

2026-01-01 20:59

Safari浏览器如何清理浏览器记录 Safari浏览器记录清理教程

2026-01-01 20:59

Win11怎么设置屏幕保护程序_Windows11个性化锁屏设置屏保

2026-01-01 21:05

Win11怎么设置快速访问主页_Windows11资源管理器文件夹选项

2026-01-01 21:05

Win11怎么更改任务栏颜色_Windows11个性化重音色设置

2026-01-01 21:05

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

堆和栈的区别

堆和栈的区别：1、内存分配方式不同；2、大小不同；3、数据访问方式不同；4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容，供大家免费下载体验。

371

2023.07.18

堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

563

2023.08.10

页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章，大家可以免费体验。

389

2023.08.14

php源码安装教程大全

本专题整合了php源码安装教程，阅读专题下面的文章了解更多详细内容。

2025.12.31

php网站源码教程大全

本专题整合了php网站源码相关教程，阅读专题下面的文章了解更多详细内容。

2025.12.31

视频文件格式

本专题整合了视频文件格式相关内容，阅读专题下面的文章了解更多详细内容。

2025.12.31

不受国内限制的浏览器大全

想找真正自由、无限制的上网体验？本合集精选2025年最开放、隐私强、访问无阻的浏览器App，涵盖Tor、Brave、Via、X浏览器、Mullvad等高自由度工具。支持自定义搜索引擎、广告拦截、隐身模式及全球网站无障碍访问，部分更具备防追踪、去谷歌化、双内核切换等高级功能。无论日常浏览、隐私保护还是突破地域限制，总有一款适合你！

2025.12.31