algorithm - 在 NxM 板上生成障碍物

Question

我有 NxM 板。我想为其添加 K 个障碍，但在某种程度上，仍然可以从每个空白空间到达每个其他空白空间。我希望它看起来像这样

其中蓝色方块是障碍物。

换句话说，我有一个图形网格，我想从中随机删除 K 个顶点而不断开它。

我知道我可以通过从一个节点执行 dfs 并删除最远的顶点来做到这一点，但它不会真的是随机的，它看起来不太好，也不是我想要的。

有没有可以做我想做的事情的算法，或者有没有人有一些想法可以测试？

编辑：典型的迷宫生成算法不适用于我的情况，因为据我了解，它们通过从图中删除边来工作，在这里我需要删除整个顶点

标签： algorithmgraph-algorithmmazeprocedural-generation

Answer 1

您可以使用不相交的集合数据结构来做到这一点： https ://en.wikipedia.org/wiki/Disjoint-set_data_structure

• 每个顶点都分配给一个集合，该集合标识它属于哪个“边界”
• 最初，外边界上的顶点都在同一个集合中，每个内部顶点都在自己的集合中。
• 随机选择一个“有效”的正方形并填充它。相应地合并其 4 个角中每个角的边界集。
• 重复直到选择了 K 个方格

如果填充正方形会创建边界循环，则正方形是“无效的”：

• 任何具有 3 个填充邻居的未填充正方形都是有效的。除此以外...
• 对于每个未填充的邻居，如果它的相邻角在同一边界内，那么填充正方形会创建一个循环，因此它是无效的。
• 如果任何一对对角在同一边界，但其他角都不在，那么填充正方形会产生一个循环，所以它是无效的。

为了有效地实现，以伪随机顺序随机尝试所有正方形。由于填充一个正方形可能会使先前无效的正方形有效，但是，每当您填充一个正方形时，将其先前排除的邻居添加回可能性池中。