递归分割算法是一种通过不断将区域分割来生成迷宫的算法，核心思路是将初始的矩形区域不断划分成更小的子区域，同时在分割墙上随机开洞，最终形成连通的迷宫结构。使用C++实现该算法并结合控制台字符图形，可以直观看到迷宫的生成过程与最终效果。
递归分割算法原理
递归分割算法的执行流程可以分为几个核心步骤：
- 首先设定初始的迷宫区域，通常是一个矩形的二维网格，网格的边界默认都是墙壁
- 如果当前区域的长或者宽小于最小阈值，就停止分割，返回当前区域
- 随机选择横向或者纵向的分割线，将当前区域分成两个部分
- 在分割线上随机选择一个位置开洞，保证两个子区域是连通的
- 对分割后的两个子区域分别递归执行上述分割流程
控制台图形绘制准备
在C++的控制台中展示迷宫，我们需要用不同的字符来表示墙壁和通路，常用的字符选择如下：
| 字符 | 含义 |
|---|---|
| # | 墙壁 |
| 空格 | 通路 |
为了能够在控制台中实时刷新展示迷宫生成过程，我们需要使用Windows系统的控制台API来操作光标位置，相关头文件和函数声明如下：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <windows.h>
// 设置控制台光标位置
void setCursorPosition(int x, int y) {
HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
COORD pos;
pos.X = x;
pos.Y = y;
SetConsoleCursorPosition(hOut, pos);
}
// 隐藏控制台光标
void hideCursor() {
HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_CURSOR_INFO cursorInfo;
GetConsoleCursorInfo(hOut, &cursorInfo);
cursorInfo.bVisible = false;
SetConsoleCursorInfo(hOut, &cursorInfo);
}
迷宫生成器完整实现
下面是结合递归分割算法和控制台图形的完整C++迷宫生成器代码，代码中包含了迷宫初始化、递归分割、绘制展示等全部逻辑：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <windows.h>
using namespace std;
// 迷宫尺寸，需要是奇数，保证墙壁和通路分布合理
const int ROW = 21;
const int COL = 41;
// 最小分割区域尺寸
const int MIN_SIZE = 3;
// 迷宫网格，true表示墙壁，false表示通路
vector<vector<bool>> maze(ROW, vector<bool>(COL, true));
// 设置光标位置
void setCursorPosition(int x, int y) {
HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
COORD pos;
pos.X = x;
pos.Y = y;
SetConsoleCursorPosition(hOut, pos);
}
// 隐藏光标
void hideCursor() {
HANDLE hOut = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_CURSOR_INFO cursorInfo;
GetConsoleCursorInfo(hOut, &cursorInfo);
cursorInfo.bVisible = false;
SetConsoleCursorInfo(hOut, &cursorInfo);
}
// 绘制当前迷宫状态
void drawMaze() {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (maze[i][j]) {
cout << "#";
} else {
cout << " ";
}
}
cout << endl;
}
}
// 递归分割函数，参数分别是区域左上角坐标和区域宽高
void recursiveDivide(int startX, int startY, int width, int height) {
// 如果区域尺寸小于最小阈值，停止分割
if (width < MIN_SIZE || height < MIN_SIZE) {
return;
}
// 随机选择分割方向，0表示横向分割，1表示纵向分割
int direction = rand() % 2;
if (direction == 0) {
// 横向分割，分割线y坐标需要在奇数位置，保证墙壁连续
int splitY = startY + (rand() % ((height - 1) / 2)) * 2 + 1;
// 分割线从startX到startX+width-1
for (int x = startX; x < startX + width; x++) {
maze[splitY][x] = true;
}
// 在分割线上随机开洞，洞的x坐标需要是奇数位置
int holeX = startX + (rand() % (width / 2)) * 2 + 1;
maze[splitY][holeX] = false;
// 递归处理上下两个子区域
recursiveDivide(startX, startY, width, splitY - startY);
recursiveDivide(startX, splitY + 1, width, startY + height - splitY - 1);
} else {
// 纵向分割，分割线x坐标需要在奇数位置
int splitX = startX + (rand() % ((width - 1) / 2)) * 2 + 1;
// 分割线从startY到startY+height-1
for (int y = startY; y < startY + height; y++) {
maze[y][splitX] = true;
}
// 在分割线上随机开洞，洞的y坐标需要是奇数位置
int holeY = startY + (rand() % (height / 2)) * 2 + 1;
maze[holeY][splitX] = false;
// 递归处理左右两个子区域
recursiveDivide(startX, startY, splitX - startX, height);
recursiveDivide(splitX + 1, startY, startX + width - splitX - 1, height);
}
// 每次分割后刷新绘制迷宫
setCursorPosition(0, 0);
drawMaze();
Sleep(200); // 延迟200毫秒，方便观察生成过程
}
int main() {
// 初始化随机种子
srand(time(0));
// 隐藏控制台光标
hideCursor();
// 初始化迷宫，先将所有位置设为通路
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
maze[i][j] = false;
}
}
// 设置边界为墙壁
for (int i = 0; i < ROW; i++) {
maze[i][0] = true;
maze[i][COL - 1] = true;
}
for (int j = 0; j < COL; j++) {
maze[0][j] = true;
maze[ROW - 1][j] = true;
}
// 设置起点和终点为通路
maze[1][1] = false;
maze[ROW - 2][COL - 2] = false;
// 开始递归分割生成迷宫
recursiveDivide(1, 1, COL - 2, ROW - 2);
// 生成完成后停留显示
setCursorPosition(0, ROW);
cout << "迷宫生成完成，按任意键退出" << endl;
system("pause > nul");
return 0;
}
代码说明与扩展
上述代码中，递归分割的核心逻辑在recursiveDivide函数中实现，我们通过限制分割线的坐标必须为奇数，保证生成的迷宫墙壁和通路分布符合常规迷宫的结构。如果需要调整迷宫的复杂度，可以修改MIN_SIZE的数值，数值越小生成的迷宫分割越细，路径越复杂。
如果需要在其他系统运行该代码，可以将Windows控制台相关的API替换为对应系统的控制台操作函数，比如Linux系统可以使用ncurses库来实现光标位置控制和屏幕刷新功能。