制作迷宫

引言

在我上一篇文章中，我们深入探讨了图中的寻路问题，这与解决迷宫密切相关。

当我开始为 Wall-E 项目创建迷宫地图时，我最初期望能够找到一种快速简便的方法来完成这项任务。然而，我很快发现自己沉浸在迷宫和曲折通道的广阔而迷人的世界中。

在此之前，我并不知道这个主题的广度和深度。我发现迷宫可以分为七种不同的方式，每种方式都有众多的变体和无数种生成算法。

> 令人惊讶的是，我找不到任何一本全面涵盖此主题的算法书籍，甚至连 维基百科页面也没有提供系统性的概述。幸运的是，我偶然发现了一个很棒的资源，其中涵盖了各种迷宫类型和算法，我强烈推荐大家去探索。

我开始着手学习不同类型的迷宫分类，包括二维和高维变体、完美迷宫与单通路迷宫、平面迷宫和稀疏迷宫等等。

如何创建迷宫

我的主要目标是生成一个表示迷宫的二维地图。

虽然实现各种迷宫生成算法进行比较会很有吸引力，但我也想要一种更有效的方法。我找到的最快解决方案是将连接的单元随机选择。这正是我使用 mazerandom 所做的。这个单一文件应用程序创建一个 20 x 20 个单元的网格表，然后使用深度优先搜索 (DFS) 遍历随机连接它们。换句话说，我们只是在网格中开辟通道。

如果你在纸上手动完成，看起来会是这样的

为了在算法上实现这一点，我们将深度优先搜索应用于单元格网格。让我们看看 Main.cpp 中是如何实现的。

像往常一样，我们将单元格网格表示为数组的数组，并使用堆栈进行 DFS。

vector < vector < int > > maze_cells; // A grid 20x20
stack<Coord> my_stack;                // Stack to traverse the grid by DFS
my_stack.push(Coord(0, 0));           // Starting from very first cell

我们遍历网格中的每个单元格，并将它们的邻居推入堆栈进行深度遍历。

...
while (visitedCells < HORIZONTAL_CELLS * VERTICAL_CELLS)
{
	vector<int> neighbours;
	// Step 1: Create an array of neighbour cells that were not yet visited 
    // (from North, East, South and West).
	// North is not visited yet?
	if ((maze_cells[offset_x(0)][offset_y(-1)] & CELL_VISITED) == 0) 
	{
		neighbours.push_back(0);
	}
	// East is not visited yet?
	if ((maze_cells[offset_x(1)][offset_y(0)] & CELL_VISITED) == 0) 
	{
		neighbours.push_back(1);
	}
	... // Do the same for West and South...

最复杂的逻辑是标记节点为可达（即，之间没有墙壁），使用 CELL_PATH_S、CELL_PATH_N、CELL_PATH_W 或 CELL_PATH_E。

...
	// If we have at least one unvisited neighbour 
	if (!neighbours.empty()) 
	{
		// Choose random neighbor to make it available
		int next_cell_dir = neighbours[rand() % neighbours.size()];

		// Create a path between the neighbour and the current cell
		switch (next_cell_dir)
		{
		case 0: // North
			// Mark it as visited. Mark connection between North and South 
            // in BOTH directions.
			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: // East
			// Mark it as visited. Mark connection between East and West 
            // in BOTH directions.
			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;
		... // Do the same for West and South...
		}
		visitedCells++;
	}
	else
	{
		my_stack.pop();
	}
...

最后，它调用 drawMaze() 方法，使用 SFML 库在屏幕上绘制迷宫。如果当前单元格未标记为 CELL_PATH_S、CELL_PATH_N、CELL_PATH_W 或 CELL_PATH_E，它会在两个单元格之间绘制一堵墙。

然而，这个迷宫不能保证有解。在许多情况下，它会生成一个地图，在两个点之间没有清晰的路径。虽然这种随机性可能很有趣，但我想要更结构化的东西。

确保迷宫有解的唯一方法是使用预先确定的结构，该结构以某种方式连接迷宫的每个部分。

使用图论创建迷宫

著名的迷宫生成算法依赖于图。每个单元格都是图中的一个节点，并且每个节点必须至少与其他节点有一个连接。

如前所述，迷宫有多种形式。有些称为“单通路”迷宫，它们像只有一个入口的曲折通道，入口也充当出口。其他迷宫可能有多种解决方案。然而，生成过程通常从创建一个“完美”迷宫开始。

“完美”迷宫，也称为简单连通迷宫，没有循环、闭合电路和无法到达的区域。从其中的任何一点出发，都有且只有一条路径可以到达任何其他点。迷宫有一个唯一、可解的路径。

如果我们使用图作为迷宫的内部表示，构建一个生成树可以确保从起点到终点存在路径。

用计算机科学的术语来说，这样的迷宫可以被描述为一组单元格或顶点的生成树。

可能存在多个生成树，但目标是确保至少有一个从起点到终点的解决方案，如下面的示例所示。

上图仅显示了一种解决方案，但实际上有多条路径。没有单元格是孤立且无法到达的。那么，我们如何实现这一点呢？

我发现了一个由 @razimantv 设计精良的 mazegenerator 代码库，它以 SVG 文件格式生成迷宫。

因此，我分叉了这个仓库并以此为基础进行了解决方案。感谢 @razimantv 优雅的 OOP 设计，它允许我自定义结果，使用 SFML 库创建视觉上吸引人的图像，或者为我的 Wall-E 项目生成包含必要地图描述的文本文件。

我重构了代码，移除了不必要的组件，并只专注于矩形迷宫。

但是，我保留了对各种生成树算法的支持。

我还为整个代码库添加了注释，以便于理解，因此我不需要在这里详细解释。主流程可以在 \mazegenerator\maze\mazebaze.cpp 中找到。

/**
 * \param algorithm Algorithm that is used to generate maze spanning tree.
 */
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);
}

我利用简单的 _Draw_ 函数引入了 SFML 图形库的可视化。

虽然 DFS 是创建生成树的默认算法，但也有多种算法可供选择。

结果是一个方便的实用程序，可生成矩形“完美”迷宫并在屏幕上显示它们。

正如你所见，它在左上角和右下角正好有一个入口和一个出口。代码仍然生成 SVG 文件，这是一个不错的附加功能（尽管它是原始代码库的核心功能）。

现在，我可以继续在 Wall-E 项目中进行实验了，我在这里告别，希望你也能受到启发，探索这个迷人的迷宫世界，并踏上自己的旅程。

历史

• 2023年9月25日：初始版本