将网格（二维阵列）划分为随机形状的部分？
问题
我想将网格（二维数组）划分为随机形状的部分（想想地球的构造板块）。
标准是：
- 用户输入网格大小（程序应该缩放，因为这可能非常大）。
- 用户输入网格划分系数（多少部分）。
- 网格是一个矩形六角形网格，顶部和底部有盖，左右环绕。
- 零件无碎片。
- 其他零件内没有任何零件。
- 没有微小或超大零件。
- 随机形状的零件，不是完美的圆形，也不是蜿蜒的形状。
我的解决方案：
- 创建一个可以访问/操作相邻单元格的方法。
- 随机确定每个部分的大小（所有部分的总和等于整个 2D 数组的大小）。
- 用最后一个零件的 id 号填充整个二维数组。
- 对于除最后一个之外的每个零件：
- 将当前零件 ID 号播种到 2D 数组的随机单元中。
- 迭代整个数组并存储与已用当前部件 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% 之间。如果有一些超级优雅的方法来做到这一点，我可能可以不指定零件大小 - 用户唯一的控制是二维数组大小和零件数量。
其他想法：
- 将部件形成完美对齐的正方形，然后遍历二维阵列并随机允许每个部件侵占其他部件，将它们扭曲成随机形状。
- 在网格上绘制蜿蜒的线并填充创建的空间，也许使用一些像这样的数学： http://mathworld .wolfram.com/PlaneDivisionbyLines.html
结论：
所以问题是：我是一名初学者程序员，不确定我是否以正确的方式解决这个问题。我可以创建一些更多的“修补”方法，将支离破碎的部分转移到一起，并允许成型零件在陷入死胡同时“跳出”死胡同，但感觉很混乱。
您将如何解决这个问题？也许我可以用一些有趣的数学来简化事情？
谢谢
The Problem
I want to divide a grid (2D array) into random shaped parts (think earth's tectonic plates).
Criteria are:
- User inputs grid size (program should scale because this could be very large).
- User inputs grid division factor (how many parts).
- Grid is a rectangular shaped hex grid, and is capped top and bottom, wrap around left and right.
- No fragmentation of the parts.
- No parts inside other parts.
- No tiny or super-large parts.
- Random shaped parts, that are not perfect circles, or strung-out snaking shapes.
My solution:
- Create a method that can access/manipulate adjacent cells.
- Randomly determine the size of each part (the sum of all the parts equal the size of the whole 2D array).
- Fill the entire 2D array with the last part's id number.
- For each part except the last:
- Seed the current part id number in a random cell of the 2D array.
- Iterate over the entire array and store the address of each cell adjacent to any cells already seeded with the current part id number.
- Extract one of the stored addresses and fill that cell with the current plate id number (and so the part starts to form).
- Repeat until the part size is reached.
Note that to avoid parts with long strung out "arms" or big holes inside them, I created two storage arrays: one for cells adjacent
to just one cell with the current part id number, and the other for cells adjacent to more than one, then I exhaust the latter before the former.
Running my solution gives the following:
Grid size: 200
width: 20
height: 10
Parts: 7
66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220
Part number: 0
Part size: 47
Part number: 1
Part size: 30
Part number: 2
Part size: 26
Part number: 3
Part size: 22
Part number: 4
Part size: 26
Part number: 5
Part size: 22
Part number: 6
Part size: 27
Problems with my solution:
- The last part is always fragmented - in the case above there are three separate groups of sixes.
- The algorithm will stall when parts form in cul-de-sacs and don't have room to grow to their full size (the algorithm does not allow forming parts over other parts, unless it's the last part, which is layed down over the entire 2D array at the start).
- If I don't specify the part sizes before forming the 2d array, and just make do with specifying the number of parts and randomly generating the part sizes on the fly, this leaves open the possibility of tiny parts being formed, that might aswell not be there at all, especially when the 2D array is very large. My current part size method limits the parts sizes to between 10% and 40% of the total size of the 2D array. I may be okay with not specifying the parts sizes if there is some super-elegant way to do this - the only control the user will have is 2d array size and number of parts.
Other ideas:
- Form the parts in perfectly aligned squares, then run over the 2D array and randomly allow each part to encroach on other parts, warping them into random shapes.
- Draw snaking lines across the grid and fill in the spaces created, maybe using some math like this: http://mathworld.wolfram.com/PlaneDivisionbyLines.html
Conclusion:
So here's the rub: I am a beginner programmer who is unsure if I'm tackling this problem in the right way. I can create some more "patch up" methods, that shift the fragmented parts together, and allow forming parts to "jump out" of the cul-de-sacs if they get stuck in them, but it feels messy.
How would you approach this problem? Is there some sexy math I could use to simplify things perhaps?
Thx
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
几个月前，我在一款游戏中做了类似的事情，尽管它是矩形网格而不是六角形网格。尽管如此，理论是相同的，并且它提出了大小大致相等的漂亮连续区域 - 有些较大，有些较小，但没有一个太小或太大。 YMMV。
从其邻居的 ID 的加权随机选择中获得的 ID。
I did something similar for a game a few months back, though it was a rectangular grid rather than a hex grid. Still, the theory is the same, and it came up with nice contiguous areas of roughly equal size -- some were larger, some were smaller, but none were too small or too large. YMMV.
the ID from a weighted random selection of the IDs of its neighbors.
这就是我要做的：使用 Voronoi 算法。首先放置一些随机点，然后让 Voronoi 算法生成零件。要了解其外观，请参阅：此小程序。
Here's what I'd do: use Voronoi algorithm. At first place some random points, then let the Voronoi algorithm generate the parts. To get the idea how it looks like consult: this applet.
正如 Rekin 所建议的，Voronoi 图加上一些随机扰动通常会做得很好，并且在像您这样的离散空间上相对容易实现。
我只是想提供一些关于如何进行随机扰动的想法。如果您以最终分辨率执行此操作，那么要么会花费很长时间，要么会花费很少的时间。您可以尝试进行多分辨率扰动。因此，从一个相当小的网格开始，随机种子，计算 Voronoi 图。然后随机扰动边界 - 就像对于具有不同区域的每对相邻单元格，以一种或另一种方式推动该区域。您可能需要运行后期处理以确保没有小岛......简单的洪水填充就可以了。
然后创建一个两倍大小（在每个方向）的网格，并复制您的区域。您也许可以使用最近邻居。然后再次扰动边界，并重复直到达到所需的分辨率。
As Rekin suggested, a Voronoi diagram plus some random perturbation will generally do a good job, and on a discretized space like you've got, is relatively easy to implement.
I just wanted to give some ideas about how to do the random perturbation. If you do it at the final resolution, then it's either going to take a very long time, or be pretty minimal. You might try doing a multi-resolution perturbation. So, start with a rather small grid, randomly seed, compute the Voronoi diagram. Then randomly perturb the borders - something like, for each pair of adjacent cells with different regions, push the region one way or the other. You might need to run a post-process to make sure you have no tiny islands.. a simple floodfill will work.
Then create a grid that's twice the size (in each direction), and copy your regions over. You can probably use nearest neighbor. Then perturb the borders again, and repeat until you reach your desired resolution.