在我们之前的帖子中，我们深入探讨了与解决迷宫问题密切相关的图路径查找问题。
当我开始为Wall-E项目创建迷宫地图时，我最初预期能找到一种快速且简便的方法来完成这个任务。然而，我很快就发现自己沉浸在广阔而迷人的迷宫世界中。
在此之前，我对这个主题的广度和深度一无所知。我发现迷宫可以按照七种不同的方式进行分类，每种方式又有许多变种和无数用于生成迷宫的算法。
令人惊讶的是，我找不到任何详细涵盖这个主题的算法书籍，甚至维基百科页面也没有提供系统的概述。幸运的是，我偶然发现了一个非常好的资源，介绍了各种类型的迷宫和算法，我强烈推荐大家探索一下。
我开始了解迷宫的不同分类，包括维度和超维度变体、完美迷宫与一笔画迷宫、平面和稀疏迷宫等等。
如何创建迷宫
我的主要目标是生成一个代表迷宫的二维地图。
虽然实现各种迷宫生成算法进行比较很诱人，但我也希望有一种更高效的方法。我找到的最快解决方案是随机选择相邻的单元格。这正是我在mazerandom中所做的。这个单文件应用程序创建一个20 x 20单元格的网格表，然后使用深度优先搜索（DFS）遍历随机连接它们。换句话说，我们只是在网格中切割通道。
如果你在纸上手动完成这个过程，它会看起来像这样：
为了以算法方式实现这一点，我们将深度优先搜索应用于单元格网格。让我们看看在Main.cpp中是如何实现的。
和往常一样，我们将单元格网格表示为数组的数组，并使用堆栈进行DFS：
我们访问网格中的每个单元格，并将其相邻单元格推入堆栈进行深度遍历：
最复杂的逻辑涉及将节点标记为可到达（即没有墙隔开）的CELL_PATH_S、CELL_PATH_N、CELL_PATH_W或CELL_PATH_E：
最后，它调用drawMaze方法使用SFML库在屏幕上绘制迷宫。如果当前单元格未标记为CELL_PATH_S、CELL_PATH_N、CELL_PATH_W或CELL_PATH_E，它在两个单元格之间绘制墙。
然而，这个迷宫并不能保证有解。在许多情况下，它会生成一张没有明显路径连接两个点的地图。虽然这种随机性可能很有趣，但我想要更有结构性的东西。
确保迷宫有解的唯一方法是使用一个预定的结构来以某种方式连接迷宫的每个部分。
使用图论创建迷宫
众所周知，迷宫生成算法依赖于图。每个单元格都是图中的一个节点，每个节点必须至少连接到其他节点。
如前所述，迷宫有多种形式。有些称为“一笔画”迷宫，它们表现为只有一个入口的迷宫，该入口也是出口。其他迷宫可能有多个解。然而，生成过程通常始于创建一个“完美”迷宫。
“完美”迷宫，也称为简单连通迷宫，不包含循环、闭合回路和不可达区域。从其中的任意一点到其他任意一点，都有且只有一条路径。迷宫有一个单一且可解的解。
如果我们将图作为迷宫的内部表示，构建一个生成树可以确保从起点到终点有一条路径。
从计算机科学的角度来说，这样的迷宫可以描述为单元格或顶点集上的生成树。
可能存在多个生成树，但目标是确保至少有一条从起点到终点的解，如下面的示例所示：
上图只显示了一条解，但实际上有多条路径。没有任何单元格是孤立的且无法到达的。那么，我们如何实现这一点呢？
我发现了一个由@razimantv设计的精心设计的mazegenerator代码库，可以生成SVG文件格式的迷宫。
因此，我fork了这个代码库，并基于它进行了解决方案。对于优雅的面向对象设计，我要感谢@razimantv，这让我可以使用SFML库创建具有视觉吸引力的图像，或生成一个包含所需地图描述的文本文件，用于我的Wall-E项目。
我对代码进行了重构，删除了不必要的组件，将重点专注于矩形迷宫。
然而，我保留了对多种算法构建生成树的支持。
我还在整个代码库中添加了注释，以便更容易理解，所以我不需要在这里详细解释了。主要的流程可以在\mazegenerator\maze\mazebaze.cpp中找到：
我引入了使用SFML图形库进行可视化，感谢一个简单的_Draw_函数。尽管DFS是创建生成树的默认算法，但有多个算法可供选择。结果是一个方便的实用程序，可以生成矩形的“完美”迷宫并在屏幕上显示：
如您所见，它恰好在左上角和右下角包含一个输入和一个输出。代码仍然生成SVG文件，这是一个很好的补充（尽管它是原始代码库的核心功能）。
现在，我可以继续进行我的Wall-E项目实验了，希望您会被激发去探索这个迷人的迷宫世界，并踏上自己的旅程。请继续关注！