algorithm - 在 NxM 板上生成障碍物

Question

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

其中蓝色方 block 是障碍物。

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

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

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

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

Answer 1

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

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

如果填充正方形会产生边界循环，则该正方形是“无效的”:

• 任何具有 3 个填充邻居的未填充方 block 都是有效的。否则...
• 对于每个未填充的邻居，如果其相邻角位于同一边界内，则填充正方形会形成环，因此无效。
• 如果任意一对对角位于同一边界，但其他两个角均不在同一边界，则填充正方形将形成环，因此无效。

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