将网格（2D数组）分成随机形状的部分？

Question

问题
我想将一个网格（2D数组）分成随机形状的部分（类似于地球的构造板块）。

标准如下：

• 用户输入网格大小（程序应该进行缩放，因为这可能非常大）。
• 用户输入网格划分系数（有多少部分）。
• 网格是一个矩形六边形网格，并且在顶部和底部被封口，在左右两侧包裹。
• 不能分裂零件。
• 没有零件在其他零件内部。
• 没有小型或超大型零件。
• 随机形状的部分，不是完美的圆形或细长的蛇形。

我的解决方案：

• 创建一个可以访问/操作相邻单元格的方法。
• 随机确定每个部分的大小（所有部分的总和等于整个二维数组的大小）。
• 用最后一个部分的ID号填充整个二维数组。
• 对于除了最后一个部分之外的每个部分：
• 在二维数组的随机单元格中种植当前部分的ID号。
• 迭代整个数组并存储与已经用当前部分ID号种植的任何单元格相邻的每个单元格的地址。
• 提取其中一个存储的地址，并将该单元格填充为当前板块ID号（因此部分开始形成）。
• 重复直到达到部分大小。

请注意，为避免具有长串“臂”或内部大孔的零件，我创建了两个存储数组：一个用于仅与当前部分ID号的一个单元格相邻的单元格，另一个用于与多个单元格相邻的单元格，然后我先排除后者再排除前者。

运行我的解决方案会得到以下结果：
网格大小：200
宽度：20
高度：10
零件：7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

零件编号: 0
零件尺寸: 47

零件编号: 1
零件尺寸: 30

零件编号: 2
零件尺寸: 26

零件编号: 3
零件尺寸: 22

零件编号: 4
零件尺寸: 26

零件编号: 5
零件尺寸: 22

零件编号: 6
零件尺寸: 27

我的解决方案存在问题:

• 最后一部分总是不完整的 - 在上面的例子中有三组不同的六个。
• 当部分形成死胡同并且没有足够的空间扩展到其完整大小时，算法将停止（除非是最后一部分，在开始时覆盖整个2D数组）。
• 如果我在形成2D数组之前不指定部件大小，而只是指定部件数量并在生成部件大小时随机生成，那么这会留下形成微小部件的可能性，这些部件可能根本不存在，特别是当2D数组非常大时。 我目前的部件大小方法将部件大小限制在2D数组总大小的10％至40％之间。 如果有一种超级优雅的方法可以做到这一点，我也许可以不指定部件大小 - 用户唯一的控制是2D数组大小和部件数量。

其他想法：

• 将零件组成完美对齐的正方形，然后在2D数组上运行，并随机允许每个零件侵入其他零件，将它们扭曲成随机形状。
• 在网格上绘制蛇形线条，并填充所创建的空间，可能使用一些数学方法，例如：http://mathworld.wolfram.com/PlaneDivisionbyLines.html

结论:
所以问题来了：我是一个初学者程序员，不确定我是否以正确的方式解决了这个问题。我可以创建一些更多的“修补”方法，将分散的部分移动到一起，并允许正在形成的部分“跳出”死胡同，如果它们被困在其中，但感觉很混乱。

你会如何解决这个问题？也许有一些性感的数学方法可以简化事情吗？

谢谢

- b1_

---

为什么不从大小为1的axb部分开始随机连接相邻部分？这些部分是否有满足的某些标准？ - Mladen Jablanović

我之前没有想到过这个，最近几天一直在尝试你的方法。它自然地避免了部件的碎片化，但无法避免部件形成在其他部件内部。你的方法中最简单的形式总是会产生一个超大的部件，其余的则会很小。调整以获得所需结果似乎并不比我的解决方案更容易。我已经在我的问题帖子中添加了更清晰的标准说明。 - b1_

Answer 1

我几个月前为一个游戏做过类似的事情，不过它是一个矩形网格而不是六边形网格。不过，理论是相同的，它生成了大小大致相等的连续区域 - 有些更大，有些更小，但没有太小或太大的区域。你的结果可能会有所不同。

1. 创建指向网格中所有空间的指针数组并对其进行洗牌。
2. 给前N个空间分配ID - 1、2、3等。
3. 直到数组不再指向没有ID的空间为止，
4. 遍历数组查找没有ID的空间。
5. 如果该空间在网格中有具有ID的邻居，则将该空间分配给其邻居ID的加权随机选择。
6. 如果没有具有ID的邻居，则跳到下一个。
7. 一旦没有非空间，你就拥有了具有足够多斑点区域的地图。

- Brenda Holloway

---

换句话说：1. 用单个零件 ID 号随机分布填充 2D 数组，2. 遍历 2D 数组并根据周围单元格的内容在空单元格中插入零件 ID 号。这种方法比我的原始解决方案显著提高了速度。它通过在一次迭代中同时形成更多的零件来最小化你迭代数组的次数。它还不会在形成零件之前形成零件大小 - 这可能是一种限制性的不必要的方法。没有孔洞或碎片。谢谢 - b1_

遍历二维数组，注意，这可能会导致您在迭代方向上出现线条。这就是为什么 Brenda 先洗牌的原因。第6步使算法重复执行，它绝对不是一次迭代。 - Mooing Duck

Answer 2

这是我会做的事情：使用泰森多边形算法。首先放置一些随机点，然后让泰森多边形算法生成部分。要了解它的外观，请参考：此应用程序。

- Rekin

---

我对此进行了非常简短的了解。我的第一个想法是，它会产生对于我的目的来说形状过于统一的零件 - 我的一些零件偶尔被钩住也无妨。我很好奇是否会有任何显著的速度提升。这足够吸引人，让我尝试在一个单独的程序中让这个数学工作起来，只是出于兴趣。而且我学到了一个新术语：计算几何。谢谢你的建议。 - b1_

经过进一步调查发现，这种方法是迄今为止最快的方法——它仅需要对网格进行一次迭代。 它也不需要实现复杂的数学知识。伪代码如下：

1. 使用单个部件ID号的单个实例（种子），随机分布填充2D数组。
2. 对于每个细胞，找到最接近的种子部件ID号（使用距离方法）并将其插入当前细胞中。结果是一个沃罗诺伊图。但它看起来可能过于线性了——可能可以以某种方式扭曲它，而仍比其他解决方案更快。

- b1_

Answer 3

正如Rekin所建议的那样，Voronoi图加上一些随机扰动通常会做得很好，在像你拥有的离散空间中，相对容易实现。

我只是想提供一些关于如何进行随机扰动的想法。如果你在最终分辨率上进行扰动，那么要么需要很长时间，要么效果可能很小。你可以尝试进行多分辨率扰动。因此，从一个相当小的网格开始，随机种子，计算Voronoi图。然后随机扰动边界-例如，对于每一对具有不同区域的相邻单元格，将该区域向左或向右推动。您可能需要运行后处理以确保没有微小的岛屿...一个简单的泛洪填充就可以解决。

然后创建一个两倍大小（在每个方向上）的网格，并复制您的区域。您可能可以使用最近邻方法。然后再次扰动边界，并重复直到达到所需的分辨率。

- tfinniga