将网格(2D阵列)划分为随机形状的部分？

Question

问题
我想将网格(2D阵列)划分为随机形状的部分(想想地球的构造板块).

标准是:

• 用户输入网格大小(程序应该缩放,因为这可能非常大).
• 用户输入网格划分因子(多少部分).
• 网格是矩形六角网格,顶部和底部封顶,左右环绕.
• 零件没有碎片.
• 其他部分内没有零件.
• 没有微小或超大的部件.
• 随机形状的部分,不是完美的圆形,或者是蜿蜒的蛇形.

我的解决方案

• 创建一个可以访问/操作相邻单元格的方法.
• 随机确定每个部分的大小(所有部分的总和等于整个2D阵列的大小).
• 用最后一部分的id号填充整个2D数组.
• 除了最后一个部分:
• 在2D阵列的随机单元格中种植当前部件ID号.
• 迭代整个阵列并将每个单元的地址存储在已经使用当前部件ID号播种的任何单元旁边.
• 提取其中一个存储的地址,并使用当前的板ID编号填充该单元格(因此部件开始形成).
• 重复,直到达到零件尺寸.

请注意,为了避免在其内部长出"臂"或大孔的部分,我创建了两个存储阵列:一个用于与一个单元相邻的单元,当前部件ID号,另一个用于与多个单元相邻的单元,然后我在前者之前用尽了后者.

运行我的解决方案提供以下内容:
网格大小:200
宽度:20
高度:10个
部分:7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
0000333111164444660
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阵列上运行并随机允许每个部件侵入其他部件,将它们翘曲成随机形状.
• 在网格上绘制蛇形线并填充创建的空间,可能使用这样的数学:http://mathworld.wolfram.com/PlaneDivisionbyLines.html

结论:
所以这就是问题:我是一名初学程序员,不确定我是否以正确的方式解决了这个问题.我可以创建一些更多的"补丁"方法,将碎片部分移动到一起,并允许形成部分"跳出"死胡同,如果它们卡在它们中,但它感觉凌乱.

你会如何解决这个问题？我可以用一些性感的数学来简化一些事情吗？

谢谢

Answer 1

几个月前，我为一款游戏做了类似的事情，尽管它是一个矩形网格而不是一个六角形网格。理论仍然是相同的，它提出了一些大小大致相等的连续区域-一些较大，一些较小，但没有一个过小或过大。YMMV。

1. 制作一个指向网格中所有空间的指针数组。随机排列数组。
2. 分配其中的前N个ID-1、2、3等。
3. 在数组指向没有ID的空格之前，
4. 遍历数组以查找没有ID的空间
5. 如果空间在网格中具有ID的邻居，则从该邻居的ID的加权随机选择中分配ID。
6. 如果没有ID的邻居，请跳到下一个。
7. 一旦没有非空的空间，您的地图就会有足够的空白区域。