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

Question

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

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

谢谢你们帮助我！ 我是一名初级程序员，我想了解这一点，因为这是我项目的一部分，非常感谢您！

Answer 1

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

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

无论如何，一旦有了生成树，您就可以准确地知道哪些墙“存在”，哪些墙“不存在”，因此您对迷宫有了完整的描述。 如果你要画迷宫，你就知道要画哪些迷宫。

要使用 ASCII 字符进行绘制，只需逐行遍历每一行：绘制“上墙”（如果 (x,y)--” code> 和 (x,y+1) 存在），然后绘制实际行（如果 (x,y) 之间有墙，则绘制“|” 和 (x+1,y) 存在）。 最后画出底部边界。

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

Answer 3

垂直墙：|
水平。 Wall：_

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

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

我不确定该怎么做，但这就是我要开始的地方。

确定网格上的起点和终点的位置。 然后，使用您想要的任何曲线创建一条路径。 基本上，它应该是随机移动，每次检查这条路径是否还有办法到达终点。 然后，从此路径中移除一定数量的墙壁，并从这些孔中创建其他路径。 继续此操作，直到用完可用空间。 然后，也许可以确保没有创建更短的路径。 如果有，请将其阻止。