8

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

标准是：

  • 用户输入网格大小（程序应该缩放，因为这可能非常大）。
  • 用户输入网格划分因子（多少部分）。
  • 网格是一个矩形的六角网格，顶部和底部都加盖，左右环绕。
  • 零件没有碎片。
  • 其他零件内没有零件。
  • 没有微小或超大的零件。
  • 随机形状的零件，不是完美的圆形，或串成的蛇形。

我的解决方案：

  • 创建一个可以访问/操作相邻单元格的方法。
  • 随机确定每个部分的大小（所有部分的总和等于整个二维数组的大小）。
  • 用最后一部分的 id 号填充整个 2D 数组。
  • 对于除最后一个部分之外的每个部分：
  • 在 2D 数组的随机单元格中播种当前零件 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 数组之前没有指定零件尺寸，而只是指定零件数量并动态随机生成零件尺寸，这就留下了形成微小零件的可能性，这也可能不会在那里，尤其是当二维数组非常大时。我当前的零件尺寸方法将零件尺寸限制在二维数组总尺寸的 10% 到 40% 之间。如果有一些超级优雅的方法可以做到这一点，我可以不指定零件尺寸 - 用户将拥有的唯一控制是二维数组大小和零件数量。

其他想法：

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

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

你会如何处理这个问题？有没有一些我可以用来简化事情的性感数学？

谢谢

4

3 回答 3

5

几个月前我为一个游戏做了类似的事情，虽然它是一个矩形网格而不是一个六角网格。尽管如此，理论是相同的，它提出了大小大致相等的漂亮连续区域——有些更大，有些更小，但都不是太小或太大。YMMV。

  1. 创建一个指向网格中所有空间的指针数组。随机排列数组。
  2. 分配其中的前 N ​​个 ID - 1、2、3 等。
  3. 直到数组指向没有没有 ID 的空格，
  4. 遍历数组寻找没有 ID 的空间
  5. 如果该空间在网格中有具有 ID 的邻居，则从其邻居的 ID 的加权随机选择中为该空间分配 ID。
  6. 如果它没有具有 ID 的邻居，请跳到下一个。
  7. 一旦没有非空白空间，您的地图就会有足够的斑点区域。
于 2010-08-05T15:27:10.233 回答
3

这就是我要做的：使用 Voronoi 算法。首先放置一些随机点，然后让 Voronoi 算法生成零件。要了解它的外观，请参阅：this applet。

于 2010-08-05T15:22:10.843 回答
1

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

我只是想提供一些关于如何进行随机扰动的想法。如果您以最终解决方案执行此操作，那么它要么需要很长时间，要么非常少。您可以尝试进行多分辨率扰动。因此，从一个相当小的网格开始，随机播种，计算 Voronoi 图。然后随机扰动边界 - 例如，对于具有不同区域的每一对相邻单元格，以一种或另一种方式推动该区域。您可能需要运行后期处理以确保您没有小岛......一个简单的洪水填充就可以了。

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

于 2010-10-01T12:29:46.400 回答