c# - 在没有 'cycles' 的情况下按程序生成迷宫

Question

我想编写一种算法，可以在封闭的房间内生成类似“迷宫”的结构。 [这不是典型的迷宫。我只想要房间里到处都是墙。]

要注意的是我不想要任何“循环”。例如:

1. 我想要这个:-

2. 我不想要这个:- [这里机器人被卡住了，因为它无法访问房间的其余部分]

我理解这是因为墙结构中没有循环。所以我想到了一个解决方案:生成一个墙段，然后在生成后检查循环(如果有循环，则重新生成)，但这似乎很乏味，因为我必须在图表中对内容进行编码，所以我想到了另一个解决方案。

生成一个墙段，然后选择一个空单元格，看看是否可以从该单元格到达所有其他空单元格(如果不能，则重新生成)。这看起来很有希望，但我不知道从哪里开始。

此外，这些解决方案并没有解决房间里的大象问题:首先要正确生成墙壁!而且，不能真正谈论以前算法的时间复杂度。

我该如何处理这个问题？

P.S:我正在使用 C# 在 Unity 中执行此操作。

Answer 1

递归划分迷宫生成法为所欲为。 https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method

从您发布的图片来看，您想要开阔的“房间”，因此您会希望尽早停止算法。您可以指定大于 1 的所需最小尺寸，而不是“直到所有腔室都达到最小尺寸”。