在为Wall-E项目创建迷宫地图时，原本以为会找到一个快速简单的方法来完成这项任务。然而，很快就发现自己沉浸在迷宫和迷宫的广阔而迷人的世界中。之前并不知道这个主题的广度和深度。发现迷宫可以以七种不同的方式进行分类，每种方式都有无数的变化和无数的生成算法。
令人惊讶的是，没有找到任何全面涵盖这一主题的算法书籍，甚至Wikipedia页面也没有提供系统的概述。幸运的是，偶然发现了一个涵盖各种迷宫类型和算法的绝佳资源，强烈推荐探索。
开始了一段旅程，学习不同类型的迷宫，包括维度和超维度变化，完美迷宫与单路径迷宫，平面和稀疏迷宫等。
主要目标是生成一个代表迷宫的2D地图。虽然实现各种迷宫生成算法进行比较会很诱人，但也想要一种更有效的方法。发现的最快解决方案涉及随机选择连接的单元格。这正是使用mazerandom所做的。这个单文件应用程序创建了一个20x20单元格的网格表，然后使用深度优先搜索（DFS）遍历随机连接它们。换句话说，只是在网格中雕刻通道。
如果手动在纸上这样做，它看起来会像这样：
// 假设有一个20x20的网格
vector> maze_cells;
// 使用栈进行DFS遍历
stack my_stack;
my_stack.push(Coord(0, 0)); // 从第一个单元格开始
// 遍历网格中的每个单元格，并将它的邻居推到栈上进行深度遍历
while (visitedCells < HORIZONTAL_CELLS * VERTICAL_CELLS) {
vector neighbours;
// 第一步：创建一个未访问邻居单元格的数组
// （来自北，东，南和西）。
// 北方尚未访问？
if ((maze_cells[offset_x(0)][offset_y(-1)] & CELL_VISITED) == 0) {
neighbours.push_back(0);
}
// 东方尚未访问？
if ((maze_cells[offset_x(1)][offset_y(0)] & CELL_VISITED) == 0) {
neighbours.push_back(1);
}
// 对西和南做同样的操作...
// 如果至少有一个未访问的邻居
if (!neighbours.empty()) {
int next_cell_dir = neighbours[rand() % neighbours.size()];
// 在邻居和当前单元格之间创建一条路径
switch (next_cell_dir) {
case 0: // 北
// 标记为已访问。在南北两个方向上标记连接。
maze_cells[offset_x(0)][offset_y(-1)] |= CELL_VISITED | CELL_PATH_S;
maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_N;
my_stack.push(Coord(offset_x(0), offset_y(-1)));
break;
case 1: // 东
// 标记为已访问。在东西两个方向上标记连接。
maze_cells[offset_x(1)][offset_y(0)] |= CELL_VISITED | CELL_PATH_W;
maze_cells[offset_x(0)][offset_y(0)] |= CELL_PATH_E;
my_stack.push(Coord(offset_x(1), offset_y(0)));
break;
// 对西和南做同样的操作...
}
visitedCells++;
} else {
my_stack.pop();
}
}
// 最后，调用drawMaze()方法使用SFML库在屏幕上绘制迷宫。
// 如果当前单元格没有标记为CELL_PATH_S、CELL_PATH_N、CELL_PATH_W或CELL_PATH_E，
// 则在两个单元格之间绘制一堵墙。
然而，这个迷宫并不能保证有解决方案。在许多情况下，它会生成一个没有清晰路径的地图。虽然这种随机性可能很有趣，但想要更结构化的东西。
确保迷宫有解决方案的唯一方法是使用一种预定的结构，以某种方式连接迷宫的每个部分。
众所周知的迷宫生成算法依赖于图。每个单元格是图中的一个节点，每个节点至少必须与其他节点有一个连接。
如前所述，迷宫有多种形式。有些被称为“单路径”迷宫，它们作为只有一个入口的迷宫，该入口也作为出口。其他的可能有多个解决方案。然而，生成过程通常从创建一个“完美”迷宫开始。
“完美”迷宫，也称为简单连通迷宫，没有环路、闭合电路和无法到达的区域。从它的任何一点，都有一条精确的路径到达任何其他点。迷宫有一个单一的、可解的解决方案。
如果使用图作为迷宫的内部表示，构建一个生成树确保从起点到终点有一条路径。
在计算机科学术语中，这样的迷宫可以被描述为一组单元格或顶点的生成树。
可能存在多个生成树，但目标是确保至少有一个从起点到终点的解决方案，如下图所示：
上图只显示了一个解决方案，但实际上有多个路径。没有单元格是孤立的，无法到达。那么如何实现这一点呢？
发现了一个设计精良的mazegenerator代码库，由@razimantv创建，它实现了这一点，生成SVG文件格式的迷宫。
因此，分叉了仓库，并基于它构建了解决方案。感谢@razimantv的优雅OOP设计，它允许自定义结果，使用SFML库创建视觉上吸引人的图像，或者生成包含必要地图描述的文本文件，用于Wall-E项目。
重构了代码，去除了不必要的组件，专注于矩形迷宫。
然而，保留了支持各种算法构建生成树的支持。
还在整个代码库中添加了注释，以便更容易理解，所以不需要在这里详细解释。主要的管道可以在\mazegenerator\maze\mazebaze.cpp中找到：
void MazeBase::GenerateMaze(SpanningtreeAlgorithmBase* algorithm) {
// Generates entire maze spanning tree
auto spanningTreeEdges = algorithm->SpanningTree(_verticesNumber, _edgesList);
// Find a solution of a maze based on Graph DFS.
_Solve(spanningTreeEdges);
// Build a maze by removing unnecessary edges.
_RemoveBorders(spanningTreeEdges);
}
引入了使用SFML图形库的可视化，这要归功于一个简单的_Draw_函数。
虽然DFS是创建生成树的默认算法，但有多种算法可供选择。
结果是一个方便的实用程序，可以生成矩形“完美”迷宫并在屏幕上显示它们：
如所见，它恰好包含一个输入和一个输出，在左上角和右下角。代码仍然生成SVG文件，这是原始代码库的核心功能（尽管它是核心功能）。