如何在C++中创建单元格或网格以生成随机迷宫？

Question

我正在尝试用C++创建随机迷宫，但我无法开始，因为我不知道如何创建网格或单元。我该怎么做呢？我还想使用ASCII字符来创建它。我应该如何将其存储在数组中？（有人可以给出一个示例代码和一些解释，以便我更好地理解吗）

另一个问题是：我需要学习和使用哪些数据结构？我打算使用Eller算法或Kruskal算法。

谢谢大家帮助我！我是初学者程序员，我想学习这个，因为这是我的项目的一部分，非常感谢！

- jesse

Answer 1

您是否在寻找迷宫生成算法(更多)？您的问题是关于算法还是图形学？

典型的算法通过将迷宫中的每个“单元格”视为图形的顶点来工作，从所有“墙壁”开始，并删除与生成树相对应的一组墙壁。(因此，为了使其随机化，许多算法都从随机权重开始并找到最小生成树。)至少对于小型迷宫，您不需要任何特殊的数据结构来表示单元格；您可以将每个单元格视为一对(x,y)（它的坐标）。而且，您也不需要任何数据结构（邻接矩阵/邻接列表）来存储图形的边缘，因为(x,y)的邻居只是(x,y±1)和(x±1,y)（忽略那些超出边界的）。

无论如何，一旦你有了生成树，你就知道哪些墙是“存在”的，哪些不是，因此你已经完整描述了迷宫。如果你要画迷宫，你就知道该画哪些。

要用ASCII字符绘制，只需逐行通过：绘制“上部墙壁”（如果在（x，y）和（x，y + 1）之间的墙存在，则放置“-”），然后绘制实际行（如果在（x，y）和（x + 1，y）之间的墙存在，则放置“|”）。最后绘制底部边界。

- ShreevatsaR

---

感谢您的解答，如果可以的话，您能否给我提供一份示例代码以便我更好地理解吗？非常感谢您！ - jessemiel

Answer 2

你可能希望将迷宫存储在一个二维字符数组中。在C++中，你可以声明一个数组并初始化或不初始化。

char a[30][10];  // declares a char array of 30 rows and 10 columns.

// declare an array with 3 rows and 3 columns, and provide initial values
char ticTacToeBoard[3][3] = {{'x', 'x', 'o'},
                             {'o', 'o', 'x'},
                             {'x', 'o', ' '}
                            };

您可以将您的迷宫中墙的初始值更改为'|'和'-'，并使用空格字符' '表示通道。两种初始化方法都可以，但您总是以相同的方式使用元素。以下是如何在上述初始化数组中清除板的方法。

// clear the board
for (int row=0; row<3; row++) {
    for (int col=0; col<3; col++) {
        ticTacToeBoard[row][col] = ' ';
    }
}

如果您想读取元素的值（在尝试导航迷宫时非常有用），则使用与设置其值相同的下标符号。

char y = a[2][2]; // reads the character in row 2, column 2

- Bill the Lizard

Answer 3

垂直墙：| 水平墙：_

如果您使用固定宽度字体：

 _____
| |  _
|_  | |
 __ | |
|_____|

我不确定该做什么，但这里是我会开始的地方。

确定起点和终点在网格上的位置。然后创建一条单一路径，可加入任何你想要的曲线。基本上，它应该是随机运动，每次检查此路径是否仍然可以到达终点。然后，从这条路径中移除一定数量的墙壁，并从这些洞口创建其他路径。继续进行，直到没有空间可用。然后，可能还需确保没有创建出更短的路径。如果有，将其封堵。

- stalepretzel